1010.总持续时间可被 60 整除的歌曲
最近忙于毕设,leetcode也就随缘刷刷每日一题了。
题目
在歌曲列表中,第 i
首歌曲的持续时间为 time[i]
秒。
返回其总持续时间(以秒为单位)可被 60
整除的歌曲对的数量。形式上,我们希望下标数字 i
和 j
满足 i < j
且有 (time[i] + time[j]) % 60 == 0
。
示例1:
输入:time = [30,20,150,100,40]
输出:3
解释:这三对的总持续时间可被 60 整除:
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60
解题思路
题目评论区有条评论说的好:”看到数据集大于1e5 就别想O(N^2)以上的时间复杂度了,指定过不了“。奈何本笨读完题目,还是控制不住自己提交了一份暴力解法:
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
n = len(time)
count = 0
for i in range(n-1):
for j in range(i+1,n):
if (time[i]+time[j])%60 == 0:
count += 1
return count
毋庸置疑是运行超时了。然后我开始认真推敲题目,此时数组的什么对撞指针、滑动窗口等在我脑中冒出来,不过好像都用不上。然后点开题目下面的相关标签,里面发现“哈希表”这个关键词,想到了Pyhton的字典。于是有了下面的解法:
from math import comb
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
count = 0
count_dict = dict.fromkeys(range(60), 0)
for t in time:
count_dict[t%60] += 1
for i in range(0, 31):
if i == 0 or i == 30:
if count_dict[i]>1:
count += comb(count_dict[i], 2)
else:
count += count_dict[60 - i] * count_dict[i]
return count
忽略掉我花了整整一个小时才想出来的这个解法,最后显示通过执行用时超过了91%的提交记录还是挺意外挺开心的hhh。
这里就不详细说我想的过程了,直接说下我的最终思路:建立一个字典,用于记录歌曲持续时间取模60所得值出现的次数。我们知道任意两个数相加能被60整除,意味着两个数分别取模60后所得结果相加为60,并且出现两者的次数相乘的结果便是题目中所需统计的歌曲对数量。对于取模结果为0和30的两个数,两两相加也满足要求,所以就是他们的组合对数。因为需要满足i<j
,我们只用统计前半部分的歌曲对数即可,也就是0,[1,29], 30
。文章来源:https://www.toymoban.com/news/detail-435883.html
后来发现其实不用调用组合的comb
函数,n
个数的两两组合个数为:
n
(
n
−
1
)
/
2
n(n-1)/2
n(n−1)/2。又可以精简一下:文章来源地址https://www.toymoban.com/news/detail-435883.html
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
count = 0
count_dict = dict.fromkeys(range(60), 0)
for t in time:
count_dict[t%60] += 1
for i in range(0, 31):
if i == 0 or i == 30:
count += count_dict[i]*(count_dict[i]-1)//2
else:
count += count_dict[60 - i] * count_dict[i]
return count
到了这里,关于Leetcode【1010】总持续时间可被 60 整除的歌曲的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!