We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
输入:[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
输入:[60,60`60] 输出:3 解释:所有三对的总持续时间都是 120,可以被 60 整数。
提示:
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60
暴力法应该是最简单的了,就是两层循环完事,但是会超时:
func numPairsDivisibleBy60(time []int) int { var ret int; for i := 0; i < len(time); i++ { for j := i+1; j < len(time); j++ { if (time[i] + time[j]) % 60 == 0 { ret++ } } } return ret }
先把所有元素都求余,这样的话,每个元素对应的元素在不在数组中就很清晰明了。 假如当前的值20,如果我能知道40在这个数组中存在几个,那么就能知道最终的结果。 我们可以把每个元素作为key存到另一个数组arr中。因为题目要求是60,所以60个数组长度足够了。
key
arr
func numPairsDivisibleBy60(time []int) int { var ret int arr := [60]int{} for _, v := range time { remainder := v % 60 var t int if remainder == 0 { t = 0 } else { t = 60 - remainder } ret += arr[t] arr[remainder]++ } return ret }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1:
示例 2:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60
解答
暴力法
暴力法应该是最简单的了,就是两层循环完事,但是会超时:
数组+余数
先把所有元素都求余,这样的话,每个元素对应的元素在不在数组中就很清晰明了。
假如当前的值20,如果我能知道40在这个数组中存在几个,那么就能知道最终的结果。
我们可以把每个元素作为
key
存到另一个数组arr
中。因为题目要求是60,所以60个数组长度足够了。The text was updated successfully, but these errors were encountered: