Задача: 27. Remove Element
Сложность: easy

Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val как k. Чтобы вас приняли, вам необходимо сделать следующее:

- Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
- Вернуть k.

Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2, nums = [2,2,_,_]  

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

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

2️⃣Проходим по массиву, копируя элементы, которые не равны val, на место указателя k.

3️⃣Возвращаем k — количество элементов, не равных val.

😎 Решение:

class Solution:  
    def removeElement(self, nums: List[int], val: int) -> int:  
        k = 0  

        for i in range(len(nums)):  
            if nums[i] != val:  
                nums[k] = nums[i]  
                k += 1  

        return k

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

Задача: 1463. Cherry Pickup II
Сложность: hard

Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).

У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).

Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.

Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

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

1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).

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

3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.

😎 Решение:

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[0] * n for _ in range(n)] for _ in range(m)]
        
        for row in range(m - 1, -1, -1):
            for col1 in range(n):
                for col2 in range(n):
                    result = grid[row][col1]
                    if col1 != col2:
                        result += grid[row][col2]
                    if row != m - 1:
                        max_cherries = 0
                        for new_col1 in range(col1 - 1, col1 + 2):
                            for new_col2 in range(col2 - 1, col2 + 2):
                                if 0 <= new_col1 < n and 0 <= new_col2 < n:
                                    max_cherries = max(max_cherries, dp[row + 1][new_col1][new_col2])
                        result += max_cherries
                    dp[row][col1][col2] = result
        return dp[0][0][n - 1]

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

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

Пример:

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

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

1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2️⃣Для данной задачи подойдет несколько способов.

3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

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

Задача: 352. Data Stream as Disjoint Intervals
Сложность: hard

Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов.

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

SummaryRanges() Инициализирует объект с пустым потоком.
void addNum(int value) Добавляет целое число в поток.
int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti.

Пример:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

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

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

2⃣addNum(int value)
Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм.

3⃣getIntervals
Если values пуст, вернуть пустой массив.
Создать пустой список интервалов.
Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу.
Итерировать по values. На каждой итерации:
Если left < 0, установить left = right = value.
Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал.
Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала.
Вставить [left, right] в intervals и вернуть intervals.

😎 Решение:

class SummaryRanges:
    def __init__(self):
        self.values = set()

    def addNum(self, value: int) -> None:
        self.values.add(value)

    def getIntervals(self) -> list[list[int]]:
        if not self.values:
            return []
        intervals = []
        sorted_values = sorted(self.values)
        left, right = -1, -1
        for value in sorted_values:
            if left < 0:
                left, right = value, value
            elif value == right + 1:
                right = value
            else:
                intervals.append([left, right])
                left, right = value, value
        intervals.append([left, right])
        return intervals

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

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

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution:
    def __init__(self):
        self.maxTime = float('-inf')
    
    def DFS(self, adjList, informTime, curr, time):
        self.maxTime = max(self.maxTime, time)
        for adjacent in adjList[curr]:
            self.DFS(adjList, informTime, adjacent, time + informTime[curr])
    
    def numOfMinutes(self, n, headID, manager, informTime):
        adjList = [[] for _ in range(n)]
        for i in range(n):
            if manager[i] != -1:
                adjList[manager[i]].append(i)
        self.DFS(adjList, informTime, headID, 0)
        return self.maxTime

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

Задача: 233. Number of Digit One
Сложность: hard

Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

def countDigitOne(n: int) -> int:
    countr = 0
    i = 1
    while i <= n:
        divider = i * 10
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr

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

Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium

Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.

Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

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

1⃣Инициализируйте две строки матрицы длины n с нулями.

2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.

3⃣Проверьте, что остатки upper и lower равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎 Решение:

def reconstructMatrix(upper, lower, colsum):
    n = len(colsum)
    top = [0] * n
    bottom = [0] * n
    
    for i in range(n):
        if colsum[i] == 2:
            if upper > 0 and lower > 0:
                top[i] = 1
                bottom[i] = 1
                upper -= 1
                lower -= 1
            else:
                return []
    
    for i in range(n):
        if colsum[i] == 1:
            if upper > lower:
                if upper > 0:
                    top[i] = 1
                    upper -= 1
                else:
                    return []
            else:
                if lower > 0:
                    bottom[i] = 1
                    lower -= 1
                else:
                    return []

    if upper == 0 and lower == 0:
        return [top, bottom]
    else:
        return []

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

