Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

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

Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

1⃣Проверяем, равны ли оба узла None, если да — возвращаем True

2⃣Если один из узлов None или значения узлов разные — возвращаем False

3⃣Рекурсивно проверяем левое и правое поддеревья

😎 Решение:

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and self.isSameTree(
            p.left, q.left
        )

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

Задача: 215. Kth Largest Element in an Array
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.

Пример:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

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

1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3️⃣ Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

class Solution:
    def findKthLargest(self, nums, k):
        nums.sort(reverse=True)
        return nums[k - 1]

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

Задача: 152. Maximum Product Subarray
Сложность: Medium

Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.

Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

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

1️⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.

2️⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.

3️⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.

😎 Решение:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        result = nums[0]

        for i in range(len(nums)):
            accu = 1
            for j in range(i, len(nums)):
                accu *= nums[j]
                result = max(result, accu)

        return result

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

Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

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

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

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

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

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

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎 Решение:

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        parents = [0] * n
        
        for i in range(n):
            if leftChild[i] != -1:
                parents[leftChild[i]] += 1
                if parents[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                parents[rightChild[i]] += 1
                if parents[rightChild[i]] > 1:
                    return False
        
        root = -1
        for i in range(n):
            if parents[i] == 0:
                if root == -1:
                    root = i
                else:
                    return False
        
        if root == -1:
            return False
        
        visited = set()
        queue = [root]
        
        while queue:
            node = queue.pop(0)
            if node in visited:
                return False
            visited.add(node)
            if leftChild[node] != -1:
                queue.append(leftChild[node])
            if rightChild[node] != -1:
                queue.append(rightChild[node])
        
        return len(visited) == n

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

Задача: №45. Jump Game II
Сложность: medium

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Возвращает минимальное количество переходов для достижения nums[n - 1].

Пример:

Input: nums = [2,3,1,1,4]  
Output: 2  

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

1️⃣Используем BFS-подход с отслеживанием границ уровня.

2️⃣На каждой итерации обновляем самую дальнюю достижимую позицию.

3️⃣Когда текущий уровень заканчивается, увеличиваем счетчик прыжков и переходим на новый уровень.

😎 Решение:

class Solution:
    def jump(self, nums):
        jumps = 0
        farthest = 0
        current_end = 0
        
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = farthest
        
        return jumps

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

Задача: 1060. Missing Element in Sorted Array
Сложность: medium

Если задан целочисленный массив nums, который отсортирован по возрастанию и все его элементы уникальны, а также задано целое число k, верните k-е недостающее число, начиная с самого левого номера массива.

Пример:

Input: nums = [4,7,9,10], k = 1
Output: 5

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

1⃣Инициализация переменных:
Задать счетчик недостающих чисел и текущее значение, которое будет проверяться на отсутствие в массиве.
Установить указатель для обхода массива.

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

3⃣Возвращение результата:
Вернуть k-е недостающее число после нахождения его.

😎 Решение:

def findKthMissing(nums, k):
    missing_count = 0
    current = nums[0]
    index = 0
    
    while True:
        if index < len(nums) and nums[index] == current:
            index += 1
        else:
            missing_count += 1
            if missing_count == k:
                return current
        current += 1

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

Задача: 541. Reverse String II
Сложность: easy

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

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        a = list(s)
        for start in range(0, len(a), 2 * k):
            i, j = start, min(start + k - 1, len(a) - 1)
            while i < j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        return ''.join(a)

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        
        counts = []
        current_run = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i - 1]:
                current_run += 1
                continue
            counts.append(current_run)
            current_run = 1
        counts.append(current_run)
        
        counts.sort(reverse=True)
        
        numbers_removed_from_arr = 0
        set_size = 0
        for count in counts:
            numbers_removed_from_arr += count
            set_size += 1   
            if numbers_removed_from_arr >= len(arr) // 2:
                break
        
        return set_size

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

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

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        ans = 0
        st = []
        
        for i in range(len(nums)):
            while st and nums[i] < nums[st[-1]]:
                ans += (i - st.pop())
            st.append(i)
        
        while st:
            ans += (len(nums) - st.pop())
        
        return ans

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

Задача: 1538. Guess the Majority in a Hidden Array
Сложность: medium

У нас есть целочисленный массив nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает:
4: если значения всех 4 элементов одинаковы (0 или 1).
2: если три элемента имеют значение 0 и один элемент имеет значение 1 или наоборот.
0: если два элемента имеют значение 0 и два элемента имеют значение 1.

