Python | LeetCode

Скидки до 90% на Wildberries На WB собрали стильную подборку одежды на любой вкус ✨ Внутри — модные платья, удобные джинсы, стильные куртки и другие популярные модели от проверенных брендов. Кстати, сейчас на Wildberries действуют скидки до 90% и быстрая доставка от 1 дня. Идеальный момент для обновления гардероба ❤️ Перейти на сайт #реклама wildberries.ru О рекламодателе

Задача: 215. Kth Largest Element in an Array Сложность: medium Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве. Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент. Пример:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

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

class Solution:
    def findKthLargest(self, nums, k):
        nums.sort(reverse=True)
        return nums[k - 1]

Ставь 👍 и забирай 📚 Базу знаний

Задача: 892. Surface Area of 3D Shapes Сложность: easy Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности. Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

def surfaceArea(grid):
    n = len(grid)
    area = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                area += (grid[i][j] * 4) + 2
            if i > 0:
                area -= min(grid[i][j], grid[i-1][j]) * 2
            if j > 0:
                area -= min(gri

Ставь 👍 и забирай 📚 Базу знаний

Скидки до 90% на Wildberries На WB собрали удобную и стильную обувь для всей семьи 🏃‍♂️ Модные кроссовки, удобные сабо, классические туфли и другие популярные модели от известных брендов. Кстати, сейчас на Wildberries действуют скидки до 90% и быстрая доставка от 1 дня. Отличный шанс пополнить свою коллекцию обуви ❤️ Перейти на сайт #реклама wildberries.ru О рекламодателе

Задача: 594. Longest Harmonious Subsequence Сложность: easy Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1. Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей. Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов. Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = {}
        res = 0
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if num + 1 in count:
                res = max(res, count[num] + count[num + 1])
            if num - 1 in count:
                res = max(res, count[num] + count[num - 1])
        
        return res

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1166. Design File System Сложность: medium Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями. Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы. Реализуйте класс FileSystem: - bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует. - int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует. Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

👨‍💻 Алгоритм: 1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции. 2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем. 3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение. 😎 Решение:

class FileSystem:

    def __init__(self):
        self.paths = {}

    def createPath(self, path: str, value: int) -> bool:
        if not path or (len(path) == 1 and path == "/") or path in self.paths:
            return False
        
        delim_index = path.rfind("/")
        parent = path[:delim_index]
        
        if len(parent) > 1 and parent not in self.paths:
            return False
        
        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        return self.paths.get(path, -1)

Ставь 👍 и забирай 📚 Базу знаний

Задача: 846. Hand of Straights Сложность: medium У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт. Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае. Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

👨‍💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение:

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        cardCount = Counter(hand)
        for card in sorted(hand):
            if cardCount[card] == 0:
                continue

            for nextCard in range(card, card + groupSize):
                if cardCount[nextCard] == 0:
                    return False
                cardCount[nextCard] -= 1

        return True

Ставь 👍 и забирай 📚 Базу знаний

Нейросеть проверит 100% закупок на стройке за минуты! 👍Контроль закупок за 15 минут в день. Нейросеть "Тринити" экономит ваше время и миллионы рублей Вы - генеральный директор строительной компании, и у вас катастрофически не хватает времени? Работаете 12+ часов в день и не можете контролировать каждую закупку? 💰Тратите миллионы на закупки, но не уверены, что получаете лучшие цены и качество? Хотите спать спокойно, зная, что ваши деньги под защитой? Просто загрузите счет или тендерный протокол в Telegram-бот Получите детальный анализ по 18 параметрам за 1 минуту Экономьте до 10% на каждой закупке без дополнительных усилий В 3-5 раз дешевле, чем содержать штат контролеров! Работает 24/7 без выходных и отпусков. 👌Узнайте про наш телеграм-бот и тестируйте бесплатно 7 дней! Экономия в первый же день. Перейти на сайт #реклама 16+ trinitysafe.ru О рекламодателе

Задача: 93. Restore IP Addresses Сложность: medium Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия: - 'A' -> "1" - 'B' -> "2" - ... - 'Z' -> "26" Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как: - "AAJF" с группировкой (1 1 10 6) - "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06". Для данной строки s, содержащей только цифры, верните количество способов декодирования. Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число. Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

👨‍💻 Алгоритм: 1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0. 2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов. 3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач. 😎 Решение:

class Solution(object):
    def valid(self, s, start, length):
        return length == 1 or (
            s[start] != "0"
            and (length < 3 or s[start : start + length] <= "255")
        )

    def helper(self, s, startIndex, dots, ans):
        remainingLength = len(s) - startIndex
        remainingNumberOfIntegers = 4 - len(dots)
        if (
            remainingLength > remainingNumberOfIntegers * 3
            or remainingLength < remainingNumberOfIntegers
        ):
            return
        if len(dots) == 3:
            if self.valid(s, startIndex, remainingLength):
                temp = ""
                last = 0
                for dot in dots:
                    temp += s[last : last + dot] + "."
                    last += dot
                temp += s[startIndex:]
                ans.append(temp)
            return
        for curPos in range(1, min(4, remainingLength + 1)):
            dots.append(curPos)
            if self.valid(s, startIndex, curPos):
                self.helper(s, startIndex + curPos, dots, ans)
            dots.pop()

    def restoreIpAddresses(self, s):
        answer = []
        self.helper(s, 0, [], answer)
        return answer

Ставь 👍 и забирай 📚 Базу знаний

Бесплатный онлайн-марафон для руководителей Два дня практических онлайн-встреч с топ-экспертами в области управления — на них расскажем, как выстроить слаженную работу сотрудников и забыть о хаосе с помощью автоматизации. Спикеры Битрикс24, SETTERS EDUCATION, «ВкусВилл» и Максим Батырев расскажут: — как обеспечить рост команды без регламентов и ручного управления — как мотивировать сотрудников и давать обратную связь — как управлять большим потоком задач и контролировать их выполнение — как выстраивать эффективную коммуникацию с командой Бонусы для всех участников: — чек-лист: «Как обезопасить команду от кибермошенников?» — бесплатная консультация по автоматизации командной работы Бесплатно. 17–18 марта. Подробная программа мероприятия и регистрация — на сайте. Узнать больше #реклама 16+ marathon.bitrix24.works О рекламодателе

Задача: 1663. Smallest String With A Given Numeric Value Сложность: medium Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее. Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8. Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k. Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке. Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

👨‍💻 Алгоритм: 1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции. 2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции: Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1. Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции. Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции. 3⃣Повторять процесс, пока все позиции не будут заполнены. 😎 Решение:

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        result = ['a'] * n
        
        for position in range(n):
            positionsLeft = (n - position - 1)
            if k > positionsLeft * 26:
                add = k - (positionsLeft * 26)
                result[position] = chr(ord('a') + add - 1)
                k -= add
            else:
                k -= 1
        
        return ''.join(result

Ставь 👍 и забирай 📚 Базу знаний

Где чатиться с аутсорсерами и подрядчиками? Пригласите подрядчиков и клиентов в ваш рабочий мессенджер Битрикс24. Они увидят только свои чаты, задачи и звонки, а внутренние данные компании остаются закрытыми. Всё нужное для работы: • Общий чат проекта со всеми участниками • Доступ к задачам, файлам и календарю проекта • Гибкие права доступа и безопасность данных Общайтесь, созванивайтесь и согласовывайте прямо в Битрикс24, можно в мобильном приложении. Зарегистрироваться #реклама 16+ bitrix24.ru О рекламодателе

Задача: 258. Add Digits Сложность: easy Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его. Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

👨‍💻 Алгоритм: 1️⃣Инициализируйте переменную digital_root значением 0. 2️⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3️⃣Верните значение digital_root. 😎 Решение:

class Solution:
    def addDigits(self, num: int) -> int:
        digital_root = 0
        while num > 0:
            digital_root += num % 10
            num //= 10
            if num == 0 and digital_root > 9:
                num = digital_root
                digital_root = 0
        return digital_root

Ставь 👍 и забирай 📚 Базу знаний

Задача: 979. Distribute Coins in Binary Tree Сложность: medium Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет. За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю. Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету. Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

👨‍💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0
        self.dfs(root)
        return self.moves

    def dfs(self, current: Optional[TreeNode]) -> int:
        if not current:
            return 0
        leftCoins = self.dfs(current.left)
        rightCoins = self.dfs(current.right)
        self.moves += abs(leftCoins) + abs(rightCoins)
        return current.val - 1 + leftCoins + rightCoins

Ставь 👍 и забирай 📚 Базу знаний

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 397. Integer Replacement Сложность: medium К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

👨‍💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:

class Solution:
    def integerReplacement(self, n: int) -> int:
        def helper(n, memo):
            if n == 1:
                return 0
            if n in memo:
                return memo[n]
            
            if n % 2 == 0:
                memo[n] = 1 + helper(n // 2, memo)
            else:
                memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
                
            return memo[n]
        
        return helper(n, {})

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

Input: heights = [1,1,4,2,1,3]
Output: 3

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

def heightChecker(heights):
    expected = sorted(heights)
    count = 0
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            count += 1
    return count

Ставь 👍 и забирай 📚 Базу знаний

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

👨‍💻 Алгоритм: 1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2. 2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1. 3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false. 😎 Решение:

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1Count = Counter(s1)
        s2Count = Counter(s2[:len(s1)])
        
        if s1Count == s2Count:
            return True
        
        for i in range(len(s1), len(s2)):
            s2Count[s2[i]] += 1
            s2Count[s2[i - len(s1)]] -= 1
            if s2Count[s2[i - len(s1)]] == 0:
                del s2Count[s2[i - len(s1)]]
            if s1Count == s2Count:
                return True
        
        return False

Ставь 👍 и забирай 📚 Базу знаний

Задача: 200. Number of Islands Сложность: medium Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов. Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой. Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

👨‍💻 Алгоритм: 1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS). 2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый. 3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров. 😎 Решение:

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition Сложность: medium Вам дан массив целых чисел nums и целое число target. Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные answer равным 0 и n как длину массива nums. Отсортируйте массив nums. Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7. 2⃣Итерация и бинарный поиск: Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left]. Если left <= right, добавьте количество допустимых подпоследовательностей к answer. 3⃣Возврат результата: Верните answer по модулю 10^9+7. 😎 Решение:

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        mod = 10**9 + 7
        
        power = [1] * n
        for i in range(1, n):
            power[i] = power[i - 1] * 2 % mod
        
        answer = 0
        left, right = 0, n - 1
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                answer = (answer + power[right - left]) % mod
                left += 1
            else:
                right -= 1
        
        return answer

Ставь 👍 и забирай 📚 Базу знаний