Задача: 496. Next Greater Element I
Сложность: easy
Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.
Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и поиск совпадений
Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.
2⃣Поиск следующего большего элемента
После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.
3⃣Заполнение результата
Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.
Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.
Пример:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
👨💻 Алгоритм:
1⃣Инициализация и поиск совпадений
Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.
2⃣Поиск следующего большего элемента
После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.
3⃣Заполнение результата
Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.
😎 Решение:
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = [-1] * len(nums1)
for i in range(len(nums1)):
found = False
for j in range(len(nums2)):
if nums2[j] == nums1[i]:
found = True
if found and nums2[j] > nums1[i]:
res[i] = nums2[j]
break
return res
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.
2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.
3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
👨💻 Алгоритм:
1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.
2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.
3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.
😎 Решение:
class Solution:
def minStartValue(self, nums: List[int]) -> int:
startValue = 1
while True:
total = startValue
isValid = True
for num in nums:
total += num
if total < 1:
isValid = False
break
if isValid:
return startValue
startValue += 1
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.
Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..
2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.
3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 418. Sentence Screen Fitting
Сложность: medium
Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.
Пример:
👨💻 Алгоритм:
1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.
2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.
3⃣Если следующая позиция является пробелом, увеличивайте счетчик. Если нет, уменьшайте счетчик, пока не найдете пробел, чтобы избежать разрыва слова.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
Пример:
👨💻 Алгоритм:
1⃣Сортировка заданий:
Сначала мы сортируем задания по времени их окончания. Это позволит нам легко проверять, какие задания могут быть выбраны без пересечения с предыдущими выбранными заданиями.
2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.
3⃣Для каждого задания мы можем либо взять его, либо не взять. Если мы берем задание, мы добавляем его прибыль к максимальной прибыли, полученной для заданий, которые заканчиваются до начала текущего задания. Для нахождения таких заданий используем двоичный поиск.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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]
Ставь 👍 и забирай 📚 Базу знаний
👍2
Задача: 838. Push Dominoes
Сложность: medium
Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.
В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.
Пример:
👨💻 Алгоритм:
1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы.
2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.
3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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)
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 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