谁能想到，斗地主也能玩出算法
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 659. Split Array into Consecutive Subsequences | 659. 分割数组为连续子序列 | 🟠 |
———–
斗地主中，大小连续的牌可以作为顺子，有时候我们把对子拆掉，结合单牌，可以组合出更多的顺子，可能更容易赢。
那么如何合理拆分手上的牌，合理地拆出顺子呢？我们今天看一道非常有意思的算法题，连续子序列的划分问题。
这是力扣第 659 题「 分割数组为连续子序列」，题目很简单：
给你输入一个升序排列的数组 nums（可能包含重复数字），请你判断 nums 是否能够被分割成若干个长度至少为 3 的子序列，每个子序列都由连续的整数组成。
函数签名如下：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
boolean isPossible(List<Integer> nums);
bool isPossible(vector<int>& nums);
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
def isPossible(nums: List[int]) -> bool
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
func isPossible(nums []int) bool {
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {};
比如题目举的例子，输入 nums = [1,2,3,3,4,4,5,5]，算法返回 true。
因为 nums 可以被分割成 [1,2,3,4,5] 和 [3,4,5] 两个包含连续整数子序列。
但如果输入 nums = [1,2,3,4,4,5]，算法返回 false，因为无法分割成两个长度至少为 3 的连续子序列。
对于这种涉及连续整数的问题，应该条件反射地想到排序，不过题目说了，输入的 nums 本就是排好序的。
那么，我们如何判断 nums 是否能够被划分成若干符合条件的子序列呢？
类似前文
回溯算法进行集合划分，我们想把 nums 的元素划分到若干个子序列中，其实就是下面这个代码逻辑：
for (int v : nums) {
if (...) {
// 将 v 分配到某个子序列中
} else {
// 实在无法分配 v
return false;
}
return true;
}
关键在于，我们怎么知道当前元素 v 如何进行分配呢？
肯定得分情况讨论，把情况讨论清楚了，题目也就做出来了。
总共有两种情况：
1、当前元素 v 自成一派，「以自己开头」构成一个长度至少为 3 的序列。
比如输入 nums = [1,2,3,6,7,8]，遍历到元素 6 时，它只能自己开头形成一个符合条件的子序列 [6,7,8]。
2、当前元素 v 接到已经存在的子序列后面。
比如输入 nums = [1,2,3,4,5]，遍历到元素 4 时，它只能接到已经存在的子序列 [1,2,3] 后面。它没办法自成开头形成新的子序列，因为少了个 6。
但是，如果这两种情况都可以，应该如何选择？
比如说，输入 nums = [1,2,3,4,5,5,6,7]，对于元素 4，你说它应该形成一个新的子序列 [4,5,6] 还是接到子序列 [1,2,3] 后面呢？
显然，nums 数组的正确划分方法是分成 [1,2,3,4,5] 和 [5,6,7]，所以元素 4 应该优先判断自己是否能够接到其他序列后面，如果不行，再判断是否可以作为新的子序列开头。
这就是整体的思路，想让算法代码实现这两个选择，需要两个哈希表来做辅助：
freq 哈希表帮助一个元素判断自己是否能够作为开头，need 哈希表帮助一个元素判断自己是否可以被接到其他序列后面。
freq 记录每个元素出现的次数，比如 freq[3] == 2 说明元素 3 在 nums 中出现了 2 次。
那么如果我发现 freq[3], freq[4], freq[5] 都是大于 0 的，那就说明元素 3 可以作为开头组成一个长度为 3 的子序列。
need 记录哪些元素可以被接到其他子序列后面。
比如说现在已经组成了两个子序列 [1,2,3,4] 和 [2,3,4]，那么 need[5] 的值就应该是 2，说明对元素 5 的需求为 2。
明白了这两个哈希表的作用，我们就可以看懂解法了：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
/**
* 检查序列是否可以被分成长度至少为 3 的连续子序列
* 每个子序列中不同的整数数量要相同
*
* @param nums 检查的序列
* @return 序列能够被组成子序列返回 true，否则返回 false
*/
public boolean isPossible(int[] nums) {
// 维护每个数在 nums 数组中出现的次数
HashMap<Integer, Integer> freq = new HashMap<>();
// 维护每个数作为结尾的连续子序列的需求量
HashMap<Integer, Integer> need = new HashMap<>();
// 遍历 nums 数组统计每个数在 nums 数组中出现的次数
for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);
for (int v : nums) {
// 如果 v 已经被用到其他子序列中则无法再被用到
if (freq.get(v) == 0) {
continue;
}
// 尝试将 v 接到之前的某个序列后面
if (need.containsKey(v) && need.get(v) > 0) {
// v 可以接到之前的某个序列后面
freq.put(v, freq.get(v) - 1);
need.put(v, need.get(v) - 1);
need.put(v + 1, need.getOrDefault(v + 1, 0) + 1);
} else if (freq.containsKey(v) && freq.get(v) > 0 && freq.containsKey(v + 1) && freq.get(v + 1) > 0 && freq.containsKey(v + 2) && freq.get(v + 2) > 0) {
// 第二种情况，新建一个长度为 3 的子序列 [v, v+1, v+2]
freq.put(v, freq.get(v) - 1);
freq.put(v + 1, freq.get(v + 1) - 1);
freq.put(v + 2, freq.get(v + 2) - 1);
need.put(v + 3, need.getOrDefault(v + 3, 0) + 1);
} else {
// 两种情况都不符合，则无法分配
return false;
}
}
return true;
}
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq, need;
// 统计 nums 中元素的频率
for (int v : nums) freq[v]++;
for (int v : nums) {
if (freq[v] == 0) {
// 已经被用到其他子序列中
continue;
}
// 先判断 v 是否能接到其他子序列后面
if (need.count(v) && need[v] > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 对 v 的需求减一
need[v]--;
// 对 v + 1 的需求加一
need[v + 1]++;
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 对 v + 3 的需求加一
need[v + 3]++;
} else {
// 两种情况都不符合，则无法分配
return false;
}
}
return true;
}
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
def isPossible(nums: List[int]) -> bool:
# 使用字典统计 nums 中元素的频率
freq, need = {}, {}
for v in nums:
freq[v] = freq.get(v, 0) + 1
for v in nums:
if freq[v] == 0:
# 已经被用到其他子序列中
continue
if v in need and need[v] > 0:
# v 可以接到之前的某个序列后面
freq[v] -= 1
need[v] -= 1
need[v + 1] = need.get(v + 1, 0) + 1
elif freq[v] > 0 and freq.get(v + 1, 0) > 0 and freq.get(v + 2, 0) > 0:
# 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v] -= 1
freq[v + 1] -= 1
freq[v + 2] -= 1
need[v + 3] = need.get(v + 3, 0) + 1
else:
# 两种情况都不符合，则无法分配
return False
return True
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
func isPossible(nums []int) bool {
freq, need := make(map[int]int), make(map[int]int)
// 统计 nums 中元素的频率
for _, v := range nums {
freq[v]++
}
for _, v := range nums {
if freq[v] == 0 {
// 已经被用到其他子序列中
continue
}
// 先判断 v 是否能接到其他子序列后面
if n, ok := need[v]; ok && n > 0 {
// v 可以接到之前的某个序列后面
freq[v]--
// 对 v 的需求减一
need[v]--
// 对 v + 1 的需求加一
need[v + 1]++
} else if freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0 {
// 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--
freq[v + 1]--
freq[v + 2]--
// 对 v + 3 的需求加一
need[v + 3]++
} else {
// 两种情况都不符合，则无法分配
return false
}
}
return true
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {
var freq = {};
var need = {};
// 统计 nums 中元素的频率
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (v in freq) {
freq[v]++;
} else {
freq[v] = 1;
}
}
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (freq[v] == 0) {
// 已经被用到其他子序列中
continue;
}
// 先判断 v 是否能接到其他子序列后面
if (v in need && need[v] > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 对 v 的需求减一
need[v]--;
// 对 v + 1 的需求加一
if (need[v + 1]) {
need[v + 1]++;
} else {
need[v + 1] = 1;
}
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 对 v + 3 的需求加一
if (need[v + 3]) {
need[v + 3]++;
} else {
need[v + 3] = 1;
}
} else {
// 两种情况都不符合，则无法分配
return false;
}
}
return true;
};
至此，这道题就解决了。
那你可能会说，斗地主里面顺子至少要 5 张连续的牌，我们这道题只计算长度最小为 3 的子序列，怎么办？
很简单，把我们的 else if 分支修改一下，连续判断 v 之后的连续 5 个元素就行了。
那么，我们再难为难为自己，如果我想要的不只是一个布尔值，我想要你给我把子序列都打印出来，怎么办？
其实这也很好实现，只要修改 need，不仅记录对某个元素的需求个数，而且记录具体是哪些子序列产生的需求：
// need[6] = 2 说明有两个子序列需要 6
unordered_map<int, int> need;
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
unordered_map<int, vector<vector<int>>> need;
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// need[6] = 2 说明有两个子序列需要 6
unordered_map<int, int> need;
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
unordered_map<int, vector<vector<int>>> need;
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# need[6] = 2 说明有两个子序列需要 6
need = {}
# need[6] = [
# [3,4,5],
# [2,3,4,5],
# ]
# 记录哪两个子序列需要 6
need = {}
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// need[6] = 2 说明有两个子序列需要 6
need := make(map[int]int)
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// 记录哪两个子序列需要 6
need := make(map[int][][]int)
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var need = new Map(); // or {}
need.set(6, 2); // 说明有两个子序列需要 6
var need = new Map(); // or {}
need.set(6, [
[3, 4, 5],
[2, 3, 4, 5]
]);
// 记录哪两个子序列需要 6
这样，我们稍微修改一下之前的代码就行了：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
/**
* 检查给定的数组是否可以分割成若干子序列，要求每个子序列长度 >= 3，
* 相同数字不能出现在同一个子序列中。
*
* 思路：贪心 + 哈希表，以哈希表 {number: frequency} 维护每个数字出现的频率，
* 再以哈希表 {end: list} 维护每个以 end 为结尾的子序列，
* 尝试向已有的子序列中添加数字，若没有已有子序列，尝试在 nums 中新建一个包含
* 连续的三个数的子序列。
*
* 时间复杂度：O(N)
* 空间复杂度：O(N)
*/
public boolean isPossible(int[] nums) {
// 统计每个数字出现的频率
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);
// 以哈希表 {end: list} 维护每个以 end 为结尾的子序列
Map<Integer, List<List<Integer>>> need = new HashMap<>();
for (int v : nums) {
if (freq.get(v) == 0) {
continue;
}
if (need.containsKey(v) && !need.get(v).isEmpty()) {
// 如果已经存在以 v - 1 结尾的子序列，就将当前 v 接到它后面
freq.put(v, freq.get(v) - 1);
// 取出需要 v 的最短子序列
List<Integer> seq = need.get(v).remove(need.get(v).size() - 1);
seq.add(v);
// 将更新后的子序列添加到 map 中
if (!need.containsKey(v + 1)) {
need.put(v + 1, new ArrayList<>());
}
need.get(v + 1).add(seq);
} else if (freq.get(v) > 0 && freq.getOrDefault(v + 1, 0) > 0
&& freq.getOrDefault(v + 2, 0) > 0) {
// 否则如果存在 v, v + 1, v + 2，就新建一个以 v, v + 1, v + 2 为顺序的子序列
freq.put(v, freq.get(v) - 1);
freq.put(v + 1, freq.get(v + 1) - 1);
freq.put(v + 2, freq.get(v + 2) - 1);
List<Integer> seq = new ArrayList<>();
seq.add(v);
seq.add(v + 1);
seq.add(v + 2);
// 将更新后的子序列添加到 map 中
if (!need.containsKey(v + 3)) {
need.put(v + 3, new ArrayList<>());
}
need.get(v + 3).add(seq);
} else {
// 如果既没有可以接到的子序列，也无法新建新的子序列，则返回 false
return false;
}
}
// 遍历所有序列，检查它们的长度是否都大于等于 3，如果有一个短于 3 则返回 false
for (List<List<Integer>> allSeq : need.values()) {
for (List<Integer> seq : allSeq) {
if (seq.size() < 3) {
return false;
}
}
}
// 如果所有序列长度都大于等于 3，则返回 true
return true;
}
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq;
unordered_map<int, vector<vector<int>>> need;
for (int v : nums) freq[v]++;
for (int v : nums) {
if (freq[v] == 0) {
continue;
}
if (need.count(v) && need[v].size() > 0) {
// v 可以接到之前的某个序列后面
freq[v]--;
// 随便取一个需要 v 的子序列
vector<int> seq = need[v].back();
need[v].pop_back();
// 把 v 接到这个子序列后面
seq.push_back(v);
// 这个子序列的需求变成了 v + 1
need[v + 1].push_back(seq);
} else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
// 可以将 v 作为开头
freq[v]--;
freq[v + 1]--;
freq[v + 2]--;
// 新建一个长度为 3 的子序列 [v,v + 1,v + 2]
vector<int> seq{v, v + 1, v + 2};
// 对 v + 3 的需求加一
need[v + 3].push_back(seq);
} else {
return false;
}
}
// 打印切分出的所有子序列
for (auto it : need) {
for (vector<int>& seq : it.second) {
for (int v : seq) {
cout << v << " ";
}
cout << endl;
}
}
return true;
}
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
from typing import List
# 定义函数isPossible，参数为一个整型列表，返回值为布尔型
def isPossible(nums: List[int]) -> bool:
# 定义标准型字典freq，来统计nums中元素出现的次数
freq = {}
# 定义映射型字典need，来记录nums中元素可以组成的子序列
need = {}
# 统计nums中元素的出现次数
for v in nums:
freq[v] = freq.get(v, 0) + 1
# 遍历nums中的元素
for v in nums:
# 如果 freq[v] 为0，则跳过
if freq[v] == 0:
continue
# 如果need中有以v为结尾的子序列，则将v接到最后一个序列之后
if v in need and len(need[v]) > 0:
# 减少v的出现次数
freq[v] -= 1
# 取出需要v的子序列
seq = need[v].pop()
# 将v加到该子序列最后
seq.append(v)
# 设置需求为v+1子序列中
need[v+1] = need.get(v+1, []) + [seq]
# 如果由 v,v+1, v+2 三个元素组成的子序列在freq中都出现
elif freq[v] > 0 and freq.get(v+1, 0) > 0 and freq.get(v+2, 0) > 0:
# 减小 v, v+1, v+2 出现的次数
freq[v] -= 1
freq[v+1] -= 1
freq[v+2] -= 1
# 新建一个由v, v+1, v+2组成的子序列
seq = [v, v+1, v+2]
# v+3子序列需要加入以后的子序列列表中
need[v+3] = need.get(v+3, []) + [seq]
else:
return False
# 打印出路径
for k, v in need.items():
for seq in v:
for num in seq:
print(num, end=' ')
print()
return True
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
// Convert this CPP code to Go.
// Don't modify Chinese comments, you should retain them.
// Restore all the comments in your code.
func isPossible(nums []int) bool {
// 使用两个map，一个记录每个数字的数量，一个记录需要哪些子序列
freq := make(map[int]int)
need := make(map[int][][]int)
// 统计频率
for _, v := range nums {
freq[v]++
}
// 遍历数组
for _, v := range nums {
// 如果已经被凑成子序列了，跳过
if freq[v] == 0 {
continue
}
// 如果可以接到之前的某个序列后面
if n, ok := need[v]; ok && len(n) > 0 {
// 减去一个 v
freq[v]--
// 随便取一个需要 v 的子序列
seq := need[v][len(need[v])-1]
need[v] = need[v][:len(need[v])-1]
// 把 v 接到这个子序列后面
seq = append(seq, v)
// 这个子序列的需求变成了 v + 1
need[v+1] = append(need[v+1], seq)
// 如果可以将 v 作为开头
} else if freq[v] > 0 && freq[v+1] > 0 && freq[v+2] > 0 {
// 都减去一次即可
freq[v]--
freq[v+1]--
freq[v+2]--
// 新建一个长度为 3 的子序列 [v, v + 1, v + 2]
need[v+3] = append(need[v+3], []int{v, v + 1, v + 2})
} else {
return false
}
}
// 打印所有子序列
for k, v := range need {
for _, seq := range v {
for _, sub := range seq {
fmt.Printf("%d ", sub)
}
fmt.Println()
}
}
return true
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var isPossible = function(nums) {
var freq = new Map();
var need = new Map();
nums.forEach(function(v) {
freq.set(v, freq.get(v) + 1 || 1);
});
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (freq.get(v) == 0) {
continue;
}
if (need.has(v) && need.get(v).length > 0) {
// v 可以接到之前的某个序列后面
var seq = need.get(v)[need.get(v).length - 1];
need.get(v).pop();
// 把 v 接到这个子序列后面
seq.push(v);
// 这个子序列的需求变成了 v + 1
if (!need.has(v + 1)) {
need.set(v + 1, []);
}
need.get(v + 1).push(seq);
} else if (freq.get(v) > 0 && freq.get(v + 1) > 0 && freq.get(v + 2) > 0) {
// 可以将 v 作为开头
freq.set(v, freq.get(v) - 1);
freq.set(v + 1, freq.get(v + 1) - 1);
freq.set(v + 2, freq.get(v + 2) - 1);
// 新建一个长度为 3 的子序列 [v,v + 1,v + 2]
var seq = [v, v + 1, v + 2];
// 对 v + 3 的需求加一
if (!need.has(v + 3)) {
need.set(v + 3, []);
}
need.get(v + 3).push(seq);
} else {
return false;
}
}
// 打印切分出的所有子序列
need.forEach(function(value, key) {
value.forEach(function(seq) {
console.log(seq.join(" "));
});
});
return true;
};
这样，我们记录具体子序列的需求也实现了。
如果本文对你有帮助，点个赞，微信会给你推荐更多相似文章。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释