Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

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

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        count = 0
        for num in nums:
            if num == target:
                count += 1
        return count > len(nums) // 2

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

Задача: 418. Sentence Screen Fitting
Сложность: medium

Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.

Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.

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

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

😎 Решение:

def wordsTyping(sentence, rows, cols):
    sentence_str = " ".join(sentence) + " "
    length = len(sentence_str)
    pos = 0
    
    for _ in range(rows):
        pos += cols
        if sentence_str[pos % length] == " ":
            pos += 1
        else:
            while pos > 0 and sentence_str[(pos - 1) % length] != " ":
                pos -= 1
    
    return pos // length

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

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

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

import bisect

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    dp = [(0, 0)]

    for s, e, p in jobs:
        i = bisect.bisect_right(dp, (s, float('inf')))
        if dp[i-1][1] + p > dp[-1][1]:
            dp.append((e, dp[i-1][1] + p))
    
    return dp[-1][1]

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

Задача: 838. Push Dominoes
Сложность: medium

Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.

В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.

Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

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

2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.

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

😎 Решение:

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        N = len(dominoes)
        indexes = [-1]
        symbols = ['L']
        
        for i in range(N):
            if dominoes[i] != '.':
                indexes.append(i)
                symbols.append(dominoes[i])
                
        indexes.append(N)
        symbols.append('R')
        
        ans = list(dominoes)
        for idx in range(len(indexes) - 1):
            i, j = indexes[idx], indexes[idx + 1]
            x, y = symbols[idx], symbols[idx + 1]
            if x == y:
                for k in range(i + 1, j):
                    ans[k] = x
            elif x == 'R' and y == 'L':
                for k in range(i + 1, j):
                    if k - i == j - k:
                        ans[k] = '.'
                    elif k - i < j - k:
                        ans[k] = 'R'
                    else:
                        ans[k] = 'L'
                        
        return ''.join(ans)

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

Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

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

1⃣Начните с:

Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:

Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

