[LeetCode] 659. Split Array into Consecutive Subsequences

[grandyang]

 

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive 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 consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

 

Example 3:

Input: [1,2,3,4,4,5]
Output: False

 

Note:

1. The length of the input is in range of [1, 10000]

 

博主第一眼看到这题，心想，我去，这不就是打牌么，什么挖坑，拐3，红桃4啊，3个起连，有时候排组合的好，就不用划单儿。这道题让将数组分割成多个连续递增的子序列，注意这里可能会产生歧义，实际上应该是分割成一个或多个连续递增的子序列，因为 [1,2,3,4,5] 也是正确的解。这道题就用贪婪解法就可以了，使用两个 HashMap，第一个 HashMap 用来建立数字和其出现次数之间的映射 freq，第二个用来建立可以加在某个连续子序列后的数字与其可以出现的次数之间的映射 need。对于第二个 HashMap，举个例子来说，就是假如有个连牌，比如对于数字1，此时检测数字2和3是否存在，若存在的话，表明有连牌 [1,2,3] 存在，由于后面可以加上4，组成更长的连牌，所以不管此时牌里有没有4，都可以建立 4->1 的映射，表明此时需要一个4。这样首先遍历一遍数组，统计每个数字出现的频率，然后开始遍历数组，对于每个遍历到的数字，首先看其当前出现的次数，如果为0，则继续循环；如果 need 中存在这个数字的非0映射，那么表示当前的数字可以加到某个连的末尾，将当前数字在 need 中的映射值自减1，然后将下一个连续数字的映射值加1，因为当 [1,2,3] 连上4后变成 [1,2,3,4] 之后，就可以连上5了，说明此时还需要一个5；如果不能连到其他子序列后面，则来看其是否可以成为新的子序列的起点，可以通过看后面两个数字的映射值是否大于0，都大于0的话，说明可以组成3连儿，于是将后面两个数字的映射值都自减1，还有由于组成了3连儿，在 need 中将末尾的下一位数字的映射值自增1；如果上面情况都不满足，说明该数字是单牌，只能划单儿，直接返回 false。最后别忘了将当前数字的 freq 映射值自减1。退出 for 循环后返回 true，参见代码如下：

 

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq, need;
        for (int num : nums) ++freq[num];
        for (int num : nums) {
            if (freq[num] == 0) continue;
            if (need[num] > 0) {
                --need[num];
                ++need[num + 1];
            } else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
                --freq[num + 1];
                --freq[num + 2];
                ++need[num + 3];
            } else return false;
            --freq[num];
        }
        return true;
    }
};

 

Github 同步地址：

#659

 

类似题目：

Top K Frequent Words

 

参考资料：

https://leetcode.com/problems/split-array-into-consecutive-subsequences/

https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106496/Java-O(n)-Time-O(n)-Space

https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106493/C%2B%2B-O(n)-solution-two-pass

https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106495/Java-O(n)-time-and-O(1)-space-solution-greedily-extending-shorter-subsequence

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

这个题是不是可以换种写法？ 不如直接考虑开多少个sequence，只用deque记录sequence的首数字， 如果 sequence在某个数字断了， 只需要看deque.back() 是否满足>=3 的条件即可。 每次加入新数字， 就看新数字的数目和deque的数目大小， 如果相等， 什么都不用做。 如果deque数目多，就需要从前面pop出去一些数字， 并检查是不是满足3这个条件。 如果新的数字多就开更多的sequence。算法beat 95%。

class Solution {
public:
    bool isPossible(vector& nums) {
      if(nums.size() < 3) return false;
      vector< int> cnts, values;    
      for(int i = 0, n= 0; i < nums.size(); ++i) {
        if(!values.empty() && nums[i] == values.back()){
          ++cnts.back();
        }else{
          values.push_back(nums[i]);
          cnts.push_back(1);
        }
      }
      deque q;
      for(int i =0; i< cnts.size(); ++i){
        int curr_num = values[i];
        int curr_cnt = cnts[i];
        if(q.empty()){
          for(int k = 0; k< cnts[i]; ++k) q.push_back(curr_num);
          continue;
        }
        if(curr_num > values[i-1]+1){ // no consecutive number, so start from scratch and check curr deque
          if(q.back()+3 > values[i-1]+1) 
            return false; 
          else{
            q.clear();
            for(int k = 0; k< cnts[i]; ++k) q.push_back(curr_num);
          }
        }else{
          if(curr_cnt < q.size()){
            int n_pop_front=q.size() - curr_cnt; 
            for(int j = 0; j < n_pop_front; ++j){
              int value = q.front();
              if(value + 3 > curr_num) return false;
              q.pop_front();
            }
          }else if(curr_cnt > q.size()){
            int extra = curr_cnt - q.size();
            for(int j= 0; j < extra; ++j){
              q.push_back(curr_num);    
            }
          }else{
            ;//doing nothing at all
          }
        }
      }
      return values.back()-q.back()+1>=3;
    }
};