Задача: 361. Bomb Enemy
Сложность: medium
Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

1⃣Перебрать каждую ячейку в сетке и для каждой пустой ячейки вычислить, сколько врагов можно убить, установив бомбу.

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

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

😎 Решение:

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

        rows, cols = len(grid), len(grid[0])
        max_count = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '0':
                    hits = self.killEnemies(row, col, grid)
                    max_count = max(max_count, hits)

        return max_count

    def killEnemies(self, row, col, grid):
        enemy_count = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for dr, dc in directions:
            r, c = row + dr, col + dc
            
            while 0 <= r < len(grid) and 0 <= c < len(grid[0]):
                if grid[r][c] == 'W':
                    break
                elif grid[r][c] == 'E':
                    enemy_count += 1
                r += dr
                c += dc

        return enemy_count

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

Задача: 1502. Can Make Arithmetic Progression From Sequence
Сложность: easy

Последовательность чисел называется арифметической прогрессией, если разница между любыми двумя последовательными элементами одинаковая.

Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false.

Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

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

1⃣Отсортируйте массив arr.

2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0].

3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True.

😎 Решение:

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        diff = arr[1] - arr[0]
        
        for i in range(2, len(arr)):
            if arr[i] - arr[i - 1] != diff:
                return False
        
        return True

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

Задача: 1136. Parallel Courses
Сложность: medium

Вам дано целое число n, которое указывает, что есть n курсов, обозначенных от 1 до n. Вам также дан массив relations, где relations[i] = [prevCoursei, nextCoursei], представляющий собой зависимость между курсами: курс prevCoursei должен быть пройден до курса nextCoursei.

За один семестр вы можете взять любое количество курсов, при условии, что вы прошли все необходимые предварительные курсы в предыдущем семестре для тех курсов, которые вы собираетесь взять.
Верните минимальное количество семестров, необходимых для прохождения всех курсов. Если нет способа пройти все курсы, верните -1.

Пример:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

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

1⃣Постройте направленный граф из зависимостей (relations).

2⃣Реализуйте функцию dfsCheckCycle для проверки наличия цикла в графе.

3⃣Реализуйте функцию dfsMaxPath для вычисления длины самого длинного пути в графе. Если цикл найден, верните -1. Иначе верните длину самого длинного пути.

😎 Решение:

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = [[] for _ in range(N + 1)]
        for prev, next in relations:
            graph[prev].append(next)
        
        visited = [0] * (N + 1)
        for node in range(1, N + 1):
            if self.dfsCheckCycle(node, graph, visited) == -1:
                return -1
        
        visited_length = [0] * (N + 1)
        max_length = 1
        for node in range(1, N + 1):
            length = self.dfsMaxPath(node, graph, visited_length)
            max_length = max(length, max_length)
        return max_length
    
    def dfsCheckCycle(self, node, graph, visited):
        if visited[node] != 0:
            return visited[node]
        else:
            visited[node] = -1
        for end_node in graph[node]:
            if self.dfsCheckCycle(end_node, graph, visited) == -1:
                return -1
        visited[node] = 1
        return 1

    def dfsMaxPath(self, node, graph, visited_length):
        if visited_length[node] != 0:
            return visited_length[node]
        max_length = 1
        for end_node in graph[node]:
            length = self.dfsMaxPath(end_node, graph, visited_length)
            max_length = max(length + 1, max_length)
        visited_length[node] = max_length
        return max_length

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей.

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        normalized_str = ''.join([c.lower() if c.isalnum() else ' ' for c in paragraph])
        words = normalized_str.split()
        word_count = defaultdict(int)
        banned_words = set(banned)
        
        for word in words:
            if word not in banned_words:
                word_count[word] += 1

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

Задача: 419. Battleships in a Board
Сложность: medium

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

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

1⃣Пройдите по каждой клетке матрицы.

2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

3⃣Верните итоговый счетчик.

😎 Решение:

