[Swift]LeetCode1010.总持续时间可被60整除的歌曲|PairsofSongsWithTotalDurationsDiv ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10546217.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a list of songs, the i-th 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 i < j with (time[i] + time[j]) % 60 == 0.

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

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。

示例 1：

输入：[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：

输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。

提示：

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

212ms

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3         var res = 0
 4         var rems: [Int] = Array(repeating: 0, count: 60)
 5         for t in time {
 6             rems[t % 60] += 1
 7         }
 8         for i in (0..<rems.count - 1) {
 9             for j in  (i..<rems.count) {
10                 if (i + j) % 60 == 0 {
11                     if i == j {
12                        res = res + ((rems[i] * (rems[i] - 1)) / 2)
13                     } else if rems[i] != 0 && rems[j] != 0 {
14                         res += (rems[i] * rems[j])
15                     }
16                  }
17             }
18         }
19         return res
20     }
21 }

228ms

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3         if time.count <= 1 { return 0 }
 4         let count = time.count
 5         var rs = [Int](repeating: 0, count: count)
 6         var map = [Int: Int]()
 7         var pair = 0
 8         for i in 0..<count {
 9             let r = time[i] % 60
10             if let c = map[r] {
11                 map[r] = c + 1
12             } else {
13                 map[r] = 1
14             }
15         }
16         for i in 1..<30 {
17             guard let c1 = map[i], let c2 = map[60 - i] else { continue }
18             pair += c1 * c2
19         }
20         if let c = map[0], c > 1 {
21             pair += (c * (c - 1)) / 2
22         }
23         if let c = map[30], c > 1 {
24             pair += (c * (c - 1)) / 2
25         }
26         return pair
27     }
28 }

Runtime: 232 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3         var n:Int = time.count
 4         var cnt:[Int] = [Int](repeating:0,count:60)
 5         var ans:Int = 0
 6         for i in 0..<n
 7         {
 8             var t:Int = time[i] % 60
 9             ans += cnt[(60 - t) % 60]
10             cnt[time[i] % 60] += 1
11         }
12         return ans
13         
14     }
15 }

236ms

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3     if time.count == 0 {
 4         return 0
 5     }
 6 
 7     var tempDic = [Int : Int]()
 8 
 9     for temp in time {
10         let v = temp % 60
11         let number = tempDic[v] ?? 0
12         tempDic[v] = number + 1
13     }
14 
15     var total = 0
16     
17     for (key, value) in tempDic {
18         
19         if key == 30 || key == 0 {
20             if value > 1 {
21                 let temp = value * (value - 1) / 2
22                 total += temp
23             }
24         }
25         else {
26             let v1 = 60 - key
27             if let cache = tempDic[v1] {
28                 total += value * cache
29                 tempDic[v1] = nil
30             }
31         }
32         tempDic[key] = nil
33     }
34     return total
35    }
36 }

252ms

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3         var bucket = Array(repeating: 0, count: 60)
 4         
 5         for time in time {
 6             bucket[time % 60] += 1
 7         }
 8         
 9         var result = 0
10         for i in 1...29 {
11             result += bucket[i] * bucket[60 - i]
12         }
13         
14         if bucket[0] >= 2 {
15             result += bucket[0] * (bucket[0] - 1) / 2
16         }
17         if bucket[30] >= 2 {
18             result += bucket[30] * (bucket[30] - 1) / 2
19         }
20         
21         return result
22     }
23 }

256ms

 1 class Solution {
 2     func numPairsDivisibleBy60(_ time: [Int]) -> Int {
 3         var res = 0
 4         var val = [Int: Int]()
 5         
 6         for t in time {
 7             let a = t % 60
 8             let sup = (60 - a) % 60
 9             res += val[a, default: 0]
10             if let v = val[sup] {
11                 val[sup] = v + 1
12             } else {
13                 val[sup] = 1
14             }
15         }
16         return res
17     }
18 }