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

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

Пожизненный PRO доступ на easyoffer — по цене одного года!

До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.

– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)

👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro

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

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