def countBattleships(board):
    m, n = len(board), len(board[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'X':
                if (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
                    count += 1
    
    return count

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

Задача: 1394. Find Lucky Integer in an Array
Сложность: easy

Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению.

Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1.

Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

1⃣Создайте хэш-карту для подсчёта частоты каждого числа в массиве.

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

3⃣Верните наибольшее счастливое число или -1, если таких чисел нет.

😎 Решение:

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        counts = collections.Counter(arr)
        largest_lucky = -1
        
        for num, count in counts.items():
            if num == count:
                largest_lucky = max(largest_lucky, num)
                
        return largest_lucky

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution:
    def generatePossibleResults(self, a, b):
        res = [a + b, a - b, b - a, a * b]
        if a != 0:
            res.append(b / a)
        if b != 0:
            res.append(a / b)
        return res

    def checkIfResultReached(self, list):
        if len(list) == 1:
            return abs(list[0] - 24) <= 0.1

        for i in range(len(list)):
            for j in range(i + 1, len(list)):
                new_list = [list[k] for k in range(len(list)) if k != i and k != j]
                for res in self.generatePossibleResults(list[i], list[j]):
                    new_list.append(res)
                    if self.checkIfResultReached(new_list):
                        return True
                    new_list.pop()
        return False

    def judgePoint24(self, cards):
        return self.checkIfResultReached(list(map(float, cards)))

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

Задача: 87. Scramble String
Сложность: hard

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

1. Если длина строки равна 1, остановиться.
2. Если длина строки больше 1, выполнить следующее:
- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.
- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.
- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.

Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.

Пример:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

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

1️⃣- Итерируйте i от 0 до n-1.
- Итерируйте j от 0 до n-1.
- Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования).

2️⃣- Итерируйте length от 2 до n.
- Итерируйте i от 0 до n + 1 - length.
- Итерируйте j от 0 до n + 1 - length.

3️⃣- Итерируйте newLength от 1 до length - 1.
- Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true.
- Верните dp[n][0][0].

😎 Решение:

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [
            [[False for j in range(n)] for i in range(n)] for l in range(n + 1)
        ]
        for i in range(n):
            for j in range(n):
                dp[1][i][j] = s1[i] == s2[j]
        for length in range(2, n + 1):
            for i in range(n + 1 - length):
                for j in range(n + 1 - length):
                    for new_length in range(1, length):
                        dp1 = dp[new_length][i]
                        dp2 = dp[length - new_length][i + new_length]
                        dp[length][i][j] |= dp1[j] and dp2[j + new_length]
                        dp[length][i][j] |= (
                            dp1[j + length - new_length] and dp2[j]
                        )
        return dp[n][0][0]

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

Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium

Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].

Пример:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]

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

1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах.

2⃣Решите систему уравнений:
4J + 2S = tomatoSlices
J + S = cheeseSlices

3⃣Если решение существует, верните его, иначе верните пустой список.

😎 Решение:

def numOfBurgers(tomatoSlices, cheeseSlices):
    if tomatoSlices % 2 != 0 or tomatoSlices < 2 * cheeseSlices or tomatoSlices > 4 * cheeseSlices:
        return []
    total_jumbo = (tomatoSlices - 2 * cheeseSlices) // 2
    total_small = cheeseSlices - total_jumbo
    return [total_jumbo, total_small]

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

1⃣Добавьте корень в очередь.

2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь.

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

class Solution:
    def getTargetCopy(self, original, cloned, target):
        queue_o = [original]
        queue_c = [cloned]
        
        while queue_o:
            node_o = queue_o.pop(0)
            node_c = queue_c.pop(0)
            
            if node_o is target:
                return node_c
            
            if node_o.left:
                queue_o.append(node_o.left)
                queue_c.append(node_c.left)
            if node_o.right:
                queue_o.append(node_o.right)
                queue_c.append(node_c.right)
        return None

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

Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy

Вам дан массив строк words и строка chars.

Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).

Верните сумму длин всех хороших строк в words.

Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

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

1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0.

2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

3⃣Если good = true, добавьте длину слова к ans. Верните ans.

😎 Решение:

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        counts = collections.Counter(chars)
        ans = 0
        
        for word in words:
            wordCount = collections.Counter(word)
            good = True
            for c, freq in wordCount.items():
                if counts[c] < freq:
                    good = False
                    break
            
            if good:
                ans += len(word)
        
        return ans

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

