Python | LeetCode

#easy Задача: 501. Find Mode in Binary Search Tree Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве. Если в дереве более одной моды, верните их в любом порядке. Предположим, что BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла. Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла. Оба поддерева также должны быть бинарными деревьями поиска. Пример:

Input: root = [1,null,2,2]
Output: [2]

👨‍💻 Алгоритм: 1⃣Обход дерева Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values. 2⃣Поиск мод Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans. 3⃣Возврат результата Верните список ans. 😎 Решение:

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        values = []
        self.dfs(root, values)
        
        max_streak = curr_streak = curr_num = 0
        ans = []
        
        for num in values:
            if num == curr_num:
                curr_streak += 1
            else:
                curr_streak = 1
                curr_num = num
                
            if curr_streak > max_streak:
                ans = [num]
                max_streak = curr_streak
            elif curr_streak == max_streak:
                ans.append(num)
                
        return ans
    
    def dfs(self, node, values):
        if not node:
            return
        self.dfs(node.left, values)
        values.append(node.val)
        self.dfs(node.right, values)

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

Канал про IT и Ботов Мемчики, фичи и тг боты – то, что обсуждают на этом канале 📱 🖥 Ждем тебя: @sudoteach

💡 В EasyOffer 2.0 появится фильтрация вопросов по грейдам и типам интервью! 📊 Например, вот вероятности ТОП-30 вопросов, которые задают на HR-скрининге Python-разработчику уровня Middle/Senior. Данные основаны на 53 реальных интервью. 97% Какие у тебя зарплатные ожидания 73% Какие у тебя есть вопросы 44% Какие критерии при выборе будущей работы 41% Расскажи о себе 38% Почему ищешь работу 35% Расскажи про свой опыт 35% Расскажи про проект на предыдущей работе 32% Почему уволился с предыдущей работы 29% Где территориально сейчас живешь/находишься 23% Есть ли другие предложения по работе 17% Есть ли военный билет 17% Почему хочешь сменить работу 17% Как проводишь свободное время 17% Расскажи про задачи на предыдущей работе 17% Сколько коммерческого опыта работы с Python 17% С какими БД работал 14% Находишься ли в активном поиске работы 14% С каким стеком работаешь 14% Почему решил откликнуться на нашу вакансию 14% Какой текущий статус поиска работы 11% Почему решил стать программистом 11% С какими фреймворками работал 11% Какую зарплату получал на предыдущей работе 11% Работаешь ли в настоящий момент 11% На какой грейд себя оцениваешь 11% Как быстро можешь приступить к работе после получения офера 11% Расскажи про свои pet-проекты 8% Какие знаешь типы данных в Python 8% Что такое декоратор в Python 8% Что ищешь на новой работе 🚀 Скоро стартует краудфандинговая кампания, которая поможет ускорить разработку EasyOffer 2.0. Первые спонсоры получат уникальные лимитированные награды! 📢 Если вам это интересно, подписывайтесь на канал 👉 этот телеграм канал

#hard Задача: 499. The Maze III В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него. Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо). Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно). Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

👨‍💻 Алгоритм: 1⃣Инициализация и вспомогательные функции Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной. 2⃣Запуск алгоритма Дейкстры Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов. 3⃣Поиск кратчайшего пути Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible". 😎 Решение:

import heapq

class State:
    def __init__(self, r, c, d, p):
        self.row = r
        self.col = c
        self.dist = d
        self.path = p

    def __lt__(self, other):
        return self.dist == other.dist and self.path < other.path or self.dist < other.dist

class Solution:
    def findShortestWay(self, maze, ball, hole):
        m, n = len(maze), len(maze[0])
        directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
        textDirections = ["l", "u", "r", "d"]
        
        heap = []
        heapq.heappush(heap, State(ball[0], ball[1], 0, ""))
        seen = [[False] * n for _ in range(m)]
        
        while heap:
            curr = heapq.heappop(heap)
            if seen[curr.row][curr.col]:
                continue
            if [curr.row, curr.col] == hole:
                return curr.path
            seen[curr.row][curr.col] = True
            
            for nextState in self.getNeighbors(curr.row, curr.col, maze, hole, directions, textDirections):
                heapq.heappush(heap, State(nextState.row, nextState.col, curr.dist + nextState.dist, curr.path + nextState.path))
        
        return "impossible"
    
    def getNeighbors(self, row, col, maze, hole, directions, textDirections):
        m, n = len(maze), len(maze[0])
        neighbors = []
        for i in range(4):
            dy, dx = directions[i]
            direction = textDirections[i]
            currRow, currCol, dist = row, col, 0
            while 0 <= currRow + dy < m and 0 <= currCol + dx < n and maze[currRow + dy][currCol + dx] == 0:
                currRow += dy
                currCol += dx
                dist += 1
                if [currRow, currCol] == hole:
                    break
            neighbors.append(State(currRow, currCol, dist, direction))
        return neighbors

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

