Сложность: medium
Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.
Пример:
Input: time = [30,20,150,100,40]
Output: 3
👨💻 Алгоритм:
1⃣Инициализация и вычисление остатков:
Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями.
2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.
3⃣Возврат результата:
Верните общее количество пар.
😎 Решение:
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
remainders = [0] * 60
count = 0
for t in time:
if t % 60 == 0:
count += remainders[0]
else:
count += remainders[60 - t % 60]
remainders[t % 60] += 1
return count
Ставь 👍 и забирай 📚 Базу знаний