#medium
Задача: 505. The Maze II

В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.

Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.

Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).

Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

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: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

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

1⃣Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.

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

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

😎 Решение:

from collections import deque

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        distance = [[float('inf')] * n for _ in range(m)]
        distance[start[0]][start[1]] = 0
        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        queue = deque([start])
        
        while queue:
            s = queue.popleft()
            for dx, dy in directions:
                x, y, count = s[0] + dx, s[1] + dy, 0
                
                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
                    x += dx
                    y += dy
                    count += 1
                
                x -= dx
                y -= dy
                
                if distance[s[0]][s[1]] + count < distance[x][y]:
                    distance[x][y] = distance[s[0]][s[1]] + count
                    queue.append([x, y])
        
        return -1 if distance[destination[0]][destination[1]] == float('inf') else distance[destination[0]][destination[1]]

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

#medium
Задача: 508. Most Frequent Subtree Sum

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

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

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

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

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

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

class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        from collections import defaultdict
        
        sumFreq = defaultdict(int)
        maxFreq = 0
        
        def subtreeSum(node):
            nonlocal maxFreq
            if not node:
                return 0
            leftSum = subtreeSum(node.left)
            rightSum = subtreeSum(node.right)
            currSum = node.val + leftSum + rightSum
            sumFreq[currSum] += 1
            maxFreq = max(maxFreq, sumFreq[currSum])
            return currSum
        
        subtreeSum(root)
        return [s for s in sumFreq if sumFreq[s] == maxFreq]

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

#medium
Задача: 340. Longest Substring with At Most K Distinct Characters

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

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

😎 Решение:

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        left = 0
        right = 0
        char_count = {}
        max_length = 0
        
        while right < len(s):
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            while len(char_count) > k:
                char_count[s[left]] -= 1
                if char_count[s[left]] == 0:
                    del char_count[s[left]]
                left += 1
            max_length = max(max_length, right - left + 1)
            right += 1
        
        return max_length

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

#medium
Задача: 510. Inorder Successor in BST II

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

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

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

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

class Solution:
    def inorderSuccessor(self, x: 'Node') -> 'Node':
        if x.right:
            x = x.right
            while x.left:
                x = x.left
            return x

        while x.parent and x == x.parent.right:
            x = x.parent
        return x.parent

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

#medium
Задача: 725. Split Linked List in Parts

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

1⃣Определите общую длину связного списка.

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

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def splitListToParts(head, k):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    part_length = length // k
    extra_parts = length % k

    parts = []
    node = head
    for i in range(k):
        part_head = node
        part_size = part_length + (1 if i < extra_parts else 0)
        for j in range(part_size - 1):
            if node:
                node = node.next
        if node:
            next_part = node.next
            node.next = None
            node = next_part
        parts.append(part_head)

    return parts

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

#medium
Задача: 341. Flatten Nested List Iterator

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки.

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

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        self._flatten(nestedList)
    
    def _flatten(self, nestedList):
        for ni in reversed(nestedList):
            self.stack.append(ni)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            self._flatten(self.stack.pop().getList())
        return bool(self.stack)

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

#medium
Задача: 729. My Calendar I

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

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

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

3⃣Если новое событие не пересекается с существующими событиями, добавьте его в список событий и верните true. В противном случае верните false.

😎 Решение:

class MyCalendar:

    def __init__(self):
        self.events = []

    def book(self, start, end):
        for s, e in self.events:
            if start < e and end > s:
                return false
        self.events.append((start, end))
        return true

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

#medium
Задача: 731. My Calendar II

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

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

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

😎 Решение:

class MyCalendarTwo:
    def __init__(self):
        self.events = []
        self.overlaps = []

    def book(self, start, end):
        for os, oe in self.overlaps:
            if start < oe and end > os:
                return False
        for es, ee in self.events:
            if start < ee and end > es:
                self.overlaps.append((max(start, es), min(end, ee)))
        self.events.append((start, end))
        return True

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

#medium
Задача: 735. Asteroid Collision

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

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

2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.

3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎 Решение:

def asteroidCollision(asteroids):
    stack = []
    
    for asteroid in asteroids:
        while stack and asteroid < 0 < stack[-1]:
            if stack[-1] < -asteroid:
                stack.pop()
                continue
            elif stack[-1] == -asteroid:
                stack.pop()
            break
        else:
            stack.append(asteroid)
    
    return stack

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

#medium
Задача: 737. Sentence Similarity II

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    
    graph = {}
    for x, y in similarPairs:
        if x not in graph:
            graph[x] = []
        if y not in graph:
            graph[y] = []
        graph[x].append(y)
        graph[y].append(x)
    
    def dfs(word1, word2, visited):
        if word1 == word2:
            return True
        visited.add(word1)
        for neighbor in graph.get(word1, []):
            if neighbor not in visited and dfs(neighbor, word2, visited):
                return True
        return False
    
    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and not dfs(w1, w2, set()):
            return False
    
    return True

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