leetcode 1013. Pairs of Songs With Total Durations Divisible by 60
程序员文章站
2022-05-27 15:26:27
...
leetcode 1013. Pairs of Songs With Total Durations Divisible by 60
题意:一个数组,每个数表示每首歌循环的时间。将所有歌两两匹配,要求满足两首歌持续的总时间能被60整除。求多少种方案。
思路:歌有50000,但是时间只有500。所以考虑将时间都对60取余,统计总个数。
mp[i]表示持续时间为i的歌的数量。
那么对于任意的i,都可以找到60-i进行匹配。
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
map<int, int>mp;
for (int i = 0; i < time.size(); i++)
mp[time[i] % 60]++;
int ans = 0;
if (mp[0]) ans += mp[0] * (mp[0] - 1)/2;
for (int i = 1; i < 30; i++)
if (mp[i] && mp[60 - i])
ans += mp[i] * mp[60 - i];
if (mp[30]) ans += mp[30] * (mp[30] - 1) / 2;
return ans;
}
};
上一篇: MongoDB数据库单节点安装