LeetCode 659. Split Array into Consecutive Subsequences

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/08/19/LeetCode-659-Split-Array-into-Consecutive-Subsequences/

访问原文「LeetCode 659. Split Array into Consecutive Subsequences」

题目要求

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:

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

题意解析

给一个数组，数组中的数字按顺序排列并且存在重复数字，需要将这个数组拆分为几个子数组。子数组的至少包含3个连续数字。返回是否可以满足这样的拆分。

解法分析

首先进行参数的校验，只要数组为空或者数组的大小小于3直接返回false。

然后我们进行拆分。新建一个ListA，里面包含所有拆分结果。从数组的第一个数字开始遍历：

• 如果A为空，则新建一个列表B1将这个数字放进去，然后将B1放入A中
• 如果A不为空则遍历A中的每一个串，如果一个串的最后一个数字为当前数字减1并且这个串的大小小于3，则放入这个串中
• 如果满足最后一个数字为当前数字减1的串的大小都是大于等于3，则将这个数字放入第一个满足条件的串后
• 当这个串的最后一个数字小于当前数字减1并且串大小小于3直接返回false，这是因为给定的数组的是有序的，那么这个串永远不会满足条件
• 如果以上都没有进行处理则新建一个列表B2将这个数字放进去，然后将B2放入A中

最后轮询A中的每一个列表，是否满足条件。满足返回true，不满足返回false。

解题代码

public boolean isPossible(int[] nums) {
      if (nums == null || nums.length < 3) {
          return false;
      }
      List<List<Integer>> subsequences = new ArrayList<>();
      for (int num : nums) {
          if (subsequences.isEmpty()) {
              List<Integer> subsequence = new ArrayList<>();
              subsequence.add(num);
              subsequences.add(subsequence);
          } else {
              boolean inserted = false;
              List<Integer> firstSubsequence = null;
              for (List<Integer> subsequence : subsequences) {
                  if (subsequence.get(subsequence.size() - 1) == num - 1) {
                      if(null == firstSubsequence){
                          firstSubsequence = subsequence;
                      }
                      if(subsequence.size() < 3) {
                          subsequence.add(num);
                          inserted = true;
                          break;
                      }
                  }

                  if (subsequence.get(subsequence.size() - 1) < num - 1 && subsequence.size() < 3){
                      return false;
                  }
              }

              if (!inserted && firstSubsequence != null) {
                  firstSubsequence.add(num);
                  inserted = true;
              }

              if (!inserted) {
                  List<Integer> subsequence = new ArrayList<>();
                  subsequence.add(num);
                  subsequences.add(subsequence);
              }
          }
      }

      for (List<Integer> subsequence : subsequences) {
          if (subsequence.size() < 3) {
              return false;
          }
      }
      return true;
  }