05 August 2008
一手顺子,爱丽丝有一手(hand)由整数数组给定的牌。
现在她想把牌重新排列成组,使得每个组的大小都是 W,且由 W 张连续的牌组成。
如果她可以完成分组就返回 true,否则返回 false。
Alice has a
of cards, given as an array of integers.1
hand
Now she wants to rearrange the cards into groups so that each group is size
, and consists of 1
W
consecutive cards.1
W
Return
if and only if she can.1
true
1
2
3
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:
1
2
3
Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.
Constraints:
1
1 <= hand.length <= 10000
1
0 <= hand[i] <= 10^9
1
1 <= W <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Solution 1
Count number of different cards to a map c
Loop from the smallest card number.
Everytime we meet a new card i, we cut off i - i + W - 1 from the counter.
Complexity: Time O(MlogM + MW), where M is the number of different cards.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isNStraightHand(int[] hand, int W) {
Map<Integer, Integer> treemap = new TreeMap<>();
for (int h : hand) {
treemap.put(h, treemap.getOrDefault(h, 0) + 1);
}
for (int k : treemap.keySet()) {
if (treemap.get(k) > 0) {
for (int i = W- 1; i >= 0; i--) {
if (treemap.getOrDefault(k + i, 0) < treemap.get(k)) {
return false;
}
treemap.put(k + i, treemap.get(k + i) - treemap.get(k));
}
}
}
return true;
}
}