题目链接
LeetCode 846. 一手顺子[1]
往期回顾：
【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念[2]
题目描述
卢本伟有一手（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 的组。
题解
这题的妙解来自于题解区网友 zhanzq，当时没怎么看懂，现在我来给大家讲解一下。
网友题解地址[3]
我们用一个例子来讲解：
假设 W = 3，给定的手牌正好是三个顺子：[1,2,3], [2,3,4], [6,7,8] 。
那么我们统计出每张牌的数量，并且从小到大排序，记为 count ，这里就是 [1,2,2,1,0,1,1,1,0] ，并且在数字不连续处和末尾补 0 （作用后面会详细说）。
- 然后从小到大遍历每一张牌，首先
1只有一张，那么如果它和后面牌能构成顺子，那么2, 3至少要有一张才行，于是total数组后面两个位置都加上1。 - 然后遍历到
2，因为2的数量是大于该位置处的total值的，所以2的数量足够满足前面的牌顺子要求。此外2还会多出一张，那么后面两个位置至少要有一张牌才行，于是total后面两个位置再加上1。 - 然后遍历
3, 4，发现数量正好都等于total，那说明它俩正好和前面的牌构成顺子，一点都不会多余。 - 然后遍历到
0了，这就说明和前面的牌断开了。如果这时候total不为0，就说明中间缺失了一些牌，前面存在顺子没法补足结尾。而如果最开始没有填充0的话，就没有办法判断这里的牌是否和前面连续的，你就有可能把6这张牌直接接到4后面组成顺子了。 - 然后遍历
6, 7, 8同理，在对应位置处更新total就行了。 - 最后遍历
0，发现total也是0，那就说明整副牌可以构成顺子，完美！
- 首先遍历
1，因为1只有一张，那么如果它和后面牌能构成顺子，那么2, 3至少要有一张才行。但是这里我们不对这几张牌的total加上一，而是在这个顺子结尾的下一张牌处的deltas减去1。 - 然后遍历
2，那么这时候没有total了，怎么计算应该扣除多少前面顺子需要的2呢？其实只需要用前一张牌的牌数加上当前的deltas值就行了。为什么呢？前面一张牌有多少张，你当前这张就得至少有那么多去构成顺子，但是如果前面一张牌是某些顺子的结尾，你还得扣掉一些，而扣掉的数值正好就是当前的deltas，这在前面顺子的开头处已经记录过了。 - 后面操作类似，就不详细阐述了。
这种方法精髓就在于，不需要直接更新所有的 total 值，只需要在顺子结尾下一个元素处更新一下 deltas 就行了，每次的 total 可以通过上一张牌的 count 和当前的 deltas 推算出来。
不得不说，这个方法还是非常妙的，反正我是一下子想不到的，看了代码都想了很久才想通。
代码
暴力更新（c++）
classSolution { public: boolvalid(vector<int>&count, intW) { intn=count.size(); vector<int>total(n, 0); for (inti=0; i<n; ++i) { if (count[i] >total[i]) { intdelta=count[i] -total[i]; for (intj=i; j<i+W&&j<n; ++j) total[j] +=delta; } elseif (count[i] <total[i]) { returnfalse; } } returntrue; } boolisNStraightHand(vector<int>&hand, intW) { intn=hand.size(); if (W==1) returntrue; if (n%W) returnfalse; sort(hand.begin(), hand.end()); vector<int>count; inti=0, j=0; while (i<n) { while (j<n&&hand[i] ==hand[j]) j++; count.push_back(j-i); if (j>=n) break; elseif (hand[j] !=hand[j-1]+1) count.push_back(0); i=j; } count.push_back(0); returnvalid(count, W); } };
优化（c++）
classSolution { public: boolvalid(vector<int>&count, intW) { intn=count.size(), pre=0; vector<int>deltas(n, 0); for (inti=0; i<n; ++i) { pre+=deltas[i]; if (pre<count[i]) { intdelta=count[i] -pre; pre=count[i]; if (i+W<n) deltas[i+W] -=delta; } elseif (pre>count[i]) { returnfalse; } } returntrue; } boolisNStraightHand(vector<int>&hand, intW) { intn=hand.size(); if (W==1) returntrue; if (n%W) returnfalse; sort(hand.begin(), hand.end() ); vector<int>count; inti=0, j=0; while (i<n) { while (j<n&&hand[i] ==hand[j]) j++; count.push_back(j-i); if (j>=n) break; elseif (hand[j] !=hand[j-1]+1) count.push_back(0); i=j; } count.push_back(0); returnvalid(count, W); } };
参考资料
[1]
LeetCode 846. 一手顺子: https://leetcode-cn.com/problems/hand-of-straights/
[2]
【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念: https://godweiyang.com/2020/04/13/leetcode-846/
[3]
网友题解地址: https://leetcode-cn.com/problems/hand-of-straights/solution/onlognsuan-fa-by-zhanzq/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