Задача: 359. Logger Rate Limiter
Сложность: easy

Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10).
Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время.

Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.

Пример:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

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

1⃣Инициализируем хеш-таблицу/словарь для хранения сообщений вместе с временной меткой.

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

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

😎 Решение:

class Logger:
    def __init__(self):
        self.msg_dict = {}

    def should_print_message(self, timestamp: int, message: str) -> bool:
        if message not in self.msg_dict or timestamp - self.msg_dict[message] >= 10:
            self.msg_dict[message] = timestamp
            return True
        return False

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

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

Пример:

Input: s = "bcabc"
Output: "abc"

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

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

2⃣Итерация по строке
На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок.

3⃣Удаление символов
Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека.

😎 Решение:

class Solution:
    def removeDuplicateLetters(self, s) -> str:
        stack = []
        seen = set()
        last_occurrence = {c: i for i, c in enumerate(s)}

        for i, c in enumerate(s):
            if c not in seen:
                while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
        return ''.join(stack)

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

Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1.

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

1⃣Инициализация очереди и подсчет апельсинов:
Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов.
Если нет свежих апельсинов, верните 0.

2⃣Использование BFS для распространения гнили:
Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь.
Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов.
Если свежих апельсинов больше не осталось, верните текущее количество минут.

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = deque()
        fresh_count = 0
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh_count += 1
        
        if fresh_count == 0:
            return 0
        
        minutes = 0
        while queue:
            for _ in range(len(queue)):
                i, j = queue.popleft()
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and grid[ni][nj] == 1:
                        grid[ni][nj] = 2
                        fresh_count -= 1
                        queue.append((ni, nj))
            if queue:
                minutes += 1
        
        return minutes if fresh_count == 0 else -1

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

Задача: 39. Combination Sum
Сложность: medium

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

Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается.

Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.

Пример:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

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

1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎 Решение:

class Solution:
    def combinationSum(self, candidates, target):
        results = []

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

            for i in range(start, len(candidates)):
                comb.append(candidates[i])
                backtrack(remain - candidates[i], comb, i)
                comb.pop()

        backtrack(target, [], 0)

        return results

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

Задача: 861. Score After Flipping Matrix
Сложность: hard

Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1], k = 1
Output: 1

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

1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались.

2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались.

3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека.

😎 Решение:

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        N = len(A)
        P = [0] * (N + 1)
        for i in range(N):
            P[i+1] = P[i] + A[i]

        ans = N + 1
        monoq = deque()

        for y in range(len(P)):
            while monoq and P[y] <= P[monoq[-1]]:
                monoq.pop()
            while monoq and P[y] >= P[monoq[0]] + K:
                ans = min(ans, y - monoq.popleft())
            monoq.append(y)

        return ans if ans < N + 1 else -1

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

Задача: 256. Paint House
Сложность: medium

Есть ряд из 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])

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

def treeDiameter(edges):
    if not edges:
        return 0

    from collections import defaultdict

    def dfs(node, parent):
        max_depth = 0
        for neighbor in graph[node]:
            if neighbor != parent:
                depth = dfs(neighbor, node)
                if depth + 1 > max_depth:
                    max_depth = depth + 1
                    farthest_node[0] = neighbor
        return max_depth

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    farthest_node = [0]
    dfs(0, -1)
    start_node = farthest_node[0]

    farthest_node = [0]
    diameter = dfs(start_node, -1)

    return diameter

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

Задача: 929. Unique Email Addresses
Сложность: easy

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: emails = ["[email protected]","[email protected]","[email protected]"]
Output: 2

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

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

2⃣Для каждого адреса в emails:
Разделить адрес на локальное и доменное имя по символу '@'.
Обработать локальное имя:
Удалить все точки '.'.
Обрезать часть после символа '+'.
Объединить обработанное локальное имя и доменное имя.
Добавить результат в множество уникальных адресов.

3⃣Вернуть количество уникальных адресов в множестве.

😎 Решение:

def numUniqueEmails(emails):
    unique_emails = set()
    for email in emails:
        local, domain = email.split('@')
        local = local.split('+')[0].replace('.', '')
        unique_emails.add(f"{local}@{domain}")
    return len(unique_emails)

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