题目链接
LeetCode 846. 一手顺子[1]
题目描述
爱丽丝有一手（hand）由整数数组给定的牌。
现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。
如果她可以完成分组就返回 true，否则返回 false。
说明：
1 <= hand.length <= 100000 <= hand[i] <= 10^91 <= 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 来保存每个数出现的次数。
然后从最小的数开始，以它作为顺子的开头，然后看顺子里的数在不在 map 里，在就次数减一，不在就直接返回 false 。
接着重复上面步骤，最后直到 map 为空，最后返回 true。
map 的特性就是你取它的第一个键值对，它的 key 就是最小的，这就很方便了。
排序统计
首先对手牌从小到大进行排序，然后从最小的开始，作为顺子开头，遍历之后的数。如果在数组里，并且没有被访问过，那么就标记为访问过了。
注意可以提前终止遍历，也就是如果发现某一个顺子还没遍历完，但是访问到的元素已经超过接在顺子后的数了，那就直接返回 false 。
排序统计2
这题还有个解法，来自于题解区网友
zhanzq，感觉挺不错的。但是我没怎么看懂，如果谁看懂了请教教我。
网友题解[2]
代码
巧用 map（c++）
classSolution { public: boolisNStraightHand(vector<int>&hand, intW) { intn=hand.size(); if (n%W) returnfalse; map<int, int>count; for (autox : hand) count[x]++; while (count.size()) { intstart=count.begin()->first; for (inti=start; i<start+W; ++i) { if (count.find(i) ==count.end()) returnfalse; if (!--count[i]) count.erase(i); } } returntrue; } };
排序统计（c++）
classSolution { public: boolisNStraightHand(vector<int>&hand, intW) { intn=hand.size(); if (n%W) returnfalse; if (W==1) returntrue; sort(hand.begin(), hand.end()); vector<int>vis(n, 0); for (inti=0; i<n; ++i) { if (vis[i]) continue; intcnt=1; vis[i] =1; for (intj=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) returnfalse; } returntrue; } };
排序统计2，来自于网友zhanzq（c++）
classSolution { public: boolvalid(vector<int>&lst, intW){ lst.push_back(0); intsz=lst.size(); intpre=0; vector<int>deltas(sz, 0); for(inti=0; i<sz; i++){ pre+=deltas[i]; if(pre<lst[i]){ intdelta=lst[i] -pre; pre=lst[i]; if(i+W<sz){ deltas[i+W] -=delta; } }elseif(pre>lst[i]){ returnfalse; } } returntrue; } boolisNStraightHand(vector<int>&hand, intW) { intsz=hand.size(); if(sz%W){ returnfalse; }else{ sort(hand.begin(), hand.end()); vector<int>lst; inti=0, j=0; while(i<sz){ while(j<sz&&hand[i] ==hand[j]){ j++; } lst.push_back(j-i); if(j>=sz){ break; }elseif(hand[j] !=hand[j-1] +1){ lst.push_back(0); } i=j; } returnvalid(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，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
