Python | LeetCode

#medium Задача: 261. Graph Valid Tree У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе. Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае. Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

import collections
from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        adj_list = [[] for _ in range(n)]
        for A, B in edges:
            adj_list[A].append(B)
            adj_list[B].append(A)
        
        parent = {0: -1}
        queue = collections.deque([0])
        
        while queue:
            node = queue.popleft()
            for neighbour in adj_list[node]:
                if neighbour == parent[node]:
                    continue
                if neighbour in parent:
                    return False
                parent[neighbour] = node
                queue.append(neighbour)
        
        return len(parent) == n

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

#medium Задача: 260. Single Number III Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке. Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство.. Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num
        diff = xor & -xor
        res = [0, 0]
        for num in nums:
            if num & diff == 0:
                res[0] ^= num
            else:
                res[1] ^= num
        return res

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

💸 Вакансии для IT'шников Выбери своё направление ⤵ 1. Frontend 2. Python 3. Java 4. Тестировщик QA 5. Data Science 6. DevOps 7. C# 8. С/C++ 9. Golang 10. PHP 11. Kotlin 12. Swift

#medium Задача: 259. 3Sum Smaller Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target. Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

👨‍💻 Алгоритм: 1️⃣Отсортируйте массив nums. 2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_count = 0
        for i in range(len(nums) - 2):
            sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
        return sum_count

    def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
        sum_count = 0
        for i in range(startIndex, len(nums) - 1):
            j = self.binarySearch(nums, i, target - nums[i])
            sum_count += j - i
        return sum_count

    def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
        left, right = startIndex, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

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

#easy Задача: 258. Add Digits Дано целое число 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

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

Форум Управление данными 2024, 26 сентября Стратегия, инструменты, опыт. Центральное событие года. Все о данных. Перенастройка в новой реальности Зарегистрироваться #реклама osp.ru О рекламодателе

#easy Задача: 257. Binary Tree Paths Дано корневое дерево, верните все пути от корня до листа в любом порядке. Лист — это узел без детей. Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

👨‍💻 Алгоритм: 1️⃣Если текущий узел не является null, добавьте его значение к текущему пути. Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей. Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов. 2️⃣Начните с корневого узла, пустого пути и пустого списка путей. 3️⃣Верните список всех путей от корня до листа. 😎 Решение:

class Solution:
    def construct_paths(self, root: TreeNode, path: str, paths: List[str]):
        if root:
            path += str(root.val)
            if not root.left and not root.right:
                paths.append(path)
            else:
                path += "->"
                self.construct_paths(root.left, path, paths)
                self.construct_paths(root.right, path, paths)

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        paths = []
        self.construct_paths(root, "", paths)
        return paths

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

#medium Задача: 256. Paint House Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет. Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3. Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее... Верните минимальную стоимость покраски всех домов. Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

👨‍💻 Алгоритм: 1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение:

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        dp = [[0] * 3 for _ in range(n)]
        dp[0] = costs[0]
        
        for i in range(1, n):
            dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
            dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
            dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
        
        return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])

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

Яндекс Заправки для бизнеса. Скидка до 3%. Без комиссий Управляйте заправками сотрудников с экономией на топливе. Возмещайте до 20% от стоимости топлива через возврат НДС. Получайте закрывающие документы в электронном виде. Еще удобнее с мобильным приложением. Узнать больше #реклама 16+ business.go.yandex О рекламодателе

#medium Задача: 213. House Robber II Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь. Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию. Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        max1 = self.rob_simple(nums, 0, len(nums) - 2)
        max2 = self.rob_simple(nums, 1, len(nums) - 1)

        return max(max1, max2)

    def rob_simple(self, nums, start, end):
        t1, t2 = 0, 0

        for i in range(start, end + 1):
            temp = t1
            current = nums[i]
            t1 = max(current + t2, t1)
            t2 = temp

        return t1

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

Налоговый мониторинг: что изменилось в 2024 году Налоговая приняла поправки, обязательные для всех участников мониторинга. Подключение к информационной системе «Налог 3» и новые формы документов - далеко не полный список изменений, с которыми предстоит столкнуться бизнесу. Рассказываем обо всех нововведениях этого года. Читайте статью, чтобы узнать: ✅ Какие компании могут подключиться к мониторингу по льготным условиям. ✅ Какие новые формы для подключения доступны с 2024 года. ✅ Как соблюсти все новые требования и ничего не упустить. Узнать больше #реклама tech.vk.com О рекламодателе

#hard Задача: 212. Word Search II Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске. Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове. Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

