#hard
Задача: 273. Integer to English Words

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

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1️⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2️⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3️⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        
        def helper(n):
            if n == 0:
                return ""
            elif n < 20:
                return below_twenty[n] + " "
            elif n < 100:
                return tens[n // 10] + " " + helper(n % 10)
            else:
                return below_twenty[n // 100] + " Hundred " + helper(n % 100)
        
        below_twenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        thousands = ["", "Thousand", "Million", "Billion"]
        
        result = ""
        i = 0
        
        while num > 0:
            if num % 1000 != 0:
                result = helper(num % 1000) + thousands[i] + " " + result
            num //= 1000
            i += 1
        
        return result.strip()

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 215. Kth Largest Element in an Array

Дан целочисленный массив 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]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 216. Combination Sum III

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1️⃣ Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

2️⃣ Рекурсивная обработка:
В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов.
Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки.
Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата.

3️⃣ Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎 Решение:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                return

            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                comb.pop()

        backtrack(n, [], 0)

        return results

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 274. H-Index

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2️⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3️⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        papers = [0] * (n + 1)
        for c in citations:
            papers[min(n, c)] += 1
        k = n
        s = papers[n]
        while k > s:
            k -= 1
            s += papers[k]
        return k

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 275. H-Index II

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3️⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if citations[mid] == n - mid:
                return n - mid
            elif citations[mid] < n - mid:
                left = mid + 1
            else:
                right = mid - 1
        
        return n - left

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 217. Contains Duplicate

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

Пример:

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

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

1️⃣ Отсортируйте массив nums по возрастанию.

2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false.

😎 Решение:

def containsDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 218. The Skyline Problem

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

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат.

😎 Решение:

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        positions = sorted(list(set([x for building in buildings for x in building[:2]])))
        
        edge_index_map = {x : i for i, x in enumerate(positions)}

        heights = [0] * len(positions)
        
        for left, right, height in buildings:
            left_idx = edge_index_map[left]
            right_idx = edge_index_map[right]

            for i in range(left_idx, right_idx):
                heights[i] = max(heights[i], height)

        answer = []

        for i in range(len(heights)):
            curr_height = heights[i]
            curr_x = positions[i]

            if not answer or answer[-1][1] != curr_height:
                answer.append([curr_x, curr_height])
        return answer

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 276. Paint Fence

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

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1️⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2️⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3️⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k
        
        twoPostsBack = k
        onePostBack = k * k
        
        for i in range(3, n + 1):
            curr = (k - 1) * (onePostBack + twoPostsBack)
            twoPostsBack = onePostBack
            onePostBack = curr
        
        return onePostBack

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 219. Contains Duplicate II

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.

Пример:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

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

1️⃣ Создайте пустое множество set.

2️⃣ Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = set()
        for i, num in enumerate(nums):
            if num in seen:
                return True
            seen.add(num)
            if len(seen) > k:
                seen.remove(nums[i - k])
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 314. Binary Tree Vertical Order Traversal

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

Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.

Пример:

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

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

1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

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

😎 Решение:

from collections import defaultdict
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        columnTable = defaultdict(list)
        queue = deque([(root, 0)])

        while queue:
            node, column = queue.popleft()

            if node is not None:
                columnTable[column].append(node.val)
                
                queue.append((node.left, column - 1))
                queue.append((node.right, column + 1))
                        
        return [columnTable[x] for x in sorted(columnTable.keys())]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 315. Count of Smaller Numbers After Self

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

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

1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3️⃣Верните результат.

😎 Решение:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        def update(index, value, tree, size):
            index += size
            tree[index] += value
            while index > 1:
                index //= 2
                tree[index] = tree[index * 2] + tree[index * 2 + 1]

        def query(left, right, tree, size):
            result = 0
            left += size
            right += size
            while left < right:
                if left % 2 == 1:
                    result += tree[left]
                    left += 1
                left //= 2
                if right % 2 == 1:
                    right -= 1
                    result += tree[right]
                right //= 2
            return result

        offset = 10**4
        size = 2 * 10**4 + 1
        tree = [0] * (2 * size)
        result = []
        for num in reversed(nums):
            smaller_count = query(0, num + offset, tree, size)
            result.append(smaller_count)
            update(num + offset, 1, tree, size)
        return reversed(result)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 220. Contains Duplicate III

Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.

Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.

Верните true, если такая пара существует, или false в противном случае.

Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

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

1️⃣ Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1.
Инициализировать пустой хэш-таблицей buckets.
Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2️⃣ Итерация и проверка корзин:
Перебрать все элементы массива nums.
Для каждого элемента nums[i]:
Определить его корзину с помощью getID.
Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true.
Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true.
Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину.
Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3️⃣ Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎 Решение:

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0: return False
        buckets = {}
        w = t + 1

        for i in range(len(nums)):
            bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
            if bucket in buckets: return True
            if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
            if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
            buckets[bucket] = nums[i]
            if i >= k:
                del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
🤔 Задача: 221. Maximal Square

Дана бинарная матрица размером 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

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

#easy
🤔 Задача: 222. Count Complete Tree Nodes

Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Пример:

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

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

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

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

😎 Решение:

class Solution:
    def compute_depth(self, node: TreeNode) -> int:
        d = 0
        while node.left:
            node = node.left
            d += 1
        return d

    def exists(self, idx: int, d: int, node: TreeNode) -> bool:
        left, right = 0, 2**d - 1
        for _ in range(d):
            pivot = left + (right - left) // 2
            if idx <= pivot:
                node = node.left
                right = pivot
            else:
                node = node.right
                left = pivot + 1
        return node is not None
        
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        d = self.compute_depth(root)
        if d == 0:
            return 1
        
        left, right = 1, 2**d - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if self.exists(pivot, d, root):
                left = pivot + 1
            else:
                right = pivot - 1
        
        return (2**d - 1) + left

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

#medium
Задача: 277. Find the Celebrity

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

from functools import lru_cache

class Solution:
    
    @lru_cache(maxsize=None)
    def cachedKnows(self, a, b):
        return knows(a, b)
    
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if self.cachedKnows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if self.cachedKnows(i, j) or not self.cachedKnows(j, i):
                return False
        return True

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

#medium
Задача: 223. Rectangle Area

Даны координаты двух прямоугольных прямоугольников на двумерной плоскости, верните общую площадь, покрытую этими двумя прямоугольниками. Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2). Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

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

