重庆品牌网站建设公司排名,帮助设计的网站,做神马网站优化排名,东莞网站关键排名题目#xff1a; 在歌曲列表中#xff0c;第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间#xff08;以秒为单位#xff09;可被 60 整除的歌曲对的数量。形式上#xff0c;我们希望下标数字 i 和 j 满足 i j 且有 (time[i] time[j]) % 60 0。
示例 1 在歌曲列表中第 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 示例 2
输入time [60,60,60] 输出3 解释所有三对的总持续时间都是 120可以被 60 整除。
提示
1 time.length 6 * 104 1 time[i] 500
来源力扣LeetCode 链接https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
题意 给出每首歌的持续时间让你选出所有时间和是60的倍数的歌曲一共有多少种组合。
思路 最简单粗暴的思路就是暴力两重循环每两个都看一遍能不能组成60的倍数。
这样必然是正确的但是也太…呆了。
那我们看看怎么能优化一下。
首先是这样暴力的做法底层逻辑是两个数相加再对60取余判断余数是否为 0 。
那这样的话是不是可以先对两个加数对60取余再进行相加判断呢
那想到这就很自然地发现对60取余之后就变成60以内的数了那如果最终结果是60的倍数不就说明余数相加是60的倍数嘛
那这样的话不就是对所有的数都对60取余然后用一个数组存下余数对应的数有多少个然后1-592-58这样两个余数对应的数字的数量相乘不就是答案嘛
OK到这这道题已经清晰了还有一点小细节需要注意。1-592-583-57这种的就直接对应数量做乘法就行。对于余数是0和余数是30的那就是它自身乘以除它自身外的所有数再除2。
代码
class Solution {
public:int numPairsDivisibleBy60(vectorint time) {vectorint cnt(60);for(int t : time){cnt[t%60];}int res 0;for(int i 1 ; i 30 ; i){res cnt[i]*cnt[60-i];}res (long long)cnt[0]*(cnt[0] - 1)/2 (long long)cnt[30]*(cnt[30] - 1)/2;return res;}
};
