Python | LeetCode

🔥 Скрытые вакансии с удаленной работой для Python разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 Python Jobs | Вакансии
🔹 Data Science ML | Вакансии
🔹 Golang Go Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

👨‍💻 Алгоритм:

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

from collections import deque

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        if not root:
            return True

        queue = deque([root])
        nullNodeFound = False

        while queue:
            node = queue.popleft()
            
            if not node:
                nullNodeFound = True
            else:
                if nullNodeFound:
                    return False
                queue.append(node.left)
                queue.append(node.right)

        return True

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

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

👨‍💻 Алгоритм:

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

from itertools import permutations

def largestTimeFromDigits(arr):
    max_time = -1
    for perm in permutations(arr):
        hours = perm[0] * 10 + perm[1]
        minutes = perm[2] * 10 + perm[3]
        if hours < 24 and minutes < 60:
            max_time = max(max_time, hours * 60 + minutes)
    if max_time == -1:
        return ""
    return f"{max_time // 60:02}:{max_time % 60:02}"

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

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome
Сложность: hard

Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.

Верните минимальное количество шагов, необходимых для превращения s в палиндром.

Палиндром — это строка, которая читается одинаково как вперед, так и назад.

Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

👨‍💻 Алгоритм:

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.

2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:

Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎 Решение:

class Solution:
    def lcs(self, s1, s2, m, n, memo):
        if m == 0 or n == 0:
            return 0
        if memo[m][n] != -1:
            return memo[m][n]
        if s1[m - 1] == s2[n - 1]:
            memo[m][n] = 1 + self.lcs(s1, s2, m - 1, n - 1, memo)
        else:
            memo[m][n] = max(self.lcs(s1, s2, m - 1, n, memo), self.lcs(s1, s2, m, n - 1, memo))
        return memo[m][n]

    def minInsertions(self, s: str) -> int:
        n = len(s)
        sReverse = s[::-1]
        memo = [[-1] * (n + 1) for _ in range(n + 1)]
        return n - self.lcs(s, sReverse, n, n, memo)

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

Задача: 1103. Distribute Candies to People
Сложность: easy

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

👨‍💻 Алгоритм:

1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2

2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2

3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d


😎 Решение:

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        n = num_people
        p = int((2 * candies + 0.25)**0.5 - 0.5)
        remaining = int(candies - (p + 1) * p * 0.5)
        rows, cols = p // n, p % n
        
        d = [0] * n
        for i in range(n):
            d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
            if i < cols:
                d[i] += i + 1 + rows * n
        d[cols] += remaining
        return d

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

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

👨‍💻 Алгоритм:

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

class Solution:
    def search(self, L, n, S):
        seen = set()
        for start in range(n - L + 1):
            tmp = S[start:start + L]
            if tmp in seen:
                return start
            seen.add(tmp)
        return -1

    def longestRepeatingSubstring(self, S):
        n = len(S)
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, n, S) != -1:
                left = L + 1
            else:
                right = L - 1
        return left - 1

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм:

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution:
    def __init__(self):
        self.maxTime = float('-inf')
    
    def DFS(self, adjList, informTime, curr, time):
        self.maxTime = max(self.maxTime, time)
        for adjacent in adjList[curr]:
            self.DFS(adjList, informTime, adjacent, time + informTime[curr])
    
    def numOfMinutes(self, n, headID, manager, informTime):
        adjList = [[] for _ in range(n)]
        for i in range(n):
            if manager[i] != -1:
                adjList[manager[i]].append(i)
        self.DFS(adjList, informTime, headID, 0)
        return self.maxTime

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

Задача: 1027. Longest Arithmetic Subsequence
Сложность: medium

Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Пример:

Input: nums = [3,6,9,12]
Output: 4

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d.

2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].

3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].

😎 Решение:

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        dp = [{} for _ in range(len(nums))]
        max_length = 0
        
        for i in range(len(nums)):
            for j in range(i):
                diff = nums[i] - nums[j]
                if diff in dp[j]:
                    dp[i][diff] = dp[j][diff] + 1
                else:
                    dp[i][diff] = 2  # Start a new sequence
                max_length = max(max_length, dp[i][diff])
        
        return max_length

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

👨‍💻 Алгоритм:

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

def minSubsequences(source, target):
    subsequences_count = 0
    target_index = 0

    while target_index < len(target):
        source_index = 0
        subsequences_count += 1
        start_index = target_index

        while source_index < len(source) and target_index < len(target):
            if source[source_index] == target[target_index]:
                target_index += 1
            source_index += 1

        if target_index == start_index:
            return -1

    return subsequences_count

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

Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.

Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

👨‍💻 Алгоритм:

1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.

2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.

3⃣Возврат результата
Верните значение longestSubarray.

😎 Решение:

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        prefixSum = 0
        longestSubarray = 0
        indices = {}
        
        for i, num in enumerate(nums):
            prefixSum += num
            
            if prefixSum == k:
                longestSubarray = i + 1
            if prefixSum - k in indices:
                longestSubarray = max(longestSubarray, i - indices[prefixSum - k])
            if prefixSum not in indices:
                indices[prefixSum] = i
        
        return longestSubarray

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

Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

👨‍💻 Алгоритм:

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:

def floodFill(image, sr, sc, color):
    original_color = image[sr][sc]
    if original_color == color:
        return image
    
    def dfs(x, y):
        if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
            return
        image[x][y] = color
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
    
    dfs(sr, sc)
    return image

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

Задача: 384. Shuffle an Array
Сложность: medium

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

