Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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

def findTarget(root, k):
    def find(node, k, seen):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return find(node.left, k, seen) or find(node.right, k, seen)
    
    return find(root, k, set())

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

def atMostNGivenDigitSet(digits, n):
    n_str = str(n)
    n_len = len(n_str)
    digits = sorted(digits)
    
    def count_less_than_equal(prefix, digits, n_str):
        if len(prefix) == len(n_str):
            return 1 if prefix <= n_str else 0
        
        total = 0
        for d in digits:
            if prefix + d <= n_str[:len(prefix) + 1]:
                total += count_less_than_equal(prefix + d, digits, n_str)
            else:
                break
        return total

    total_count = 0
    for i in range(1, n_len):
        total_count += len(digits) ** i

    total_count += count_less_than_equal("", digits, n_str)
    
    return total_count

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

Задача: 221. Maximal Square
Сложность: medium

Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

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

1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.

2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

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

😎 Решение:

class Solution:
    def maximalSquare(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0
        dp = [0] * (cols + 1)
        maxsqlen = 0
        prev = 0
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                temp = dp[j]
                if matrix[i - 1][j - 1] == "1":
                    dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1
                    maxsqlen = max(maxsqlen, dp[j])
                else:
                    dp[j] = 0
                prev = temp
        return maxsqlen * maxsqlen

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

Задача: 362. Design Hit Counter
Сложность: medium

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

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

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

3⃣Верните размер очереди как количество попаданий за последние 5 минут.

😎 Решение:

from collections import deque

class HitCounter:
    def __init__(self):
        self.hits = deque()

    def hit(self, timestamp: int) -> None:
        self.hits.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        while self.hits and timestamp - self.hits[0] >= 300:
            self.hits.popleft()
        return len(self.hits)

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

Задача: 242. Valid Anagram
Сложность: easy

Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.

Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1️⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2️⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3️⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for char in s:
        count[ord(char) - ord('a')] += 1
    for char in t:
        count[ord(char) - ord('a')] -= 1
        if count[ord(char) - ord('a')] < 0:
            return False
    return True

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

Задача: 285. Inorder Successor in BST
Сложность: medium

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.

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

Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

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

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

2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.

3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎 Решение:

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

class Solution:
    def __init__(self):
        self.previous = None
        self.inorderSuccessorNode = None

    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        if p.right:
            leftmost = p.right
            while leftmost.left:
                leftmost = leftmost.left
            self.inorderSuccessorNode = leftmost
        else:
            self.inorderCase2(root, p)
        return self.inorderSuccessorNode

    def inorderCase2(self, node: TreeNode, p: TreeNode):
        if not node:
            return

        self.inorderCase2(node.left, p)

        if self.previous == p and self.inorderSuccessorNode is None:
            self.inorderSuccessorNode = node
            return

        self.previous = node

        self.inorderCase2(node.right, p)

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями. Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path
Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited.

3⃣Возврат результата
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        moves = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
        visited = {(0, 0)}
        x = y = 0
        
        for c in path:
            dx, dy = moves[c]
            x += dx
            y += dy
            if (x, y) in visited:
                return True
            visited.add((x, y))
        
        return False

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

Задача: 404. Sum of Left Leaves
Сложность: easy

Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

1⃣Рекурсивный обход дерева
Обходите дерево с помощью рекурсивной функции, которая принимает текущий узел и флаг, указывающий, является ли узел левым ребенком.

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

3⃣Рекурсивный вызов для детей
Рекурсивно вызовите функцию для левого и правого детей текущего узла, передавая соответствующий флаг.

😎 Решение:

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        def dfs(node, is_left):
            if not node:
                return 0
            if not node.left and not node.right:
                return node.val if is_left else 0
            return dfs(node.left, True) + dfs(node.right, False)
        
        return dfs(root, False)

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

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

1⃣Инициализация и вычисление:
Создайте переменную x для хранения текущего числа в десятичной системе.
Создайте пустой массив answer для хранения результатов делимости на 5.

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        x = 0
        answer = []
        for num in nums:
            x = (x * 2 + num) % 5
            answer.append(x == 0)
        return answer

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

Задача: 535. Encode and Decode TinyURL
Сложность: medium

Спроектируйте класс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

import random
import string

class Codec:
    def __init__(self):
        self.alphabet = string.ascii_letters + string.digits
        self.map = {}
        self.key = self.get_rand()

    def get_rand(self):
        return ''.join(random.choice(self.alphabet) for _ in range(6))

    def encode(self, longUrl: str) -> str:
        while self.key in self.map:
            self.key = self.get_rand()
        self.map[self.key] = longUrl
        return "https://tinyurl.com/" + self.key

    def decode(self, shortUrl: str) -> str:
        key = shortUrl.replace("https://tinyurl.com/", "")
        return self.map.get(key, "")

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

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

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        count = k
        for num in nums:
            if num == 1:
                if count < k:
                    return False
                count = 0
            else:
                count += 1
        return True

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