Python | LeetCode

#medium Задача: 64. Minimum Path Sum На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути. Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени. Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

👨‍💻 Алгоритм: 1️⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы. 2️⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз. 3️⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий. 😎 Решение:

class Solution:
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i == m - 1 and j != n - 1:
                    dp[i][j] = grid[i][j] + dp[i][j + 1]
                elif j == n - 1 and i != m - 1:
                    dp[i][j] = grid[i][j] + dp[i + 1][j]
                elif j != n - 1 and i != m - 1:
                    dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1])
                else:
                    dp[i][j] = grid[i][j]
        return dp[0][0]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 63. Unique Paths II Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями. Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла. Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9. Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

👨‍💻 Алгоритм: 1️⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем. 2️⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца. 3️⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях. 😎 Решение:

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        if obstacleGrid[0][0] == 1:
            return 0

        obstacleGrid[0][0] = 1

        for i in range(1, m):
            obstacleGrid[i][0] = int(
                obstacleGrid[i][0] == 0 and obstacleGrid[i - 1][0] == 1
            )

        for j in range(1, n):
            obstacleGrid[0][j] = int(
                obstacleGrid[0][j] == 0 and obstacleGrid[0][j - 1] == 1
            )

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = (
                        obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                    )
                else:
                    obstacleGrid[i][j] = 0

        return obstacleGrid[m - 1][n - 1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 62. Unique Paths На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Даны два целых числа m и n, верните количество возможных уникальных путей, которые робот может пройти, чтобы достичь нижнего правого угла. Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9. Пример:

Input: m = 3, n = 7
Output: 28

👨‍💻 Алгоритм: 1️⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами. 2️⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1]. 3️⃣Вернуть d[m - 1][n - 1]. 😎 Решение:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1

        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Сливаем вам 2 архива на 500 курсов! ➤ Backend и языки программирования: - Python - REST - Java - PHP - Go - SQL - NoSQL - C# - C++ - Rust - JavaScript - Другое ➤ Frontend и Web-дизайн: - JavaScript - Figma - Web-Дизайн - HTML/CSS - Верстка - UI/UX - Другое

#medium Задача: 61. Rotate List Дан указатель на начало связного списка, поверните список вправо на k позиций. Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

👨‍💻 Алгоритм: 1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n. 2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n). 3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head. 😎 Решение:

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head

        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head

        new_tail = head
        for i in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next

        new_tail.next = None

        return new_head

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#hard Задача: 60. Permutation Sequence Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок. Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3: "123" "132" "213" "231" "312" "321" Дано n и k, верните k-ю перестановку последовательности. Пример:

Input: n = 3, k = 3
Output: "213"

👨‍💻 Алгоритм: 1️⃣Сгенерируйте входной массив nums чисел от 1 до N. 2️⃣Вычислите все факториальные основы от 0 до (N−1)!. 3️⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). Используйте коэффициенты факториалов для построения перестановки. Верните строку перестановки. 😎 Решение:

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorials, nums = [1], ["1"]
        for i in range(1, n):
            factorials.append(factorials[i - 1] * i)
            nums.append(str(i + 1))
        k -= 1
        output = []
        for i in range(n - 1, -1, -1):
            idx = k // factorials[i]
            k -= idx * factorials[i]
            output.append(nums[idx])
            del nums[idx]
        return "".join(output)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

БЕСПЛАТНЫЙ БОТ ДЛЯ ПОДГОТОВКИ К СОБЕСУ 15000 вопросов из СБЕР, ТИНЬКОФФ, ЯНДЕКС, МТС и GOOGLE 🌐 PYTHON, JAVA, JS, C#, GO, KOTLIN 📗ФРЕЙМВОРКИ 📕ЯЗЫКИ 📘АЛГОРИТМЫ МЫ НЕ ЗАБЫЛИ ПРО СОФТ СКИЛЫ, ОНИ ТУТ

– Помощь с pet-проектом – Составление roadmap – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#medium Задача: 59. Spiral Matrix II Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке. Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

👨‍💻 Алгоритм: 1️⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2️⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3️⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        def idx_convert_1D_2D(idx):
            return idx // n, idx % n

        def is_out_of_bound(row, col):
            return row < 0 or row >= n or col < 0 or col >= n

        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        result = [[0] * n for _ in range(n)]
        cur_dir_idx = 0
        row, col = 0, 0
        for i in range(1, n * n + 1):
            result[row][col] = i
            dx, dy = dirs[cur_dir_idx]
            if is_out_of_bound(row + dx, col + dy) or result[row + dx][col + dy] > 0:
                cur_dir_idx = (cur_dir_idx + 1) % 4
            dx, dy = dirs[cur_dir_idx]
            row, col = row + dx, col + dy
        return result

🪙 1096 вопроса вопроса на Python разработчика 🔒 База собесов | 🔒 База тестовых

#easy Задача: 58. Length of Last Word Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке. Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами. Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

👨‍💻 Алгоритм: 1️⃣Поиск последнего слова: Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова. 2️⃣Определение длины последнего слова: После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл. 3️⃣Итог: Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины. 😎 Решение:

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        p = len(s) - 1
        while p >= 0 and s[p] == " ":
            p -= 1

        length = 0
        while p >= 0 and s[p] != " ":
            p -= 1
            length += 1
        return length

🪙 1096 вопроса вопроса на Python разработчика 🔒 База собесов | 🔒 База тестовых