Задача: 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
Ставь 👍 и забирай 📚 Базу знаний
👍1