Задача: 490. The Maze
Сложность: medium

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

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

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

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

1⃣Инициализация и подготовка данных
Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции.

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

3⃣Результат
Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false.

😎 Решение:

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        def dfs(m, n, maze, curr, destination, visit):
            if visit[curr[0]][curr[1]]:
                return False
            if curr == destination:
                return True
            visit[curr[0]][curr[1]] = True
            for dx, dy in directions:
                r, c = curr
                while 0 <= r < m and 0 <= c < n and maze[r][c] == 0:
                    r += dx
                    c += dy
                if dfs(m, n, maze, [r - dx, c - dy], destination, visit):
                    return True
            return False

        m, n = len(maze), len(maze[0])
        visit = [[False] * n for _ in range(m)]
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        return dfs(m, n, maze, start, destination, visit)

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

Задача: 159. Longest Substring with At Most Two Distinct Characters
Сложность: medium

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

Пример:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

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

1️⃣Возвратить N, если длина строки N меньше 3. Установить оба указателя в начало строки left = 0 и right = 0 и инициализировать максимальную длину подстроки max_len = 2.

2️⃣Пока указатель right меньше N:
Если в хэшмапе меньше 3 различных символов, добавить текущий символ s[right] в хэшмап и переместить указатель right вправо.
Если в хэшмапе 3 различных символа, удалить самый левый символ из хэшмапа и переместить указатель left, чтобы скользящее окно содержало только 2 различных символа.

3️⃣Обновить max_len.

😎 Решение:

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        if n < 3:
            return n

        left, right = 0, 0
        hashmap = defaultdict()

        max_len = 2

        while right < n:
            hashmap[s[right]] = right
            right += 1

            if len(hashmap) == 3:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx + 1

            max_len = max(max_len, right - left)

        return max_len

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

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

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

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

😎 Решение:

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

class Solution:
    def longestZigZag(self, root: TreeNode) -> int:
        self.max_length = 0
        
        def dfs(node, is_left, length):
            if not node:
                return
            self.max_length = max(self.max_length, length)
            if is_left:
                dfs(node.left, False, length + 1)
                dfs(node.right, True, 1)
            else:
                dfs(node.right, True, length + 1)
                dfs(node.left, False, 1)
        
        dfs(root, True, 0)
        dfs(root, False, 0)
        
        return self.max_length

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

Задача: 148. Sort List
Сложность: Medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

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

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

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

2️⃣Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3️⃣Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        mid = self.getMid(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)

    def merge(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummyHead = ListNode(0)
        tail = dummyHead
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 if list1 else list2
        return dummyHead.next

    def getMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
        midPrev = None
        while head and head.next:
            midPrev = head if not midPrev else midPrev.next
            head = head.next.next
        mid = midPrev.next
        midPrev.next = None
        return mid

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

Задача: 274. H-Index
Сложность: medium

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

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

2⃣Поиск первой и второй части:
Итерируйте по массиву и ищите первую часть с суммой, равной одной трети от общей суммы. Продолжайте итерацию для поиска второй части с такой же суммой.
Убедитесь, что между первой и второй частью есть хотя бы один элемент.

3⃣Проверка третьей части:
Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎 Решение:

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total_sum = sum(arr)
        if total_sum % 3 != 0:
            return False
        
        target = total_sum // 3
        part_sum, count, n = 0, 0, len(arr)
        
        for i in range(n):
            part_sum += arr[i]
            if part_sum == target:
                count += 1
                part_sum = 0
                if count == 2 and i < n - 1:
                    return True
        
        return False

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

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

😎 Решение:

class WordFilter:
    def __init__(self, words):
        self.prefix_suffix_map = {}
        for index, word in enumerate(words):
            length = len(word)
            for prefix_length in range(1, length + 1):
                for suffix_length in range(1, length + 1):
                    key = word[:prefix_length] + '#' + word[-suffix_length:]
                    self.prefix_suffix_map[key] = index
    
    def f(self, pref, suff):
        key = pref + '#' + suff
        return self.prefix_suffix_map.get(key, -1)

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

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

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

Задача: 31. Next Permutation
Сложность: medium

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

Например, для arr = [1,2,3] следующие являются всеми перестановками arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Более формально, если все перестановки массива отсортированы в одном контейнере по лексикографическому порядку, то следующая перестановка этого массива — это перестановка, следующая за ней в отсортированном контейнере. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (то есть отсортирован по возрастанию).

Например, следующая перестановка arr = [1,2,3] — это [1,3,2].
Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2].
В то время как следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет лексикографически большего переупорядочивания.

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

