[Swift]LeetCode846.一手顺子|HandofStraights

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

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

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

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

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

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

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

Note:

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

爱丽丝有一手（hand）由整数数组给定的牌。

现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。

如果她可以完成分组就返回 true，否则返回 false。

示例 1：

输入：hand = [1,2,3,6,2,3,4,7,8], W = 3
输出：true
解释：爱丽丝的手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：

输入：hand = [1,2,3,4,5], W = 4
输出：false
解释：爱丽丝的手牌无法被重新排列成几个大小为 4 的组。

提示：

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

240ms

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         guard hand.count % W == 0 else { return false }
 4         var modulus = Array(repeating: 0, count: W)
 5         for i in 0..<hand.count {
 6             modulus[hand[i]%W] += 1
 7         }
 8         for i in 0..<modulus.count-1 {
 9             if modulus[i] != modulus[i+1] {
10                 return false
11             }
12         }
13         return true
14     }
15 }

300ms

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         if W == 0 { return true }
 4         if hand.count % W != 0 { return false }
 5 
 6         var map = [Int: Int]()
 7         for h in hand { map[h, default: 0] += 1 }
 8         let sortedHand = Array(Set<Int>(hand)).sorted()
 9         if sortedHand.count < W { return false }
10 
11         for i in 0 ... sortedHand.count - W {
12             let cti = map[sortedHand[i]]!
13             if cti == 0 { continue }
14             map[sortedHand[i]]! -= cti
15             for j in (i+1)..<(W+i) {
16                 if map[sortedHand[j]]! < cti { return false }
17                 if sortedHand[j] !=  sortedHand[j-1] + 1 { return false }
18                 map[sortedHand[j]]! -= cti
19             }
20         }
21 
22         return map.values.filter{ $0 > 0 }.count == 0
23     }
24 }

356ms

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         guard hand.count % W == 0 else { return false }
 4         let hand = hand.sorted()
 5         var dict = hand.reduce(into: [Int: Int]()){ $0[$1, default: 0] += 1 }
 6         for n in hand {
 7             guard dict[n, default: 0] > 0 else { continue }
 8             for w in 0..<W {
 9                 dict[n+w, default: 0] -= 1
10                 if dict[n+w, default: 0] < 0 { return false }
11             }
12         }
13         return dict.filter{ $0.value > 0 }.isEmpty
14     }
15 }

Runtime: 372 ms

Memory Usage: 19.5 MB

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         var c:[Int:Int] = [Int:Int]()
 4         var hand = hand.sorted(by:<)
 5         for i in hand
 6         {
 7             c[i,default:0] += 1          
 8         }
 9         var start:[Int] = [Int]()
10         var last_checked:Int = -1
11         var opened:Int = 0
12         var nums = Set(c.keys).sorted(by:<)
13         for key in nums
14         {
15             if opened > 0 && key > last_checked + 1 || opened > c[key,default:0]
16             {
17                 return false
18             }
19             start.append(c[key,default:0] - opened)
20             last_checked = key
21             opened = c[key,default:0]
22             if start.count == W
23             {
24                 opened -= start.removeFirst()                
25             }
26         }
27         return opened == 0
28     }
29 }

376ms

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         guard hand.count % W == 0 else { return false }
 4         let limit = 1_000_000_000
 5         var cache: [Int: Int] = [Int: Int]()
 6         for card in hand {
 7             cache[card, default: 0] += 1
 8         }
 9         
10         var sortedKeys = cache.keys.sorted()
11         while !cache.isEmpty {
12             let first = sortedKeys.first!
13             for i in first..<first+W {
14                 guard let value = cache[i] else { return false }
15                 cache[i] = value - 1
16                 if cache[i] == 0 {
17                     cache.removeValue(forKey: i)
18                     if let index = sortedKeys.index(of: i) { 
19                         sortedKeys.remove(at: index) 
20                     }
21                 }
22             }
23         }
24         return true
25     }
26 }

540ms

 1 class Solution {
 2     func isNStraightHand(_ hand: [Int], _ W: Int) -> Bool {
 3         if hand.count % W != 0 { return false }
 4         let hand = hand.sorted()
 5         let list = DoublyLinkedList(hand)
 6         
 7         while !list.isEmpty {
 8             var count = W
 9             var node = list.head.next
10             var prevVal = -1
11             while count > 0 && !list.isEmpty && node !== list.tail {
12                 let val = node!.val
13                 if prevVal >= 0 {
14                     if val == prevVal {
15                         node = node!.next
16                     } else if (val - 1) != prevVal {
17                         return false
18                     } else {
19                         prevVal = val
20                         node = node!.next
21                         list.delete(node!.prev!)
22                         count -= 1
23                     }
24                 } else {
25                     prevVal = val
26                     list.delete(node!)
27                     count -= 1
28                     node = list.head.next
29                 }
30             }
31             if count > 0 { return false }
32         }
33         return true
34     }
35 }
36 
37 class DoublyLinkedList {
38     var head = Node(0)
39     var tail = Node(0)
40     
41     init() {
42         head.next = tail
43         tail.prev = head
44     }
45     
46     init(_ arr: [Int]) {
47         head.next = tail
48         tail.prev = head
49         for el in arr {
50             append(el)
51         }
52     }
53     
54     func append(_ val: Int) {
55         let node = Node(val)
56         if isEmpty {
57             head.next = node
58             node.next = tail
59             node.prev = head
60             tail.prev = node
61         } else {
62             tail.prev?.next = node
63             node.next = tail
64             node.prev = tail.prev
65             tail.prev = node
66         }
67     }
68     
69     func delete(_ node: Node) {
70         node.prev?.next = node.next
71         node.next?.prev = node.prev
72     }
73     
74     var isEmpty: Bool {
75         return head.next === tail
76     }
77     
78     func printL() {
79         var node = head.next
80         while node !== tail {
81             print("\(node!.val)", terminator: "->")
82             node = node!.next
83         }
84         print("")
85     }
86 }
87 
88 class Node {
89     var val: Int
90     var next: Node?
91     weak var prev: Node?
92     
93     init(_ val: Int) {
94         self.val = val
95     }
96 }