# 谁能想到，斗地主也能玩出算法

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

659. Split Array into Consecutive Subsequences | 🟠 |

In the card game Dou Di Zhu, consecutive cards can be used as a straight. Sometimes, by breaking pairs and combining them with single cards, we can form more straights, which might increase our chances of winning.

So, how can we reasonably break up the cards in our hand to form straights? Today, we'll look at a very interesting algorithm problem: the partitioning of consecutive subsequences.

This is LeetCode problem #659, "Split Array into Consecutive Subsequences." The problem is straightforward:

You are given an **ascendingly sorted** array `nums`

(which may contain duplicate numbers). Your task is to determine if `nums`

can be split into several subsequences, each of which has a **length of at least 3** and consists of consecutive integers.

The function signature is as follows:

`boolean isPossible(int[] nums);`

`bool isPossible(vector<int>& nums);`

`def isPossible(nums: List[int]) -> bool:`

`func isPossible(nums []int) bool`

`var isPossible = function(nums) {}`

For example, consider the given input `nums = [1,2,3,3,4,4,5,5]`

. The algorithm returns true.

This is because `nums`

can be split into two subsequences of consecutive integers: `[1,2,3,4,5]`

and `[3,4,5]`

.

However, if the input is `nums = [1,2,3,4,4,5]`

, the algorithm returns false, as it cannot be split into two subsequences of at least length 3 with consecutive integers.

**For problems involving consecutive integers, sorting should be your first instinct.** But in this case, the problem states that the input `nums`

is already sorted.

So, how do we determine if `nums`

can be divided into several subsequences that meet the criteria?

Similar to the previous article on Backtracking for Set Partitioning, we want to partition the elements of `nums`

into several subsequences. The logic can be represented by the following code:

```
for (int v : nums) {
if (...) {
// assign v to a subsequence
} else {
// really cannot assign v
return false;
}
return true;
}
```

The key question is, how do we determine how to allocate the current element `v`

?

We need to discuss different scenarios. Once we clarify these scenarios, the problem can be solved.

There are two main scenarios:

**1. The current element v forms its own group, starting a sequence with a length of at least 3.**

For example, given `nums = [1,2,3,6,7,8]`

, when we reach the element `6`

, it can only start its own valid subsequence `[6,7,8]`

.

**2. The current element v is appended to an existing subsequence.**

For example, given `nums = [1,2,3,4,5]`

, when we reach the element `4`

, it can only be appended to the existing subsequence `[1,2,3]`

. It cannot start a new subsequence because there is no `6`

.

But what if both scenarios are possible? How do we choose?

For instance, given `nums = [1,2,3,4,5,5,6,7]`

, for the element `4`

, should it start a new subsequence `[4,5,6]`

or be appended to the subsequence `[1,2,3]`

?

Clearly, the correct way to split the `nums`

array is into `[1,2,3,4,5]`

and `[5,6,7]`

, so the element `4`

should **first check if it can be appended to another sequence**. If not, then check if it can start a new subsequence.

This is the overall approach. To implement these choices in the algorithm, we need two hash tables for assistance:

- The
`freq`

hash table helps an element determine if it can start a new sequence. - The
`need`

hash table helps an element determine if it can be appended to an existing sequence.

** freq records the frequency of each element**, for example,

`freq[3] == 2`

means the element `3`

appears twice in `nums`

.If we find that `freq[3], freq[4], freq[5]`

are all greater than 0, it means element `3`

can start a sequence of length 3.

** need records which elements can be appended to existing subsequences**.

For example, if we already have two subsequences `[1,2,3,4]`

and `[2,3,4]`

, then `need[5]`

should be 2, indicating that there is a demand for two `5`

s.

Understanding the roles of these two hash tables allows us to comprehend the solution:

```
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Integer> need = new HashMap<>();
// count the frequency of elements in nums
for (int v : nums) {
freq.put(v, freq.getOrDefault(v, 0) + 1);
}
for (int v : nums) {
if (freq.get(v) == 0) {
// already used in other subsequences
continue;
}
// first determine if v can be appended to the end of other subsequences
if (need.containsKey(v) && need.get(v) > 0) {
// v can be appended to the end of a previous subsequence
freq.put(v, freq.get(v) - 1);
// decrease the need for v by one
need.put(v, need.get(v) - 1);
// increase the need for v + 1 by one
need.put(v + 1, need.getOrDefault(v + 1, 0) + 1);
} else if (freq.getOrDefault(v, 0) > 0 &&
freq.getOrDefault(v + 1, 0) > 0 &&
freq.getOrDefault(v + 2, 0) > 0) {
// create a new subsequence of length 3 starting with v: [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);
// increase the need for v + 3 by one
need.put(v + 3, need.getOrDefault(v + 3, 0) + 1);
} else {
// if neither of the two conditions is met, it cannot be allocated
return false;
}
}
return true;
}
}
```

