Python | LeetCode

#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 разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 57. Insert Interval Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала. Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы). Верните массив intervals после вставки. Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его. Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

👨‍💻 Алгоритм: 1️⃣ Инициализация переменных: Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата. 2️⃣Обработка случаев без перекрытия и с перекрытием: В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему. В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один. 3️⃣Обработка интервалов после вставки: Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним. Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом. 😎 Решение:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        res = []

        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

        while i < n:
            res.append(intervals[i])
            i += 1

        return res

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

📌 Составили список лучших каналов от действующих разработчиков: Python Developer — советы и практики от действующего Senior-разработчика Java Developer — секреты и тонкости программирования на Java Frontend Developer — готовый код и полезные ресурсы для любого фронтендера

#medium Задача: 56. Merge Intervals Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

👨‍💻 Алгоритм: 1️⃣ Представление графа: Имея представленную интуицию, мы можем изобразить граф в виде списка смежности, вставляя направленные ребра в обоих направлениях, чтобы симулировать неориентированные ребра. 2️⃣Определение компонент связности: Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время. 3️⃣Объединение интервалов внутри компонент: Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу. Решение:

import collections

class Solution:
    def overlap(self, a, b):
        return a[0] <= b[1] and b[0] <= a[1]

    def buildGraph(self, intervals):
        graph = collections.defaultdict(list)
        for i, interval_i in enumerate(intervals):
            for j in range(i + 1, len(intervals)):
                if self.overlap(interval_i, intervals[j]):
                    graph[tuple(interval_i)].append(intervals[j])
                    graph[tuple(intervals[j])].append(interval_i)
        return graph

    def mergeNodes(self, nodes):
        min_start = min(node[0] for node in nodes)
        max_end = max(node[1] for node in nodes)
        return [min_start, max_end]

    def getComponents(self, graph, intervals):
        visited = set()
        comp_number = 0
        nodes_in_comp = collections.defaultdict(list)

        def markComponentDFS(start):
            stack = [start]
            while stack:
                node = tuple(stack.pop())
                if node not in visited:
                    visited.add(node)
                    nodes_in_comp[comp_number].append(node)
                    stack.extend(graph[node])

        for interval in intervals:
            if tuple(interval) not in visited:
                markComponentDFS(interval)
                comp_number += 1

        return nodes_in_comp, comp_number

    def merge(self, intervals):
        graph = self.buildGraph(intervals)
        nodes_in_comp, number_of_comps = self.getComponents(graph, intervals)
        return [self.mergeNodes(nodes_in_comp[comp]) for comp in range(number_of_comps)]

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

😮 Добавлена новая база слитых курсов на 800ГБ: Программирование: https://t.me/+tHab1ttNTE85Yjgy Python: https://t.me/+zpUxu2ScikwwZGJi Графика и дизайн: https://t.me/+GwFBZ4HOcOs2ZDcy Frontend и Web: https://t.me/+8op47ibl8thhYTIy

#medium Задача: 55. Jump Game Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае. Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

👨‍💻Алгоритм: 1️⃣ Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2️⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3️⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:

class Solution:
    def __init__(self):
        self.memo = []
        self.nums = []

    def canJumpFromPosition(self, position):
        if self.memo[position] != -1:
            return self.memo[position] == 1
        furthestJump = min(position + self.nums[position], len(self.nums) - 1)
        for nextPosition in range(position + 1, furthestJump + 1):
            if self.canJumpFromPosition(nextPosition):
                self.memo[position] = 1
                return True
        self.memo[position] = 0
        return False

    def canJump(self, nums):
        self.nums = nums
        self.memo = [-1] * len(nums)
        self.memo[-1] = 1
        return self.canJumpFromPosition(0)

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

#hard Задача: 43. Multiply Strings Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки. Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа. Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

👨‍💻 Алгоритм: 1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber: Инициализируйте переменную carry, первоначально равную 0. Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber. 2️⃣Для каждой цифры в firstNumber: Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению. Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру в массив currentResult. Разделите умножение на 10, чтобы получить новое значение для carry. 3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult. Добавьте currentResult к ans. Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль. Переверните ans и верните его. 😎 Решение:

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        first_number = num1[::-1]
        second_number = num2[::-1]

        N = len(first_number) + len(second_number)
        answer = [0] * N

        for index, digit in enumerate(second_number):
            answer = self.addStrings(
                self.multiplyOneDigit(first_number, digit, index), answer
            )

        if answer[-1] == 0:
            answer.pop()

        answer.reverse()
        return "".join(str(digit) for digit in answer)

    def multiplyOneDigit(self, first_number: str, digit2: str, num_zeros: int):
        currentResult = [0] * num_zeros
        carry = 0

        for digit1 in first_number:
            multiplication = int(digit1) * int(digit2) + carry
            carry = multiplication // 10
            currentResult.append(multiplication % 10)

        if carry != 0:
            currentResult.append(carry)
        return currentResult

    def addStrings(self, result: list, answer: list) -> list:
        carry = 0
        new_answer = []
        for digit1, digit2 in zip_longest(result, answer, fillvalue=0):
            curr_sum = digit1 + digit2 + carry
            carry = curr_sum // 10
            new_answer.append(curr_sum % 10)

        return new_answer

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

#hard Задача: 42. Trapping Rain Water Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя. Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

👨‍💻 Алгоритм: 1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max. 2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max. 3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans. 😎 Решение:

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

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

👩‍💻Хотите улучшить свои навыки python? На канале программистика вы найдёте: 👀Огромную библиотеку книг 👀Уроки по python 👀Фундаментальные статьи 👀Полезные библиотеки и методы python 👍Подписывайся и развивайся!!!!

#hard Задача: 41. First Missing Positive Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums. Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти. Пример:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

👨‍💻 Алгоритм: 1️⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen. Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true. 2️⃣Найти наименьшее недостающее положительное число: Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число. 3️⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число. 😎 Решение:

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        seen = [False] * (n + 1)

        for num in nums:
            if 0 < num <= n:
                seen[num] = True

        for i in range(1, n + 1):
            if not seen[i]:
                return i

        return n + 1

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

#medium Задача: 40. Combination Sum II Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target. Каждое число в candidates может быть использовано только один раз в комбинации. Примечание: Набор решений не должен содержать повторяющихся комбинаций. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

👨‍💻 Алгоритм: 1️⃣Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию backtrack(comb, remain, curr, candidate_groups, results). Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции: comb: комбинация, которую мы построили на данный момент. remain: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы. curr: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков. counter: текущая таблица счётчиков. results: окончательные комбинации, которые достигают целевой суммы. 2️⃣При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть sum(comb) = target), и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму. 3️⃣Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию backtrack() с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название. 😎 Решение:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def backtrack(comb, remain, curr, counter, results):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for next_curr in range(curr, len(counter)):
                candidate, freq = counter[next_curr]

                if freq <= 0:
                    continue

                comb.append(candidate)
                counter[next_curr] = (candidate, freq - 1)
                backtrack(comb, remain - candidate, next_curr, counter, results)
                counter[next_curr] = (candidate, freq)
                comb.pop()

        results = []
        counter = Counter(candidates)
        counter = [(c, counter[c]) for c in counter]

        backtrack(
            comb=[], remain=target, curr=0, counter=counter, results=results
        )

        return results

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

Ну все! Теперь не нужно тратить деньги на топовые курсы и книги по программированию — их выложили в Telegram бесплатно Все найденные курсы собирают тут — @portalToIT По этим курсам выучить любой язык за 7 дней вообще не проблема, находка для начинающих программистов.