Замена должна быть выполнена на месте и использовать только постоянную дополнительную память.

Пример:

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

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

1️⃣Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное число на индексе i−1. Однако текущая перестановка ещё не является той перестановкой, которую мы ищем. Нам нужна наименьшая перестановка, которая может быть сформирована с использованием чисел только справа от a[i−1]. Следовательно, нам нужно расположить эти числа в порядке возрастания, чтобы получить их наименьшую перестановку.

2️⃣Однако, вспомните, что, сканируя числа справа налево, мы просто уменьшали индекс, пока не нашли пару a[i] и a[i−1], где a[i] > a[i−1]. Таким образом, все числа справа от a[i−1] уже были отсортированы в порядке убывания. Более того, обмен местами a[i−1] и a[j] не изменил этот порядок.

3️⃣Поэтому нам просто нужно перевернуть числа, следующие за a[i−1], чтобы получить следующую наименьшую лексикографическую перестановку.

😎 Решение:

class Solution:
    def nextPermutation(self, nums):
        i = len(nums) - 2
        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            self.swap(nums, i, j)
        self.reverse(nums, i + 1)

    def reverse(self, nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            self.swap(nums, i, j)
            i += 1
            j -= 1

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

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

Задача: 757. Set Intersection Size At Least Two
Сложность: hard

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

1⃣Отсортируйте интервалы по их конечным точкам.

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

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

😎 Решение:

def minSetSize(intervals):
    intervals.sort(key=lambda x: x[1])
    nums = []
    for start, end in intervals:
        if not nums or nums[-1] < start:
            nums.append(end - 1)
            nums.append(end)
        elif nums[-1] == end - 1:
            nums.append(end)
    return len(nums)

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

Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1️⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

2️⃣Перевернуть каждое слово: пройти по всей строке, идентифицировать границы каждого слова и использовать функцию reverse для переворачивания символов в пределах каждого слова.

3️⃣Окончательная корректировка: проверить, чтобы между словами оставался только один пробел, и удалить лишние пробелы в начале и конце строки, если это необходимо.

😎 Решение:

class Solution:
    def reverse(self, l: List[str], left: int, right: int) -> None:
        while left < right:
            l[left], l[right] = l[right], l[left]
            left, right = left + 1, right - 1

    def reverse_each_word(self, l: List[str]) -> None:
        n = len(l)
        start = end = 0

        while start < n:
            while end < n and l[end] != ' ':
                end += 1
            self.reverse(l, start, end - 1)
            start = end + 1
            end += 1
            
    def reverseWords(self, s: List[str]) -> None:
        self.reverse(s, 0, len(s) - 1)
        self.reverse_each_word(s)

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

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

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

Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

class Solution:
    def sortTransformedArray(self, nums, a, b, c):
        transformed = [a * x * x + b * x + c for x in nums]
        self.radix_sort(transformed)
        return transformed

    def radix_sort(self, array):
        max_element = max(abs(num) for num in array)
        place_value = 1

        while max_element // place_value > 0:
            self.counting_sort_by_digit(array, place_value)
            place_value *= 10

        negatives = sorted([x for x in array if x < 0])
        positives = sorted([x for x in array if x >= 0])
        array[:] = negatives + positives

    def counting_sort_by_digit(self, array, place_value):
        output = [0] * len(array)
        count = [0] * 10

        for num in array:
            digit = (abs(num) // place_value) % 10
            count[digit] += 1

        for i in range(1, 10):
            count[i] += count[i - 1]

        for num in reversed(array):
            digit = (abs(num) // place_value) % 10
            output[count[digit] - 1] = num
            count[digit] -= 1

        array[:] = output

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