```
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq;
unordered_map<int, int> need;
// count the frequency of elements in nums
for (int v : nums) {
++freq[v];
}
for (int v : nums) {
if (freq[v] == 0) {
// already used in other subsequences
continue;
}
// first determine if v can be appended to other subsequences
if (need.count(v) && need[v] > 0) {
// v can be appended to a previous subsequence
freq[v] = freq[v] - 1;
// decrease the need for v by one
need[v] = need[v] - 1;
// increase the need for v + 1 by one
need[v + 1] = need[v + 1] + 1;
} else if (freq[v] > 0 &&
freq[v + 1] > 0 &&
freq[v + 2] > 0) {
// create a new subsequence of length 3 starting with v: [v, v+1, v+2]
freq[v] = freq[v] - 1;
freq[v + 1] = freq[v + 1] - 1;
freq[v + 2] = freq[v + 2] - 1;
// increase the need for v + 3 by one
need[v + 3] = need[v + 3] + 1;
} else {
// if neither condition is met, it cannot be allocated
return false;
}
}
return true;
}
};
```

```
class Solution:
def isPossible(self, nums):
freq = {}
need = {}
# count the frequency of elements in nums
for v in nums:
freq[v] = freq.get(v, 0) + 1
for v in nums:
if freq.get(v) == 0:
# already used in other subsequences
continue
# first determine if v can be appended to other subsequences
if v in need and need[v] > 0:
# v can be appended to a previous subsequence
freq[v] = freq.get(v) - 1
# decrease the need for v by one
need[v] = need.get(v) - 1
# increase the need for v + 1 by one
need[v + 1] = need.get(v + 1, 0) + 1
elif freq.get(v, 0) > 0 and \
freq.get(v + 1, 0) > 0 and \
freq.get(v + 2, 0) > 0:
# create a new subsequence of length 3 starting with v: [v, v+1, v+2]
freq[v] = freq[v] - 1
freq[v + 1] = freq[v + 1] - 1
freq[v + 2] = freq[v + 2] - 1
# increase the need for v + 3 by one
need[v + 3] = need.get(v + 3, 0) + 1
else:
# if neither condition is met, it cannot be allocated
return False
return True
```

```
func isPossible(nums []int) bool {
freq := make(map[int]int)
need := make(map[int]int)
// count the frequency of elements in nums
for _, v := range nums {
freq[v]++
}
for _, v := range nums {
if freq[v] == 0 {
// already used in other subsequences
continue
}
// first determine if v can be appended to other subsequences
if need[v] > 0 {
// v can be appended to a previous subsequence
freq[v]--
// decrease the need for v by one
need[v]--
// increase the need for v + 1 by one
need[v+1]++
} else if freq[v] > 0 &&
freq[v+1] > 0 &&
freq[v+2] > 0 {
// create a new subsequence of length 3 starting with v: [v, v+1, v+2]
freq[v]--
freq[v+1]--
freq[v+2]--
// increase the need for v + 3 by one
need[v+3]++
} else {
// if neither condition is met, it cannot be allocated
return false
}
}
return true
}
```

```
var isPossible = function(nums) {
var freq = new Map();
var need = new Map();
// count the frequency of elements in nums
for (let v of nums) {
freq.set(v, (freq.get(v) || 0) + 1);
}
for (let v of nums) {
if (freq.get(v) == 0) {
// already used in other subsequences
continue;
}
// first determine if v can be appended to other subsequences
if (need.has(v) && need.get(v) > 0) {
// v can be appended to a previous subsequence
freq.set(v, freq.get(v) - 1);
// decrease the need for v by one
need.set(v, need.get(v) - 1);
// increase the need for v + 1 by one
need.set(v + 1, (need.get(v + 1) || 0) + 1);
} else if ((freq.get(v) || 0) > 0 &&
(freq.get(v + 1) || 0) > 0 &&
(freq.get(v + 2) || 0) > 0) {
// create a new subsequence of length 3 starting with v: [v, v+1, v+2]
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);
// increase the need for v + 3 by one
need.set(v + 3, (need.get(v + 3) || 0) + 1);
} else {
// if neither condition is met, it cannot be allocated
return false;
}
}
return true;
};
```

