题目链接
LeetCode 846. 一手顺子[1]
爱丽丝有一手(hand)由整数数组给定的牌。
现在她想把牌重新排列成组,使得每个组的大小都是 W
,且由 W
张连续的牌组成。
如果她可以完成分组就返回 true
,否则返回 false
。
说明:
1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length
示例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 的组。
这也是最直观的一个方法,用 map
来保存每个数出现的次数。
然后从最小的数开始,以它作为顺子的开头,然后看顺子里的数在不在 map
里,在就次数减一,不在就直接返回 false
。
接着重复上面步骤,最后直到 map
为空,最后返回 true
。
map
的特性就是你取它的第一个键值对,它的 key
就是最小的,这就很方便了。
首先对手牌从小到大进行排序,然后从最小的开始,作为顺子开头,遍历之后的数。如果在数组里,并且没有被访问过,那么就标记为访问过了。
注意可以提前终止遍历,也就是如果发现某一个顺子还没遍历完,但是访问到的元素已经超过接在顺子后的数了,那就直接返回 false
。
这题还有个解法,来自于题解区网友
zhanzq
,感觉挺不错的。但是我没怎么看懂,如果谁看懂了请教教我。
网友题解[2]
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
int n = hand.size();
if (n%W) return false;
map<int, int> count;
for (auto x : hand) count[x]++;
while (count.size()) {
int start = count.begin()->first;
for (int i = start; i < start+W; ++i) {
if (count.find(i) == count.end()) return false;
if (!--count[i]) count.erase(i);
}
}
return true;
}
};
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
int n = hand.size();
if (n%W) return false;
if (W==1) return true;
sort(hand.begin(), hand.end());
vector<int> vis(n, 0);
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
int cnt = 1;
vis[i] = 1;
for (int j = i+1; j < n; ++j) {
if (hand[j]>hand[i]+cnt) break;
if (!vis[j] && hand[j]==hand[i]+cnt) {
vis[j] = 1;
cnt++;
if (cnt == W) break;
}
}
if (cnt != W) return false;
}
return true;
}
};
class Solution {
public:
bool valid(vector<int> &lst, int W){
lst.push_back(0);
int sz = lst.size();
int pre = 0;
vector<int> deltas(sz, 0);
for(int i = 0; i < sz; i++){
pre += deltas[i];
if(pre < lst[i]){
int delta = lst[i] - pre;
pre = lst[i];
if(i + W < sz){
deltas[i+W] -= delta;
}
}else if(pre > lst[i]){
return false;
}
}
return true;
}
bool isNStraightHand(vector<int>& hand, int W) {
int sz = hand.size();
if(sz%W){
return false;
}else{
sort(hand.begin(), hand.end());
vector<int> lst;
int i = 0, j = 0;
while(i < sz){
while(j < sz && hand[i] == hand[j]){
j++;
}
lst.push_back(j - i);
if(j >= sz){
break;
}else if(hand[j] != hand[j-1] + 1){
lst.push_back(0);
}
i = j;
}
return valid(lst, W);
}
}
};
[1]
LeetCode 846. 一手顺子: https://leetcode-cn.com/problems/hand-of-straights/
[2]
网友题解: https://leetcode-cn.com/problems/hand-of-straights/solution/onlognsuan-fa-by-zhanzq/
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~
我的微信:weiyang792321264。有任何问题都可以在评论区留言,也欢迎加我微信深入沟通~