int length(): Возвращает размер массива.

Вам разрешено вызывать query() не более 2 * n раз, где n равно ArrayReader.length().

Верните любой индекс самого частого значения в nums, в случае ничьей верните -1.

Пример:

Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.

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

1⃣Получите n вызовом функции length. Объявите и инициализируйте переменные cntEqual = 1, cntDiffer = 0, indexDiffer = -1. Вызовите query(0, 1, 2, 3) и сохраните результат в переменной query0123. Вызовите query(1, 2, 3, 4) и сохраните результат в переменной query1234. Если query1234 равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 4.

2⃣Итерация от i = 5 до n-1. Если значение query(1, 2, 3, i) равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = i. Дополнительные проверки для первых элементов: если query(0, 2, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 1. Если query(0, 1, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 2. Если query(0, 1, 2, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 3.

3⃣Если cntEqual > cntDiffer, верните 0. Если cntDiffer > cntEqual, верните indexDiffer. Верните -1.

😎 Решение:

class Solution:
    def __init__(self):
        self.cntEqual = 1
        self.cntDiffer = 0
        self.indexDiffer = -1

    def f(self, equal, i):
        if equal:
            self.cntEqual += 1
        else:
            self.cntDiffer += 1
            self.indexDiffer = i

    def guessMajority(self, reader: 'ArrayReader') -> int:
        n = reader.length()
        query0123 = reader.query(0, 1, 2, 3)
        query1234 = reader.query(1, 2, 3, 4)
        self.f(query1234 == query0123, 4)
        for i in range(5, n):
            self.f(reader.query(1, 2, 3, i) == query0123, i)
        self.f(reader.query(0, 2, 3, 4) == query1234, 1)
        self.f(reader.query(0, 1, 3, 4) == query1234, 2)
        self.f(reader.query(0, 1, 2, 4) == query1234, 3)
        return 0 if self.cntEqual > self.cntDiffer else self.indexDiffer if self.cntDiffer > self.cntEqual else -1

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

Задача: 901. Online Stock Span
Сложность: medium

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

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.

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

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

class StockSpanner:
    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

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

Задача: 1423. Maximum Points You Can Obtain from Cards
Сложность: medium

Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.

Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.

Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

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

1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.

2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.

3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.

😎 Решение:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        frontSetOfCards = [0] * (k + 1)
        rearSetOfCards = [0] * (k + 1)
        
        for i in range(k):
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
        
        maxScore = 0
        for i in range(k + 1):
            currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
            maxScore = max(maxScore, currentScore)
        
        return maxScore

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

Задача: 1470. Shuffle the Array
Сложность: easy

Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].

Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].

Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

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

1⃣Создайте массив result размером 2 * n.

2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.

3⃣Верните массив result.

😎 Решение:

class Solution:
    def shuffle(self, nums, n):
        result = [0] * (2 * n)
        for i in range(n):
            result[2 * i] = nums[i]
            result[2 * i + 1] = nums[n + i]
        return result

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1️⃣Сдвигать left и right вправо, пока они не станут равными.

2️⃣Подсчитать количество сдвигов.

3️⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0
        while m < n:
            m = m >> 1
            n = n >> 1
            shift += 1
        return m << shift

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

Задача: 1424. Diagonal Traverse II
Сложность: medium

Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

from collections import deque

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        queue = deque([(0, 0)])
        ans = []
        
        while queue:
            row, col = queue.popleft()
            ans.append(nums[row][col])
            
            if col == 0 and row + 1 < len(nums):
                queue.append((row + 1, col))
                
            if col + 1 < len(nums[row]):
                queue.append((row, col + 1))
                
        return ans

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

Задача: 953. Verifying an Alien Dictionary
Сложность: hard

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

Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

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

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

2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.

3⃣Если все слова отсортированы правильно, вернуть true.

😎 Решение:

def isAlienSorted(words, order):
    order_map = {char: i for i, char in enumerate(order)}
    
    def compare(word1, word2):
        for c1, c2 in zip(word1, word2):
            if order_map[c1] < order_map[c2]:
                return True
            elif order_map[c1] > order_map[c2]:
                return False
        return len(word1) <= len(word2)
    
    for i in range(len(words) - 1):
        if not compare(words[i], words[i + 1]):
            return False
    return True

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

Задача: 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

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

Задача: 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

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

Задача: 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

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