659.Split-Array-into-Consecutive-Subsequences

659. Split Array into Consecutive Subsequences

题目地址

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

题目描述

Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

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

Constraints:
1 <= nums.length <= 10000

代码

Appraoch #2 Greedy Fréquence HashMap

public boolean isPossible(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
    for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);
    for (int i : nums) {
        if (freq.get(i) == 0) continue;
        else if (appendfreq.getOrDefault(i, 0) > 0) {
          // freq[i]不为零，可以追加到子列
            appendfreq.put(i, appendfreq.get(i) - 1);
            appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);
        }   
        else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) { // 创建新的连续子列
            freq.put(i+1, freq.get(i+1) - 1);
            freq.put(i+2, freq.get(i+2) - 1);
            appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
        }
        else return false; // 单个数字，直接返回
        freq.put(i, freq.get(i) - 1);
    }
    return true;
}

Approach #2 Greedy

Say we have a count of each number, and let tails[x] be the number of chains ending right before x.

Time: O(N) && Space: O(N)

class Solution {
  public boolean isPossible(int[] nums) {
    Counter count = new Counter();
    Counter tails = new Counter();
    for (int x: nums)        count.add(x, 1);

    for (int x: nums) {
      if (count.get(x) == 0) {
        continue;
      } else if (tails.get(x) > 0) {
        tails.add(x, -1);
        tails.add(x+1, 1);
      } else if (count.get(x+1) > 0 && count.get(x+2) > 0) {
        count.add(x+1, -1);
        count.add(x+2, -1);
        tails.add(x+3, 1); 
      } else {
        return false;
      }
      count.add(x, -1);
    }
    return true;
  }
}

class Counter extends HashMap<Integer, Integer> {
  public int get(int k) {
    return containsKey(k) ? super.get(k) : 0;
  }

  public void add(int k, int v) {
    put(k, get(k) + v);
  }
}

Approach #1 Opening and Closing Events

Time: O(N) && Space: O(N)

class Solution {
  public boolean isPossible(int[] nums) {
        Integer prev = null;
    int prevCount = 0;
    Queue<Integer> starts = new LinkedList();
    int anchor = 0;

    for (int i = 0; i < nums.length; i++) {
      int t = nums[i];
      if (i == nums.length - 1 || nums[i+1] != t) {
        int count = i - anchor + 1;
        if (prev != null && t - prev != 1) {
          while (prevCount-- > 0) {
            if (prev < starts.poll() + 2)     return false;
            prev = null;
          }
        }

        if (prev == null || t - prev == 1) {
          while (prevCount > count) {
            prevCount--;
            if (t-1 < starts.poll() + 2)     return false;
          }
          while (prevCount++ < count) {
            starts.add(t);
          }
        }
        prev = t;
        preCount = count;
        anchor = i + 1;
      }
    }

    while (prevCount-- > 0) {
      if (nums[nums.length - 1] < starts.poll() + 2)     return false;
    }

    return true;
  }
}