1010. Pairs of Songs With Total Durations Divisible by 60

问题:

给出一列歌曲所花时间的数组。

求任意两首歌合起来时间是60分钟的倍数的组队pair数。

Example 1:
Input: [30,20,150,100,40]
Output: 3
Explanation: 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: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60. 

Note:
1 <= time.length <= 60000
1 <= time[i] <= 500

  

解法:

遍历数组,依次读入一个元素,

查看已遍历过的元素中,是否存在与当前元素互补(和=60倍数)的元素,假设有n个,那么到当前元素为止,已经有n个pair了。

(其实感觉思想都是看当前状态下的一个结果,思想很像DP:注重某个状态)

假设遍历到的当前元素时间为 t

那么我们要找的互补元素为:(t+X)%60=0

t%60+X%60=60

X%60=60-t%60

所以,我们用数组c[i]来记录,已遍历过数组元素中,被60除,余 i 的个数。

当遍历到 t 的时候,我们得到的互补元素个数即为 c[60-t%60]

⚠️ 注意:这里当 t=60时,会访问c[60],我们设定数组index:0~59,

因此,我们应该访问c[0],上述式子 c[60-t%60] 转化为-> c[(60-t%60)%60]

同时将当前的元素更新到数组c中,c[t%60]++

 

代码参考:

 1 class Solution {
 2 public:
 3     int numPairsDivisibleBy60(vector<int>& time) {
 4         int res=0;
 5         int c[60]={0};
 6         for(int t:time){
 7             res+=c[(60-t%60)%60];
 8             c[t%60]++;
 9         }
10         return res;
11     }
12 };

 

上一篇:[LeetCode] 368. Largest Divisible Subset


下一篇:OpenWrt 编译分割