👨‍💻 Алгоритм: 1️⃣ Построение Trie: Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже. 2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки: Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell). 3️⃣ Обход соседних ячеек: В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell). На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале. 😎 Решение:

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        WORD_KEY = "$"

        trie = {}
        for word in words:
            node = trie
            for letter in word:
                node = node.setdefault(letter, {})
            node[WORD_KEY] = word

        rowNum = len(board)
        colNum = len(board[0])
        matchedWords = []

        def backtracking(row, col, parent):
            letter = board[row][col]
            currNode = parent[letter]

            word_match = currNode.pop(WORD_KEY, False)
            if word_match:
                matchedWords.append(word_match)

            board[row][col] = "#"

            for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                newRow, newCol = row + rowOffset, col + colOffset
                if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
                    continue
                if board[newRow][newCol] not in currNode:
                    continue
                backtracking(newRow, newCol, currNode)

            board[row][col] = letter

            if not currNode:
                parent.pop(letter)

        for row in range(rowNum):
            for col in range(colNum):
                if board[row][col] in trie:
                    backtracking(row, col, trie)

        return matchedWords

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

Обучаем Java-разработчиков оплата после выхода на работу В Kata Academy можно выучиться на Java-разработчика бесплатно, а заплатить уже после трудоустройства по специальности из фактической зарплаты. Если задуматься, то все в выигрыше: — ты получаешь работу в Москве или Санкт-Петербурге с хорошей зарплатой, мы получаем процент за инвестиции в тебя; — в наших интересах научить тебя так, чтобы твоя зарплата была как можно выше; — мы прокачиваем твои навыки еще 2 года после курса: проводим выездные мероприятия и мастер-классы — и доходы наших выпускников растут; — мы не зависим от банков и их рассрочек — кризис не повлиял на доступность курсов. Чтобы попасть на курс, нужно выполнить небольшое тестовое задание. Переходи по ссылке и оставляй заявку! Узнать больше #реклама 16+ kata.academy О рекламодателе

#medium Задача: 211. Design Add and Search Words Data Structure Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову. Реализуйте класс WordDictionary: WordDictionary() инициализирует объект. void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже. bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой. Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

👨‍💻 Алгоритм: 1️⃣ Инициализация и добавление слова: Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode. Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова. 2️⃣ Поиск слова в узле: Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова. 3️⃣ Поиск слова в структуре данных: Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false. 😎 Решение:

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node["$"] = True

    def search(self, word: str) -> bool:

        def search_in_node(word, node) -> bool:
            for i, ch in enumerate(word):
                if ch not in node:
                    if ch == ".":
                        for x in node:
                            if x != "$" and search_in_node(word[i + 1:], node[x]):
                                return True
                    return False
                else:
                    node = node[ch]
            return "$" in node

        return search_in_node(word, self.trie)

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#medium Задача: 255. Verify Preorder Sequence in Binary Search Tree Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска. Пример:

Input: preorder = [5,2,1,3,6]
Output: true

👨‍💻 Алгоритм: 1️⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек. 2️⃣Итерируйте по массиву preorder. Для каждого num: Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit. Если num <= minLimit, верните false. Добавьте num в стек. 3️⃣Верните true, если удалось пройти весь массив. 😎 Решение:

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        minLimit = float('-inf')
        stack = []
        
        for num in preorder:
            while stack and stack[-1] < num:
                minLimit = stack.pop()
            
            if num <= minLimit:
                return False
            
            stack.append(num)
        
        return True

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

Помощь в трудоустройстве в IT-сфере! По всей России объявили бесплатную программу на шестимесячное обучение по IT-cпециальностям. Запись на участие в программе продлится до конца июля, но чтобы туда попасть, нужно пройти специальный профтест. По результату тестирования сразу узнаете, какая профессия вам подойдет, и проходите ли вы на бесплатное обучение. Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#medium Задача: 253. Meeting Rooms II Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов. Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        heap = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= heap[0]:
                heapq.heapreplace(heap, intervals[i][1])
            else:
                heapq.heappush(heap, intervals[i][1])
        
        return len(heap)

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

ТОП-4 Курса по Data Science Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. 🎓Освойте продвинутую математику с самых азов 💻Научитесь создавать ML-модели и работать с нейронными сетями ✅Получите реальный опыт на практических проектах 🏠Начните работать удаленно 💰Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#easy Задача: 252. Meeting Rooms Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи. Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        def overlap(interval1: List[int], interval2: List[int]) -> bool:
            return (interval1[0] >= interval2[0] and interval1[0] < interval2[1]
                or interval2[0] >= interval1[0] and interval2[0] < interval1[1])

        for i in range(len(intervals)):
            for j in range(i + 1, len(intervals)):
                if overlap(intervals[i], intervals[j]):
                    return False
        return True

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