So far, we have solved this problem.

You might be wondering, in the card game Dou Di Zhu, a straight requires at least 5 consecutive cards, but in our problem, we only calculate subsequences with a minimum length of 3. How do we handle this?

It's simple. Just modify our `else if`

branch to check for 5 consecutive elements after `v`

.

Now, let's challenge ourselves further. What if I don't just want a boolean value? What if I want you to print out all the subsequences? How do we do that?

Actually, this is also easy to implement. Just modify `need`

to not only record the required count for an element but also record which specific subsequences generate these requirements:

```
// need[6] = 2 means there are two subsequences that need 6
Map<Integer, Integer> need = new HashMap<>();
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// record which two subsequences need 6
Map<Integer, List<List<Integer>>> need = new HashMap<>();
```

```
// need[6] = 2 means there are two subsequences that need 6
unordered_map<int, int> need;
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// record which two subsequences need 6
unordered_map<int, vector<vector<int>>> need;
```

```
# need[6] = 2 means there are two subsequences that need 6
need = {}
# record which two subsequences need 6
need_sequences = {}
```

```
// need[6] = 2 means there are two subsequences that require 6
need := make(map[int]int)
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// record which two subsequences require 6
need := make(map[int][][]int)
```

```
// need[6] = 2 means there are two subsequences that need 6
var need = {};
// need[6] = {
// {3,4,5},
// {2,3,4,5},
// }
// record which two subsequences need 6
var needTwoSubsequences = {};
```

This way, we just need to slightly modify the previous code:

```
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, List<List<Integer>>> need = new HashMap<>();
// count the frequency of elements in nums
for (int v : nums) {
freq.put(v, freq.getOrDefault(v, 0) + 1);
}
for (int v : nums) {
if (freq.get(v) == 0) {
continue;
}
if (need.containsKey(v) && need.get(v).size() > 0) {
// v can be appended to a previous sequence
freq.put(v, freq.get(v) - 1);
// take any subsequence that needs v
List<Integer> seq = need.get(v).remove(need.get(v).size() - 1);
// append v to this subsequence
seq.add(v);
// the requirement of this subsequence becomes v + 1
need.computeIfAbsent(v + 1, k -> new ArrayList<>()).add(seq);
} else if (freq.getOrDefault(v, 0) > 0 &&
freq.getOrDefault(v + 1, 0) > 0 &&
freq.getOrDefault(v + 2, 0) > 0) {
// v can be used as the start
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);
// create a subsequence of length 3 [v, v + 1, v + 2]
List<Integer> seq = new ArrayList<>(Arrays.asList(v, v + 1, v + 2));
// increment the need for v + 3 by one
need.computeIfAbsent(v + 3, k -> new ArrayList<>()).add(seq);
} else {
return false;
}
}
// print all the subsequences that have been split out
for (Map.Entry<Integer, List<List<Integer>>> entry : need.entrySet()) {
for (List<Integer> seq : entry.getValue()) {
for (int val : seq) {
System.out.print(val + " ");
}
System.out.println();
}
}
return true;
}
}
```

```
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq;
unordered_map<int, vector<vector<int>>> need;
// count the frequency of elements in nums
for (int v : nums) {
freq[v] = freq[v] + 1;
}
for (int v : nums) {
if (freq[v] == 0) {
continue;
}
if (need.count(v) && need[v].size() > 0) {
// v can be appended to a previous sequence
freq[v] = freq[v] - 1;
// take any subsequence that needs v
vector<int> seq = need[v].back();
need[v].pop_back();
// append v to this subsequence
seq.push_back(v);
// the requirement of this subsequence becomes v + 1
need[v + 1].push_back(seq);
} else if (freq.count(v) > 0 &&
freq.count(v + 1) > 0 &&
freq.count(v + 2) > 0) {
// v can be used as the start
freq[v] = freq[v] - 1;
freq[v + 1] = freq[v + 1] - 1;
freq[v + 2] = freq[v + 2] - 1;
// create a subsequence of length 3 [v, v + 1, v + 2]
vector<int> seq = {v, v + 1, v + 2};
// increase the need for v + 3 by one
need[v + 3].push_back(seq);
} else {
return false;
}
}
// print all the subsequences that have been split out
for (auto& entry : need) {
for (vector<int>& seq : entry.second) {
for (int val : seq) {
cout << val << " ";
}
cout << endl;
}
}
return true;
}
};
```

