【每日算法Day 103】老题新做，几乎不会有人想到的解法，它来了
【每日算法Day 103】老题新做，几乎不会有人想到的解法，它来了
前两天 Day 99 的时候，做过一道顺子的题目，当时有一个网友的妙解有点没看懂，今天我来给大家详细讲解一下。
题目链接
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，那就说明整副牌可以构成顺子，完美！
时间复杂度是 ，这题数据不强也可以过的。
有没有办法优化呢？其实更新 total 这一步可以优化掉 这个复杂度，直接 更新 total 。
- 首先遍历
1，因为1只有一张，那么如果它和后面牌能构成顺子，那么2, 3至少要有一张才行。但是这里我们不对这几张牌的total加上一，而是在这个顺子结尾的下一张牌处的deltas减去1。 - 然后遍历
2，那么这时候没有total了，怎么计算应该扣除多少前面顺子需要的2呢？其实只需要用前一张牌的牌数加上当前的deltas值就行了。为什么呢？前面一张牌有多少张，你当前这张就得至少有那么多去构成顺子，但是如果前面一张牌是某些顺子的结尾，你还得扣掉一些，而扣掉的数值正好就是当前的deltas，这在前面顺子的开头处已经记录过了。 - 后面操作类似，就不详细阐述了。
这种方法精髓就在于，不需要直接更新所有的 total 值，只需要在顺子结尾下一个元素处更新一下 deltas 就行了，每次的 total 可以通过上一张牌的 count 和当前的 deltas 推算出来。
这样总的时间复杂度就降到了 ，近似 。
不得不说，这个方法还是非常妙的，反正我是一下子想不到的，看了代码都想了很久才想通。
代码
暴力更新（c++）
class Solution {
public:
bool valid(vector<int> &count, int W) {
int n = count.size();
vector<int> total(n, 0);
for (int i = 0; i < n; ++i) {
if (count[i] > total[i]) {
int delta = count[i] - total[i];
for (int j = i; j < i+W && j < n; ++j) total[j] += delta;
} else if (count[i] < total[i]) {
return false;
}
}
return true;
}
bool isNStraightHand(vector<int>& hand, int W) {
int n = hand.size();
if (W == 1) return true;
if (n%W) return false;
sort(hand.begin(), hand.end());
vector<int> count;
int i = 0, j = 0;
while (i < n) {
while (j < n && hand[i] == hand[j]) j++;
count.push_back(j-i);
if (j >= n) break;
else if (hand[j] != hand[j-1]+1) count.push_back(0);
i = j;
}
count.push_back(0);
return valid(count, W);
}
};优化（c++）
class Solution {
public:
bool valid(vector<int> &count, int W) {
int n = count.size(), pre = 0;
vector<int> deltas(n, 0);
for (int i = 0; i < n; ++i) {
pre += deltas[i];
if (pre < count[i]) {
int delta = count[i] - pre;
pre = count[i];
if (i + W < n) deltas[i+W] -= delta;
} else if (pre > count[i]) {
return false;
}
}
return true;
}
bool isNStraightHand(vector<int>& hand, int W) {
int n = hand.size();
if (W == 1) return true;
if (n%W) return false;
sort(hand.begin(), hand.end());
vector<int> count;
int i = 0, j = 0;
while (i < n) {
while (j < n && hand[i] == hand[j]) j++;
count.push_back(j-i);
if (j >= n) break;
else if (hand[j] != hand[j-1]+1) count.push_back(0);
i = j;
}
count.push_back(0);
return valid(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/