#medium Задача: 498. Diagonal Traverse Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке. Пример:

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

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

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        
        N, M = len(mat), len(mat[0])
        result = []
        
        for d in range(N + M - 1):
            intermediate = []
            r = 0 if d < M else d - M + 1
            c = d if d < M else M - 1
            
            while r < N and c > -1:
                intermediate.append(mat[r][c])
                r += 1
                c -= 1
            
            if d % 2 == 0:
                result.extend(intermediate[::-1])
            else:
                result.extend(intermediate)
        
        return result

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

#medium Задача: 723. Candy Crush Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску. Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

def candyCrush(board):
    m, n = len(board), len(board[0])
    stable = False

    while not stable:
        stable = True
        crush = [[False] * n for _ in range(m)]

        for i in range(m):
            for j in range(n - 2):
                if abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
                    stable = False
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = True

        for i in range(m - 2):
            for j in range(n):
                if abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]) != 0:
                    stable = False
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = True

        for i in range(m):
            for j in range(n):
                if crush[i][j]:
                    board[i][j] = 0

        for j in range(n):
            idx = m - 1
            for i in range(m - 1, -1, -1):
                if board[i][j] != 0:
                    board[idx][j] = board[i][j]
                    idx -= 1
            for i in range(idx, -1, -1):
                board[i][j] = 0

    return board

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#easy Задача: 496. Next Greater Element I Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве. Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2. Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1. Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше. Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

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

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums1)
        
        for i in range(len(nums1)):
            found = False
            for j in range(len(nums2)):
                if nums2[j] == nums1[i]:
                    found = True
                if found and nums2[j] > nums1[i]:
                    res[i] = nums2[j]
                    break
        
        return res

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

#medium Задача: 722. Remove Comments Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными. Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой. Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

def removeComments(source):
    inBlock = False
    buffer = []
    result = []
    for line in source:
        i = 0
        if not inBlock:
            buffer = []
        while i < len(line):
            if not inBlock and i + 1 < len(line) and line[i:i+2] == "/*":
                inBlock = True
                i += 1
            elif inBlock and i + 1 < len(line) and line[i:i+2] == "*/":
                inBlock = False
                i += 1
            elif not inBlock and i + 1 < len(line) and line[i:i+2] == "//":
                break
            elif not inBlock:
                buffer.append(line[i])
            i += 1
        if buffer and not inBlock:
            result.append("".join(buffer))
    return result

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

Вебинар про UserGate SIEM ⚡ Отечественные компании каждый день сталкиваются с различными рисками и угрозами, часть из которых помогает закрыть отказоустойчивость. 📊Спикеры: - Дмитрий Чеботарев, менеджер по развитию UserGate SIEM; - Дмитрий Богданов, ведущий инженер UserGate. ✅ Расскажут об отказоустойчивости и кластеризации и о том, для чего они нужны; ✅ Покажут кейсы использования. Зарегистрироваться #реклама 16+ webinar.usergate.com О рекламодателе

#easy Задача: 495. Teemo Attacking Наш герой Тимо атакует врага Эшу ядовитыми атаками! Когда Тимо атакует Эшу, она оказывается отравленной на ровно duration секунд. Более формально, атака в секунду t означает, что Эша будет отравлена в течение интервала времени [t, t + duration - 1] включительно. Если Тимо атакует снова до окончания эффекта яда, таймер для него сбрасывается, и эффект яда закончится через duration секунд после новой атаки. Вам дано неубывающее целое число timeSeries, где timeSeries[i] обозначает, что Тимо атакует Эшу во вторую timeSeries[i], и целое число duration. Верните общее количество секунд, в течение которых Эша была отравлена. Пример:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

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

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        n = len(timeSeries)
        if n == 0:
            return 0

        total = 0
        for i in range(n - 1):
            total += min(timeSeries[i + 1] - timeSeries[i], duration)
        return total + duration

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

Совет на 2025 год - учите Data Science и Machine learning Все нейросети, базы данных компаний, выявление болезней и многое другое - не обходятся без DS и ML. А чтобы освоиться за несколько месяцев, а не лет, читайте канал Data Science. В нём на пальцах рассказывается, что и как учить, чтобы стать специалистом. Начните 2025 год с освоения новой профессии - devsp

#medium Задача: 494. Target Sum Вам дан массив целых чисел nums и целое число target. Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа. Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1". Верните количество различных выражений, которые можно построить и которые оцениваются в target. Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

👨‍💻 Алгоритм: 1⃣Инициализация и вызов рекурсивной функции Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target). 2⃣Рекурсивная функция calculate Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы. 3⃣Возврат результата После завершения всех рекурсивных вызовов верните значение счетчика решений. 😎 Решение:

class Solution:
    def __init__(self):
        self.count = 0

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.calculate(nums, 0, 0, S)
        return self.count

    def calculate(self, nums: List[int], i: int, sum: int, S: int):
        if i == len(nums):
            if sum == S:
                self.count += 1
        else:
            self.calculate(nums, i + 1, sum + nums[i], S)
            self.calculate(nums, i + 1, sum - nums[i], S)

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

Целевые кибератаки 2024: аналитика и кейсы На вебинаре 27 февраля команда Solar 4RAYS подведет итоги по следам расследований целевых атак 2024 года Вы узнаете, как профессиональные хакеры атакуют российские компании и обходят системы безопасности, когда защита не соответствует уровню угроз. А также какие тактики используют киберпреступники, каков конечный импакт для систем ИБ от воздействия хакеров и как выстроить стратегию защиты. Что будет на вебинаре: - Какие инструменты противодействия актуальны в 2025 году; - Какие отрасли бизнеса подвергались атакам и с какой целью; - Какие интересные техники использовали злоумышленники: разбор кейсов расследований. Все примеры и рекомендации основаны на реальных расследованиях инцидентов в российских организациях. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 491. Non-decreasing Subsequences Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = set()
        sequence = []
        self.backtrack(nums, 0, sequence, result)
        return list(result)

    def backtrack(self, nums, index, sequence, result):
        if index == len(nums):
            if len(sequence) >= 2:
                result.add(tuple(sequence))
            return
        if not sequence or sequence[-1] <= nums[index]:
            sequence.append(nums[index])
            self.backtrack(nums, index + 1, sequence, result)
            sequence.pop()
        self.backtrack(nums, index + 1, sequence, result)

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

#medium Задача: 721. Accounts Merge Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке. Пример:

nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

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

def accountsMerge(accounts):
    from collections import defaultdict

    graph = defaultdict(set)
    email_to_name = {}

    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            graph[first_email].add(email)
            graph[email].add(first_email)
            email_to_name[email] = name

    visited = set()
    merged_accounts = []

    def dfs(email):
        emails = [email]
        stack = [email]
        while stack:
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
                    emails.append(neighbor)
        return emails

    for email in graph:
        if email not in visited:
            visited.add(email)
            emails = dfs(email)
            merged_accounts.append([email_to_name[email]] + sorted(emails))

    return merged_accounts

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Уже есть опыт работы в ИТ, но хочешь прокачать скилы и продвинуться в карьере? Тогда скорее залетай на бесплатный ИТ-интенсив в Открытых школах Т1. Открытые школы — это возможность усилить свои навыки и получить оффер в ИТ-холдинг Т1. И все это за месяц, онлайн и в удобное вечернее время. Что ты получишь? ✅ бесплатное обучение в гибком формате: по вечерам, онлайн, из любого города РФ и РБ. ✅ материалы от HR для прокачки резюме и подготовки к интервью в Т1. ✅ много практики и уникальный рыночный опыт. ✅ поддержку опытных преподавателей и карьерный фаст-трек до мидла в Т1 для лучших выпускников. ✅ реальный шанс получить оффер в Т1. Более 1000 специалистов уже прошли этот путь — теперь твоя очередь! Регистрация до 14 марта! Подать заявку #реклама 16+ t1.ru О рекламодателе

#hard Задача: 489. Robot Room Cleaner Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка. Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot. Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов. Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке. Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

class Solution:
    def __init__(self):
        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        self.visited = set()
        self.robot = None

    def go_back(self):
        self.robot.turnRight()
        self.robot.turnRight()
        self.robot.move()
        self.robot.turnRight()
        self.robot.turnRight()

    def backtrack(self, row, col, d):
        self.visited.add((row, col))
        self.robot.clean()
        for i in range(4):
            new_d = (d + i) % 4
            new_row = row + self.directions[new_d][0]
            new_col = col + self.directions[new_d][1]
            if (new_row, new_col) not in self.visited and self.robot.move():
                self.backtrack(new_row, new_col, new_d)
                self.go_back()
            self.robot.turnRight()

    def cleanRoom(self, robot):
        self.robot = robot
        self.backtrack(0, 0, 0)

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

#medium Задача: 490. The Maze В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление. Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false. Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны. Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка данных Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции. 2⃣DFS обход Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции. 3⃣Результат Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false. 😎 Решение:

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        def dfs(m, n, maze, curr, destination, visit):
            if visit[curr[0]][curr[1]]:
                return False
            if curr == destination:
                return True
            visit[curr[0]][curr[1]] = True
            for dx, dy in directions:
                r, c = curr
                while 0 <= r < m and 0 <= c < n and maze[r][c] == 0:
                    r += dx
                    c += dy
                if dfs(m, n, maze, [r - dx, c - dy], destination, visit):
                    return True
            return False

        m, n = len(maze), len(maze[0])
        visit = [[False] * n for _ in range(m)]
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        return dfs(m, n, maze, start, destination, visit)

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