```
class Solution:
def isPossible(self, nums):
freq = collections.Counter(nums)
need = collections.defaultdict(list)
# count the frequency of elements in nums
for v in nums:
if freq[v] == 0:
continue
if need[v]:
# v can be appended to a previous sequence
freq[v] -= 1
# take any subsequence that needs v
seq = need[v].pop()
# append v to this subsequence
seq.append(v)
# the requirement of this subsequence becomes v + 1
need[v + 1].append(seq)
elif freq[v] > 0 and freq[v + 1] > 0 and freq[v + 2] > 0:
# can use v as the start
freq[v] -= 1
freq[v + 1] -= 1
freq[v + 2] -= 1
# create a subsequence of length 3 [v, v + 1, v + 2]
seq = [v, v+1, v+2]
# increase the need for v + 3 by one
need[v + 3].append(seq)
else:
return False
# print all the subsequences that have been split out
for v, seqs in need.items():
for seq in seqs:
print(' '.join(map(str, seq)))
return True
```

```
func isPossible(nums []int) bool {
freq := map[int]int{}
need := map[int][][]int{}
// count the frequency of elements in nums
for _, v := range nums {
freq[v] = freq[v] + 1
}
for _, v := range nums {
if freq[v] == 0 {
continue
}
seqs, ok := need[v]
if ok && len(seqs) > 0 {
// v can be appended to a previous sequence
freq[v] = freq[v] - 1
// pick any subsequence that needs v
seq := need[v][len(need[v])-1]
need[v] = need[v][:len(need[v])-1]
// append v to this subsequence
seq = append(seq, v)
// the requirement of this subsequence becomes v + 1
need[v+1] = append(need[v+1], seq)
} else if freq[v] > 0 && freq[v+1] > 0 && freq[v+2] > 0 {
// v can be used as the beginning
freq[v] = freq[v] - 1
freq[v+1] = freq[v+1] - 1
freq[v+2] = freq[v+2] - 1
// create a subsequence of length 3 [v, v + 1, v + 2]
seq := []int{v, v + 1, v + 2}
// increment the need for v + 3
need[v+3] = append(need[v+3], seq)
} else {
return false
}
}
// print all subsequences that have been split out
for _, seqs := range need {
for _, seq := range seqs {
for _, val := range seq {
fmt.Print(val, " ")
}
fmt.Println()
}
}
return true
}
```

```
var isPossible = function(nums) {
let freq = new Map();
let need = new Map();
// count the frequency of elements in nums
for (let v of nums) {
freq.set(v, (freq.get(v) || 0) + 1);
}
for (let v of nums) {
if (freq.get(v) === 0) {
continue;
}
if (need.has(v) && need.get(v).length > 0) {
// v can be appended to a previous sequence
freq.set(v, freq.get(v) - 1);
// take any subsequence that needs v
let seq = need.get(v).pop();
// append v to this subsequence
seq.push(v);
// the requirement of this subsequence becomes v + 1
need.has(v + 1) || need.set(v + 1, []);
need.get(v + 1).push(seq);
} else if ((freq.get(v) || 0) > 0 &&
(freq.get(v + 1) || 0) > 0 &&
(freq.get(v + 2) || 0) > 0) {
// v can be used as the start
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);
// create a new subsequence of length 3 [v, v + 1, v + 2]
let seq = [v, v + 1, v + 2];
// increase the need for v + 3 by one
need.has(v + 3) || need.set(v + 3, []);
need.get(v + 3).push(seq);
} else {
return false;
}
}
// print all the subsequences that have been split out
for (let [key, value] of need.entries()) {
for (let seq of value) {
for (let val of seq) {
console.log(val + " ");
}
console.log('\n');
}
}
return true;
};
```

This way, we have also achieved the need to record specific subsequences.

If this article was helpful to you, give it a thumbs up, and WeChat will recommend more similar articles to you.