Задача: 930. Binary Subarrays With Sum
Сложность: medium
Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.
Пример:
👨💻 Алгоритм:
1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.
2⃣Пройти по массиву и обновить текущую сумму.
Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов.
Обновить словарь префиксных сумм.
3⃣Вернуть счетчик подмассивов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: №45. Jump Game II
Сложность: medium
Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Возвращает минимальное количество переходов для достижения nums[n - 1].
Пример:
👨💻 Алгоритм:
1️⃣Используем BFS-подход с отслеживанием границ уровня.
2️⃣На каждой итерации обновляем самую дальнюю достижимую позицию.
3️⃣Когда текущий уровень заканчивается, увеличиваем счетчик прыжков и переходим на новый уровень.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 760. Find Anagram Mappings
Сложность: easy
Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.
Пример:
👨💻 Алгоритм:
1⃣Создайте словарь для хранения индексов элементов в nums2.
2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.
3⃣Верните массив индексов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍2💊1
Задача: 1267. Count Servers that Communicate
Сложность: medium
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
👨💻 Алгоритм:
1⃣Подсчитайте количество серверов в каждой строке и каждом столбце.
2⃣Пройдите по каждой ячейке и определите, взаимодействует ли сервер с другими серверами в той же строке или столбце.
3⃣Подсчитайте и верните количество взаимодействующих серверов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍1💊1
Задача: 245. Shortest Word Distance II
Сложность: medium
Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.
Пример:
👨💻 Алгоритм:
1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.
2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.
3️⃣Верните значение переменной shortestDistance.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍2
Задача: 1214. Two Sum BSTs
Сложность: medium
Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.
Пример:
👨💻 Алгоритм:
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.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.
Пример:
👨💻 Алгоритм:
1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.
2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.
3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
🔥2
Задача: 1035. Uncrossed Lines
Сложность: medium
Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.
Пример:
👨💻 Алгоритм:
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].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.
Пример:
👨💻 Алгоритм:
1⃣Понимание поведения робота:
Мы анализируем, как робот движется в пределах одной серии команд. Если он вернется в начальную точку или изменит направление после выполнения всех команд, значит, он будет двигаться по замкнутой траектории, что соответствует условию задачи.
2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).
3⃣Обработка команд:
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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. Верните количество чисел в массиве, которые содержат четное количество цифр.
Пример:
👨💻 Алгоритм:
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.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
Пример:
👨💻 Алгоритм:
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 без возможности привести их к равенству одной операцией редактирования.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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] представляют одно и то же значение.
Пример:
👨💻 Алгоритм:
1⃣Подсчитать количество единиц в массиве.
2⃣Если количество единиц не делится на три, вернуть [-1, -1].
Найти индексы начала каждой части, игнорируя ведущие нули.
Использовать эти индексы для проверки, могут ли три части быть одинаковыми.
3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
Пример:
👨💻 Алгоритм:
1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.
2⃣Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.
3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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)
Ставь 👍 и забирай 📚 Базу знаний