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'shandcan 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'shandcan't be rearranged into groups of4.
Note:
1 <= hand.length <= 100000 <= hand[i] <= 10^91 <= 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 <= 100000 <= hand[i] <= 10^91 <= 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 }