😎 Решение:

class Solution:
    def computeArea(self,
                    ax1: int, ay1: int,
                    ax2: int, ay2: int,
                    bx1: int, by1: int,
                    bx2: int, by2: int) -> int:
        area_of_a = (ay2 - ay1) * (ax2 - ax1)
        area_of_b = (by2 - by1) * (bx2 - bx1)

        left = max(ax1, bx1)
        right = min(ax2, bx2)
        x_overlap = right - left

        top = min(ay2, by2)
        bottom = max(ay1, by1)
        y_overlap = top - bottom

        area_of_overlap = 0
        if x_overlap > 0 and y_overlap > 0:
            area_of_overlap = x_overlap * y_overlap

        total_area = area_of_a + area_of_b - area_of_overlap

        return total_area

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

#hard
Задача: 224. Basic Calculator

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

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

class Solution:
    def evaluate_expr(self, stack):
        if not stack or type(stack[-1]) == str:
            stack.append(0)
            
        res = stack.pop()

        while stack and stack[-1] != ')':
            sign = stack.pop()
            if sign == '+':
                res += stack.pop()
            else:
                res -= stack.pop()
        return res       

    def calculate(self, s: str) -> int:
        stack = []
        n, operand = 0, 0

        for i in range(len(s) - 1, -1, -1):
            ch = s[i]

            if ch.isdigit():
                operand = (10**n * int(ch)) + operand
                n += 1

            elif ch != " ":
                if n:
                    stack.append(operand)
                    n, operand = 0, 0

                if ch == '(':         
                    res = self.evaluate_expr(stack)
                    stack.pop()        

                    stack.append(res)

                else:
                    stack.append(ch)

        if n:
            stack.append(operand)

        return self.evaluate_expr(stack)

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

#easy
Задача: 367. Valid Perfect Square

Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.

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

Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

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

1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.

2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.

3⃣Если вышли из цикла, вернуть False.

😎 Решение:

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
    if num < 2:
        return True

    x = num // 2
    while x * x > num:
        x = (x + num // x) // 2
    return x * x == num

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

#easy
Задача: 225. Implement Stack using Queues

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
        self.top_element = None

    def push(self, x: int) -> None:
        self.q2.append(x)
        self.top_element = x
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        result = self.q1.popleft()
        if self.q1:
            self.top_element = self.q1[0]
        return result

    def top(self) -> int:
        return self.top_element

    def empty(self) -> bool:
        return not self.q1

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

#easy
Задача: 226. Invert Binary Tree

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        right = self.invertTree(root.right)
        left = self.invertTree(root.left)
        root.left = right
        root.right = left
        return root

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