Задача: 373. Find K Pairs with Smallest Sums
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.

Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.

Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.

Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

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

1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.

2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.

3⃣Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.

😎 Решение:

import heapq

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        ans = []
        visited = set()
        minHeap = [(nums1[0] + nums2[0], 0, 0)]
        visited.add((0, 0))

        while k > 0 and minHeap:
            sum_val, i, j = heapq.heappop(minHeap)
            ans.append([nums1[i], nums2[j]])
            if i + 1 < m and (i + 1, j) not in visited:
                heapq.heappush(minHeap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
            k -= 1

        return ans

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

Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.

2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = index
                    ans += dfs(nr, nc, index)
            return ans

        def neighbors(r, c):
            for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc

        N = len(grid)
        index = 2
        area = [0] * (N * N + 2)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    ans = max(a

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

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

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

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

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

1⃣Постройте карту. Для каждого слова в списке words:
Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1.

2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

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

😎 Решение:

class Solution:
    def bitmask(self, word: str) -> int:
        mask = 0
        for letter in word:
            mask |= 1 << (ord(letter) - ord('a'))
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_count = {}
        for word in words:
            mask = self.bitmask(word)
            word_count[mask] = word_count.get(mask, 0) + 1

        result = []
        for puzzle in puzzles:
            first = 1 << (ord(puzzle[0]) - ord('a'))
            count = word_count.get(first, 0)
            mask = self.bitmask(puzzle[1:])
            submask = mask
            while submask > 0:
                count += word_count.get(submask | first, 0)
                submask = (submask - 1) & mask
            result.append(count)
        return result

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

Задача: 26. Remove Duplicates from Sorted Array
Сложность: easy

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

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

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

Пример:

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

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

1️⃣Используем два указателя: один для уникальных элементов, другой для прохода по массиву.

2️⃣Перебираем массив, добавляя уникальные элементы на место.

3️⃣Возвращаем количество уникальных элементов.

😎 Решение:

from typing import List  

class Solution:  
    def removeDuplicates(self, nums: List[int]) -> int:  
        i = 0    
        while i < len(nums) - 1:     
            if nums[i] == nums[i + 1]:  
                nums.pop(i + 1)     
            else:  
                i += 1    

        return len(nums)

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

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

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

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

class Solution:
    def __init__(self):
        self.isTravelNeeded = set()
    
    def solve(self, dp, days, costs, currDay):
        if currDay > days[-1]:
            return 0
        
        if currDay not in self.isTravelNeeded:
            return self.solve(dp, days, costs, currDay + 1)
        
        if dp[currDay] != -1:
            return dp[currDay]
        
        oneDay = costs[0] + self.solve(dp, days, costs, currDay + 1)
        sevenDay = costs[1] + self.solve(dp, days, costs, currDay + 7)
        thirtyDay = costs[2] + self.solve(dp, days, costs, currDay + 30)
        
        dp[currDay] = min(oneDay, min(sevenDay, thirtyDay))
        return dp[currDay]
    
    def mincostTickets(self, days, costs):
        lastDay = days[-1]
        dp = [-1] * (lastDay + 1)
        
        for day in days:
            self.isTravelNeeded.add(day)
        
        return self.solve(dp, days, costs, 1)

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

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

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список.

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        vals = []
        
        def dfs(node):
            if node:
                vals.append(node.val)
                dfs(node.left)
                dfs(node.right)
        
        dfs(root)
        return all(v == vals[0] for v in vals)

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

Задача: 259. 3Sum Smaller
Сложность: medium

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

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

2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_count = 0
        for i in range(len(nums) - 2):
            sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
        return sum_count

    def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
        sum_count = 0
        for i in range(startIndex, len(nums) - 1):
            j = self.binarySearch(nums, i, target - nums[i])
            sum_count += j - i
        return sum_count

    def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
        left, right = startIndex, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def f(p, i, m):
            if i == len(piles):
                return 0
            if dp[p][i][m] != -1:
                return dp[p][i][m]
            res = 1000000 if p == 1 else -1
            s = 0
            for x in range(1, min(2 * m, len(piles) - i) + 1):
                s += piles[i + x - 1]
                if p == 0:
                    res = max(res, s + f(1, i + x, max(m, x)))
                else:
                    res = min(res, f(0, i + x, max(m, x)))
            dp[p][i][m] = res
            return res

        dp = [[[-1] * (len(piles) + 1) for _ in range(len(piles) + 1)] for _ in range(2)]
        return f(0, 0, 1)

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

Задача: 214. Shortest Palindrome
Сложность: hard

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

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1️⃣Создайте обратную строку от исходной строки s, назовем ее rev. Она будет использована для сравнения, чтобы найти наибольший палиндромный сегмент с начала строки.

2️⃣ Итеративно перемещайтесь по переменной i от 0 до size(s) - 1:
Если s[0:n−i] == rev[i:] (т.е. подстрока s от 0 до n−i равна подстроке rev от i до конца строки). Это по сути означает, что подстрока от 0 до n−i является палиндромом, так как rev является обратной строкой s.

3️⃣ Так как мы находим сначала большие палиндромы, можем вернуть обратную строку от наибольшего палиндрома + s, как только найдем его.

😎 Решение:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        rev = s[::-1]
        for i in range(n):
            if s[: n - i] == rev[i:]:
                return rev[:i] + s
        return ""

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

Задача: 823. Binary Trees With Factors
Сложность: medium

Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.

Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов.

Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7.

Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

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

1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎 Решение:

class Solution:
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        A.sort()
        dp = [1] * len(A)
        index = {x: i for i, x in enumerate(A)}
        
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0:
                    right = x // A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

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

Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium

Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.

Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

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

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

2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

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

😎 Решение:

def countSquares(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    count = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                count += dp[i][j]
                
    return count

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

Задача: 411. Minimum Unique Word Abbreviation
Сложность: hard

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.

Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

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

1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:

def generate_abbreviations(word):
    def helper(word, current, pos, count, result):
        if pos == len(word):
            result.add(current + (str(count) if count > 0 else ""))
            return
        helper(word, current, pos + 1, count + 1, result)
        helper(word, current + (str(count) if count > 0 else "") + word[pos], pos + 1, 0, result)
    
    result = set()
    helper(word, "", 0, 0, result)
    return result

def min_abbreviation(target, dictionary):
    target_abbrs = generate_abbreviations(target)
    dict_abbrs = set()
    for word in dictionary:
        dict_abbrs.update(generate_abbreviations(word))
    valid_abbrs = target_abbrs - dict_abbrs
    return min(valid_abbrs, key=len)

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        counter = collections.Counter(nums)
        result = 0
        
        for x in counter:
            if k > 0 and (x + k) in counter:
                result += 1
            elif k == 0 and counter[x] > 1:
                result += 1
        
        return result

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

Задача: 371. Sum of Two Integers
Сложность: medium

Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -.

Пример:

Input: a = 1, b = 2
Output: 3

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

1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата.

2⃣Если нужно вычислить сумму:
Пока перенос не равен нулю (y != 0):
Текущий ответ без переноса равен XOR x и y: answer = x ^ y.
Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = carry.
Верните x * sign.

3⃣Если нужно вычислить разность:
Пока заимствование не равно нулю (y != 0):
Текущий ответ без заимствования равен XOR x и y: answer = x ^ y.
Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = borrow.
Верните x * sign.

😎 Решение:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        x, y = abs(a), abs(b)
        if x < y:
            return self.getSum(b, a)  
        sign = 1 if a > 0 else -1
        
        if a * b >= 0:
            while y:
                x, y = x ^ y, (x & y) << 1
        else:
            while y:
                x, y = x ^ y, ((~x) & y) << 1
        
        return x * sign

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

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

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

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

😎 Решение:

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.sum = 0
    
    def next(self, val: int) -> float:
        self.queue.append(val)
        self.sum += val
        if len(self.queue) > self.size:
            self.sum -= self.queue.popleft()
        return self.sum / len(self.queue)

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

Задача: 588. Design In-Memory File System
Сложность: hard

Спроектируйте структуру данных, которая симулирует файловую систему в памяти.

Реализуйте класс FileSystem:
FileSystem() Инициализирует объект системы.
List<String> ls(String path)
Если path является путем к файлу, возвращает список, содержащий только имя этого файла.
Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.
Ответ должен быть в лексикографическом порядке.
void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.
void addContentToFile(String filePath, String content)
Если filePath не существует, создает файл, содержащий заданный контент.
Если filePath уже существует, добавляет заданный контент к исходному содержимому.
String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.

Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

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

1⃣ Инициализация файловой системы:
Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content.

2⃣ Обработка команд:
Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.
Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.
Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.
Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.

3⃣ Обработка путей и работа с файлами/директориями:
Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов.
Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий.

😎 Решение:

class FileSystem:
    class File:
        def __init__(self):
            self.isfile = False
            self.files = {}
            self.content = ""

    def __init__(self):
        self.root = self.File()

    def ls(self, path: str) -> list:
        t = self._navigate(path)
        if t.isfile:
            return [path.split("/")[-1]]
        return sorted(t.files.keys())

    def mkdir(self, path: str) -> None:
        self._navigate(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        t = self._navigate(filePath)
        t.isfile = True
        t.content += content

    def readContentFromFile(self, filePath: str) -> str:
        return self._navigate(filePath).content

    def _navigate(self, path: str) -> 'File':
        t = self.root
        if path != "/":
            for dir in path.split("/"):
                if dir:
                    if dir not in t.files:
                        t.files[dir] = self.File()
                    t = t.files[dir]
        return t

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

1⃣Используйте стек для отслеживания текущего уровня скобок.

2⃣Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее число, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

import collections

def countOfAtoms(formula: str) -> str:
    stack = [collections.Counter()]
    i, n = 0

    while i < n:
        if formula[i] == '(':
            stack.append(collections.Counter())
            i += 1
        elif formula[i] == ')':
            top = stack.pop()
            i += 1
            i_start = i
            while i < n and formula[i].isdigit():
                i += 1
            multiplicity = int(formula[i_start:i] or 1)
            for name, count in top.items():
                stack[-1][name] += count * multiplicity
        else:
            i_start = i
            i += 1
            while i < n and formula[i].islower():
                i += 1
            name = formula[i_start:i]
            i_start = i
            while i < n and formula[i].isdigit():
                i += 1
            multiplicity = int(formula[i_start:i] or 1)
            stack[-1][name] += multiplicity

    result = ''
    for name in sorted(stack[-1]):
        result += name
        if stack[-1][name] > 1:
            result += str(stack[-1][name])
    
    return result

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

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

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

3⃣Завершение работы:
Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому.

😎 Решение:

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

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

Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

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

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

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

😎 Решение:

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

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

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

class Solution:
    def valid(self, str1, str2, k):
        len1, len2 = len(str1), len(str2)
        if len1 % k > 0 or len2 % k > 0:
            return False
        else:
            base = str1[:k]
            n1, n2 = len1 // k, len2 // k
            return str1 == base * n1 and str2 == base * n2
    
    def gcdOfStrings(self, str1, str2):
        len1, len2 = len(str1), len(str2)
        for i in range(min(len1, len2), 0, -1):
            if self.valid(str1, str2, i):
                return str1[:i]
        return ""

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

Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.

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

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

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

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

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

😎 Решение:

class Solution:
    def __init__(self):
        self.answer = []
        self.digits = ""
        self.target = 0

    def recurse(self, index, previous_operand, current_operand, value, ops):
        if index == len(self.digits):
            if value == self.target and current_operand == 0:
                self.answer.append("".join(ops[1:]))
            return

        current_operand = current_operand * 10 + int(self.digits[index])
        str_operand = str(current_operand)

        if current_operand > 0:
            self.recurse(index + 1, previous_operand, current_operand, value, ops)

        ops.append("+")
        ops.append(str_operand)
        self.recurse(index + 1, current_operand, 0, value + current_operand, ops)
        ops.pop()
        ops.pop()

        if ops:
            ops.append("-")
            ops.append(str_operand)
            self.recurse(index + 1, -current_operand, 0, value - current_operand, ops)
            ops.pop()
            ops.pop()

            ops.append("*")
            ops.append(str_operand)
            self.recurse(index + 1, current_operand * previous_operand, 0, value - previous_operand + (current_operand * previous_operand), ops)
            ops.pop()
            ops.pop()

    def addOperators(self, num, target):
        if not num:
            return []

        self.target = target
        self.digits = num
        self.answer = []
        self.recurse(0, 0, 0, 0, [])
        return self.answer

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