class Solution:
    MOD = 10**9 + 7
    
    def waysToTarget(self, memo, diceIndex, n, currSum, target, k):
        if diceIndex == n:
            return int(currSum == target)
        
        if memo[diceIndex][currSum] != -1:
            return memo[diceIndex][currSum]
        
        ways = 0
        for i in range(1, min(k, target - currSum) + 1):
            ways = (ways + self.waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % self.MOD
        
        memo[diceIndex][currSum] = ways
        return ways
    
    def numRollsToTarget(self, n, k, target):
        memo = [[-1] * (target + 1) for _ in range(n + 1)]
        return self.waysToTarget(memo, 0, n, 0, target, k)

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

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

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

def numSubarraysWithSum(nums, goal):
    prefix_sum_count = {0: 1}
    current_sum = 0
    count = 0
    
    for num in nums:
        current_sum += num
        if current_sum - goal in prefix_sum_count:
            count += prefix_sum_count[current_sum - goal]
        if current_sum in prefix_sum_count:
            prefix_sum_count[current_sum] += 1
        else:
            prefix_sum_count[current_sum] = 1
    
    return count

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 760. Find Anagram Mappings
Сложность: easy

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

1⃣Создайте словарь для хранения индексов элементов в nums2.

2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.

3⃣Верните массив индексов.

😎 Решение:

def anagramMapping(nums1, nums2):
    index_map = {}
    for i, num in enumerate(nums2):
        if num in index_map:
            index_map[num].append(i)
        else:
            index_map[num] = [i]
    
    mapping = []
    for num in nums1:
        mapping.append(index_ma

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

Задача: 1267. Count Servers that Communicate
Сложность: medium

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

Input: grid = [[1,0],[0,1]]
Output: 0

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

1⃣Подсчитайте количество серверов в каждой строке и каждом столбце.

2⃣Пройдите по каждой ячейке и определите, взаимодействует ли сервер с другими серверами в той же строке или столбце.

3⃣Подсчитайте и верните количество взаимодействующих серверов.

😎 Решение:

def countServers(grid):
    rows = [0] * len(grid)
    cols = [0] * len(grid[0])

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                rows[i] += 1
                cols[j] += 1

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1):
                count += 1

    return count

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

Задача: 245. Shortest Word Distance II
Сложность: medium

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

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

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

from bisect import bisect_right

class Solution:
    def shortestWordDistance(self, wordsDict, word1, word2):
        indices1 = [i for i, word in enumerate(wordsDict) if word == word1]
        indices2 = [i for i, word in enumerate(wordsDict) if word == word2]
        
        shortestDistance = float('inf')
        for index in indices1:
            x = bisect_right(indices2, index)
            if x < len(indices2):
                shortestDistance = min(shortestDistance, indices2[x] - index)
            if x > 0 and indices2[x - 1] != index:
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
        return shortestDistance

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

Задача: 1214. Two Sum BSTs
Сложность: medium

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

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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

class Solution:
    def dfs(self, node, node_set):
        if not node:
            return
        self.dfs(node.left, node_set)
        node_set.add(node.val)
        self.dfs(node.right, node_set)

    def twoSumBSTs(self, root1, root2, target):
        node_set1 = set()
        node_set2 = set()
        self.dfs(root1, node_set1)
        self.dfs(root2, node_set2)
        
        for value1 in node_set1:
            if target - value1 in node_set2:
                return True
                
        return False

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

Задача: 1231. Divide Chocolate
Сложность: hard

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

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

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

2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.

3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎 Решение:

def maximizeSweetness(sweetness, k):
    def canDivide(minSweetness):
        current_sum = 0
        cuts = 0
        for sweet in sweetness:
            current_sum += sweet
            if current_sum >= minSweetness:
                cuts += 1
                current_sum = 0
        return cuts >= k + 1

    left, right = min(sweetness), sum(sweetness) // (k + 1)
    while left < right:
        mid = (left + right + 1) // 2
        if canDivide(mid):
            left = mid
        else:
            right = mid - 1
    return left

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2

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

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

def maxUncrossedLines(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

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

😎 Решение:

def isRobotBounded(instructions):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    x = y = 0
    direction = 0
    
    for instruction in instructions:
        if instruction == 'G':
            x += directions[direction][0]
            y += directions[direction][1]
        elif instruction == 'L':
            direction = (direction + 3) % 4
        elif instruction == 'R':
            direction = (direction + 1) % 4
    
    return (x == 0 and y == 0) or direction != 0

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

Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy

Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.

Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

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

1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false.

2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0.

3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount.

😎 Решение:

class Solution:
    def hasEvenDigits(self, num: int) -> bool:
        digitCount = 0
        while num > 0:
            digitCount += 1
            num //= 10
        return (digitCount & 1) == 0

    def findNumbers(self, nums: list[int]) -> int:
        evenDigitCount = 0
        for num in nums:
            if self.hasEvenDigits(num):
                evenDigitCount += 1
        return evenDigitCount

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

Задача: 161. One Edit Distance
Сложность: medium

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.

Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1️⃣Проверка длины строк: Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку. Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2️⃣Сравнение строк посимвольно: Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t. Если находите различающийся символ: Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false. Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

3️⃣Проверка на возможное добавление символа в конец s: Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true. В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.

😎 Решение:

class Solution:
    def isOneEditDistance(self, s: "str", t: "str") -> "bool":
        ns, nt = len(s), len(t)
        if ns > nt:
            return self.isOneEditDistance(t, s)
        if nt - ns > 1:
            return False

        for i in range(ns):
            if s[i] != t[i]:
                if ns == nt:
                    return s[i + 1 :] == t[i + 1 :]
                else:
                    return s[i:] == t[i + 1 :]
        return ns + 1 == nt

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

Задача: 927. Three Equal Parts
Сложность: hard

Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с 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] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.

Пример:

Input: arr = [1,0,1,0,1]
Output: [0,3]

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

1⃣Подсчитать количество единиц в массиве.

2⃣Если количество единиц не делится на три, вернуть [-1, -1].
Найти индексы начала каждой части, игнорируя ведущие нули.
Использовать эти индексы для проверки, могут ли три части быть одинаковыми.

3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].

😎 Решение:

def threeEqualParts(arr):
    ones = sum(arr)
    if ones % 3 != 0:
        return [-1, -1]
    if ones == 0:
        return [0, len(arr) - 1]
    
    part_ones = ones // 3
    first = second = third = cnt = 0
    for i, val in enumerate(arr):
        if val == 1:
            if cnt == 0:
                first = i
            elif cnt == part_ones:
                second = i
            elif cnt == 2 * part_ones:
                third = i
            cnt += 1
    
    while third < len(arr) and arr[first] == arr[second] == arr[third]:
        first += 1
        second += 1
        third += 1
    
    if third == len(arr):
        return [first - 1, second]
    return [-1, -1]

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

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

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

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

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

😎 Решение:

def minDeletionSize(strs):
    n = len(strs)
    m = len(strs[0])
    delete_count = [False] * m
    
    def is_sorted():
        for i in range(n - 1):
            for j in range(m):
                if delete_count[j]:
                    continue
                if strs[i][j] > strs[i + 1][j]:
                    return False
                if strs[i][j] < strs[i + 1][j]:
                    break
        return True
    
    while not is_sorted():
        for j in range(m):
            if delete_count[j]:
                continue
            for i in range(n - 1):
                if strs[i][j] > strs[i + 1][j]:
                    delete_count[j] = True
                    break
            if delete_count[j]:
                break
    
    return sum(delete_count)

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