Реализуйте класс Solution:

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

👨‍💻 Алгоритм:

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.

😎 Решение:

import random

class Solution:
    def __init__(self, nums: list[int]):
        self.array = nums[:]
        self.original = nums[:]
    
    def reset(self) -> list[int]:
        self.array = self.original[:]
        return self.original
    
    def shuffle(self) -> list[int]:
        for i in range(len(self.array)):
            rand_index = random.randint(i, len(self.array) - 1)
            self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
        return self.array

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

👨‍💻 Алгоритм:

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution:
    def shiftAndCount(self, xShift, yShift, M, R):
        leftShiftCount = 0
        rightShiftCount = 0
        rRow = 0
        for mRow in range(yShift, len(M)):
            rCol = 0
            for mCol in range(xShift, len(M)):
                if M[mRow][mCol] == 1 and M[mRow][mCol] == R[rRow][rCol]:
                    leftShiftCount += 1
                if M[mRow][rCol] == 1 and M[mRow][rCol] == R[rRow][mCol]:
                    rightShiftCount += 1
                rCol += 1
            rRow += 1
        return max(leftShiftCount, rightShiftCount)

    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        maxOverlaps = 0
        for yShift in range(len(A)):
            for xShift in range(len(A)):
                maxOverlaps = max(maxOverlaps, self.shiftAndCount(xShift, yShift, A, B))
                maxOverlaps = m

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

Задача: 1441. Build an Array With Stack Operations
Сложность: medium

Вам дан целочисленный массив target и целое число n.

У вас есть пустой стек с двумя следующими операциями:

"Push": добавляет целое число на вершину стека.
"Pop": удаляет целое число с вершины стека.
Также у вас есть поток целых чисел в диапазоне [1, n].

Используйте две операции стека, чтобы сделать числа в стеке (от нижнего к верхнему) равными target. Вы должны следовать следующим правилам:

Если поток чисел не пуст, возьмите следующее целое число из потока и поместите его на вершину стека.
Если стек не пуст, извлеките целое число с вершины стека.
Если в любой момент элементы в стеке (от нижнего к верхнему) равны target, не берите новые числа из потока и не выполняйте больше операций со стеком.
Верните операции стека, необходимые для построения target согласно указанным правилам. Если существует несколько правильных ответов, верните любой из них.

Пример:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].

👨‍💻 Алгоритм:

1⃣Инициализировать пустой список ans и переменную i равной 0.

2⃣Для каждого элемента num в target:
Пока i < num - 1:
Добавить "Push" в ans.
Добавить "Pop" в ans.
Увеличить i.
Добавить "Push" в ans.
Увеличить i.

3⃣Вернуть ans.

😎 Решение:

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ans = []
        i = 0
        
        for num in target:
            while i < num - 1:
                ans.append("Push")
                ans.append("Pop")
                i += 1
            ans.append("Push")
            i += 1
        
        return ans

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

Задача: 752. Open the Lock
Сложность: medium

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

from collections import deque

def openLock(deadends, target):
    def neighbors(node):
        for i in range(4):
            x = int(node[i])
            for d in (-1, 1):
                y = (x + d) % 10
                yield node[:i] + str(y) + node[i+1:]

    dead = set(deadends)
    queue = deque([('0000', 0)])
    visited = {'0000'}
    
    while queue:
        node, steps = queue.popleft()
        if node == target:
            return steps
        if node in dead:
            continue
        for neighbor in neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, steps + 1))
    
    return -1

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

Задача: 1422. Maximum Score After Splitting a String
Сложность: easy

Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).

Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.

Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

👨‍💻 Алгоритм:

1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.

2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.

3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.

😎 Решение:

class Solution:
    def maxScore(self, s: str) -> int:
        ones = s.count('1')
        zeros = ans = 0

        for i in range(len(s) - 1):
            if s[i] == '1':
                ones -= 1
            else:
                zeros += 1
            ans = max(ans, zeros + ones)
        
        return ans

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

👨‍💻 Алгоритм:

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.

😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        parent_x, parent_y = None, None
        depth_x, depth_y = -1, -1
        
        def dfs(node, parent, depth):
            nonlocal parent_x, parent_y, depth_x, depth_y
            if not node:
                return
            if node.val == x:
                parent_x, depth_x = parent, depth
            elif node.val == y:
                parent_y, depth_y = parent, depth
            else:
                dfs(node.left, node, depth + 1)
                dfs(node.right, node, depth + 1)
        
        dfs(root, None, 0)
        return depth_x == depth_y and parent_x != parent_y

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

Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.

Пример:

Input: s = "(()"
Output: 2

👨‍💻 Алгоритм:

1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.

2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.

3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.

😎 Решение:

def is_valid(s: str) -> bool:
    stack = []
    for char in s:
        if char == '(':
            stack.append('(')
        elif stack and stack[-1] == '(':
            stack.pop()
        else:
            return False
    return len(stack) == 0

def longest_valid_parentheses(s: str) -> int:
    maxlen = 0
    for i in range(len(s)):
        for j in range(i + 2, len(s) + 1, 2):
            substring = s[i:j]
            if is_valid(substring):
                maxlen = max(maxlen, j - i)
    return maxlen

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

Задача: 238. Product of Array Except Self
Сложность: medium

Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].

Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.

Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм:

1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎 Решение:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        L = [1] * length
        R = [1] * length
        answer = [1] * length

        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        for i in range(length - 2, -1, -1):
            R[i] = nums[i + 1] * R[i + 1]

        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer

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