1009. Complement of Base 10 Integer

You are given a list of songs where the ith 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 ij such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: time = [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: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Constraints:

  • 1 <= time.length <= 6 * 104
  • 1 <= time[i] <= 500

这道题说是给了一个歌曲列表的每首歌的播放时长,现在让找出有多少对儿的歌曲,使得其播放时长之和是 60 的倍数,看到这里有没有觉得很眼熟,没错,其实本质还是一道 Two Sum 的题,来跟着博主一起大声念 ’平生不识 TwoSum,刷尽 LeetCode 也枉然‘。不过这里不是简单的判断两数之和是否存在,而是要求出所有的符合题意的个数。由于数组中可能出现重复数字,所以需要统计出每个数字出现的个数。另外,这道题有一个很好的 trick,利用到了余数的性质,若两个数之和可以被 60 整数,则对其先分别对 60 取余后,再相加之和,还是可以被 60 整数,这样就可以把数字都缩小到 [0, 59] 的范围内了。之后就是要找和可以被 60 整除的两个数字了,经典的 Two Sum 的思路是先确定一个数字,然后用目标和减去当前这个数字,就是要在 HashMap 中查找是否存在。若是两个数字不同,则总共的组合数就是两个数字的出现次数直接相乘,但是假如两个数字相同,则是个组合问题,比如在n个数字中任意选两个数字的情况有多少种,为 n(n - 1) / 2。这里两个数字相同有两种情况,一种是它们都是 60 的倍数,取余后都变成了0,另一种是它们都是 30,这样加起来就是 60 的倍数,这两种情况要单独计算。还有,就是要用一个 HashSet 记录已经处理过的数字,以免产生重复计算,参见代码如下:

解法一:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int res = 0;
        unordered_set<int> visited;
        unordered_map<int, int> timeCnt;
        for (int t : time) ++timeCnt[t % 60];
        for (auto &a : timeCnt) {
            if (visited.count(a.first)) continue;
            if (a.first % 60 == 0 || a.first == 30) {
                res += (a.second - 1) * a.second / 2;
            } else {
                int target = 60 - a.first;
                if (!timeCnt.count(target)) continue;
                res += a.second * timeCnt[target];
                visited.insert(target);
            }
            visited.insert(a.first);
        }
        return res;
    }
};

其实有种更简洁的写法,不用在统计完了出现次数之后再计算,而是在统计的时候就直接累加了。这里没有用 HashMap,而是直接用了一个大小为 60 的数组,上面提到了通过对 60 取余,可以把数字都缩小到 [0, 59] 的范围内,对于每次遍历到的数字,加上能和其配对的数字的出现次数,方法是用 600 减去当前数字,然后对 60 取余。然后累加对 60 取余的次数,参见代码如下:

解法二:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int res = 0;
        vector<int> cnt(60);
        for (int t : time) {
            res += cnt[(600 - t) % 60];
            ++cnt[t % 60];
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1010

类似题目:

Two Sum

参考资料:

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256738/JavaC%2B%2BPython-Two-Sum-with-K-60

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256726/JavaPython-3-O(n)-code-w-comment-similar-to-Two-Sum

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation