LeetCode Split Array into Consecutive Subsequences

原题链接在这里：https://leetcode.com/problems/split-array-into-consecutive-subsequences/description/

题目：

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,

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]

题解：

对于当前distinct数字 cur, 保存以它结尾的长度1, 2, 和>=3的subsequences数目. count是cur的frequency.

当前个distinct值pre, 如果pre+1 != cur, 说明cur只能用来起头新的subsequence, 但如果前面的噗p1或p2不为0, 说明前面的只能组成长度为1或2的subsequence, return false.

如果pre+1 == cur, 说明cur可以用来append前面的subsequence.

前面长度为1的subsequence个数就是现在长度为2的subsequence个数. c2=p1.

前面长度为2的subsequence个数就是现在长度为3的subsequence个数. 若前面有长度大于3的, 这里可以继续append组成长度大于4的. 但前提是先满足前面长度1和2后剩下的. c3 = p2 + Math.min(p3, count-(p1+p2)).

也可以开始组成新的长度为1的subsequence, 前提是前面用剩下的. c1 = Math.max(0, count-(p1+p2+p3)).

Time Complexity: O(nums.length). Space: O(1).

AC Java:

 class Solution {

     public boolean isPossible(int[] nums) {

         int pre = Integer.MIN_VALUE;

         int p1 = 0;

         int p2 = 0;

         int p3 = 0;

         int cur = 0;

         int c1 = 0;

         int c2 = 0;

         int c3 = 0;

         int count = 0;

         int i = 0;

         while(i<nums.length){

             for(cur = nums[i], count = 0; i<nums.length && cur==nums[i]; i++){

                 count++;

             }

             if(cur != pre+1){

                 if(p1!=0 || p2!=0){

                     return false;

                 }

                 c1 = count;

                 c2 = 0;

                 c3 = 0;

             }else{

                 if(count < p1+p2){

                     return false;

                 }

                 c1 = Math.max(0, count-(p1+p2+p3));

                 c2 = p1;

                 c3 = p2 + Math.min(p3, count-(p1+p2));

             }

             pre=cur;

             p1=c1;

             p2=c2;

             p3=c3;

         }

         return p1==0 && p2==0;

     }

 }

如果给出的nums不是sorted的, 则可先统计数字的frequency.

再扫一遍nums array, 对于每个数字要么能承上, 要么能启下.

都不能就return false.

Time Complexity: O(nums.length).

Space: O(nums.length).

AC Java:

 class Solution {

     public boolean isPossible(int[] nums) {

         HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

         for(int num : nums){

             hm.put(num, hm.getOrDefault(num, 0)+1);

         }

         HashMap<Integer, Integer> append = new HashMap<Integer, Integer>();

         for(int num : nums){

             if(hm.get(num) == 0){

                 continue;

             }

             if(append.getOrDefault(num, 0) > 0){

                 append.put(num, append.get(num)-1);

                 append.put(num+1, append.getOrDefault(num+1, 0)+1);

             }else if(hm.getOrDefault(num+1, 0) > 0 && hm.getOrDefault(num+2, 0) > 0){

                 hm.put(num+1, hm.get(num+1)-1);

                 hm.put(num+2, hm.get(num+2)-1);

                 append.put(num+3, append.getOrDefault(num+3, 0)+1);

             }else{

                 return false;

             }

             hm.put(num, hm.get(num)-1);

         }

         return true;

     }

 }

巴特西

LeetCode Split Array into Consecutive Subsequences

最新文章

热门文章