Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium
У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.
Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
👨💻 Алгоритм:
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.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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)
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 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