LintCode 1103 Split Array into Consecutive Subsequences (斗地主算法好题)

1103 · Split Array into Consecutive Subsequences
Algorithms
Medium
Accepted Rate
53%

Description
Solution10
Notes
Discuss16
Leaderboard
Record

Description
Given an integer array nums. You need to split nums into several (at least 1) subsequences, where each subsequence contains at least 3 consecutive integers.

Return whether you can make such a split.

nums.length will be in the range of [1, 10000].
nums has been sorted in ascending order and may contain duplicates.
If you can make such a split, each element of nums must and can only exist in one of subsequences.
A legitimate subsequence can only consist of consecutive elements and cannot contain duplicate elements.
Example
Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation: You can split them into two subsequences:
[1, 2, 3]
[3, 4, 5]
Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation: You can split them into two subsequences:
[1, 2, 3, 4, 5]
[3, 4, 5]
Example 3:

Input: [1,2,3,4,4,5]
Output: False
Explanation: We can’t split them into several legal subsequences.
Tags
Company
Google

解法1：参考的labuladong的解法。

1. freq在需要创建新的序列时候用，need在判断是否需要连到某个已有序列的时候用。
2. 一个关键是如果某个数又能连到某个已有序列，又能新创建一个序列的时候，选哪个？应该选连到某个已有序列！
   举例：[1,2,3,4,4,5,6]。第一个4可以连到[1,2,3]后面，也可以新开一个[4,5,6]。
   前面的做法会得到[1,2,3,4]和[4,5,6]，后面的做法会得到[1,2,3],[4,5,6]，然后还有一个4用不掉。
   举例：[1,2,3,4,5,6]。虽然这里遇到4的时候新创建一个序列也可以，因为会得到[1,2,3]和[4,5,6]。
   但是我们把4连到[1,2,3]后面也对，因为最后会得到[1,2,3,4,5,6]。
   总之，尽量把某个数连到某个已有序列后。

class Solution {
public:
    /**
     * @param nums: a list of integers
     * @return: return a boolean
     */
    bool isPossible(vector<int> &nums) {
        map<int, int> freq; //<num, freq>
        for (auto n : nums) freq[n]++;
        map<int,int> needed; //<num, # of needed>
        for (auto n : nums) {
            if (freq[n] == 0) continue; //已经被前面的序列消耗完了

            if (needed[n] > 0) { //可以直接接到某个序列的后面
                freq[n]--;
                needed[n]--;
                needed[n + 1]++;
            } else if (freq[n + 1] && freq[n + 2]) { //重启一个序列，注意freq[n]>0已经检查过了。
                freq[n]--;
                freq[n + 1]--;
                freq[n + 2]--;
                needed[n + 3]++;
            } else {
                return false;
            }
        }
        return true;
    }
};