[leetcode] 1010. Pairs of Songs With Total Durations Divisible by 60

[leetcode] 1010. Pairs of Songs With Total Durations Divisible by 60

Description

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]Output: 3Explanation: Three pairs have a total duration divisible by 60:(time[0] = 30, time[2] = 150): total duration 180(time[1] = 20, time[3] = 100): total duration 120(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]Output: 3Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1 <= time.length <= 60000.1 <= time[i] <= 500.

分析

题目的意思是：求出所有两个数加起来能够被60整除的对，我最开始用暴力破解了一下，果然超时了，看了结果才发现需要找规律，做法是这样，首先对所有的数用60取余数，然后进行统计，我这里用字典实现了统计的过程，接着就是从余数中统计出哪些组合能够被60整除了，余数为0或者30的数，组合形式的数目为v*(v-1)//2，不要问我为什么，我也只是验证了一下，发现是这个样子的。对于小于30的数，看字典中有没有能够加在一起构成60的，如果有组合形式就为，避免重复，大于30的就要跳过了哈：

cnt+=cnt_dict[k]*cnt_dict[60-k]

代码

class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: n=len(time) cnt=0 cnt_dict={} for i in range(n): key=time[i]%60 if(key in cnt_dict): cnt_dict[key]+=1 else: cnt_dict[key]=1 for k,v in cnt_dict.items(): if(k==0 or k==30): cnt+=v*(v-1)//2 elif(k>30): continue elif(60-k in cnt_dict): cnt+=cnt_dict[k]*cnt_dict[60-k] return cnt

参考文献

​​[LeetCode] Tried this in Python​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。