This is the 9th day of my participation in the August Wen Challenge.More challenges in August

Difficulty: Medium

Title introduction

You are given an ascending array of integers, num (which may contain repeated numbers), and are asked to split them into one or more subsequences of at least length 3, each of which consists of consecutive integers.

Return true if the above segmentation can be done; Otherwise, return false.

Example 1:

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

Example 2:

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

Example 3:

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

Tip:

1 <= nums.length <= 10000

Idea 1:

Two dictionaries are used for recording, the first dictionary first counts the numbers in NUMS, and the second initializes. So there are two cases, (1) there’s a new number, and we’re going to see if there was a subsequence that was 1 less than that number, and we can put that number after that subsequence. If possible, update the end of the subsequence to the new number (2) to see if the new number is followed by two numbers, one and two more. If so, the degree of the two numbers is reduced by one, and a new subsequence ends with the new number appears. If neither can return False, the new number needs to be subtracted by 1 for each iteration. We started with “continue” because some of the numbers got used up.


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = collections.Counter(nums)
        end = collections.Counter()
        for num in nums:
            if count[num] == 0:
                continue
            elif end[num-1] > 0:
                end[num-1] -= 1
                end[num] += 1
            elif count[num+1] > 0 and count[num+2] > 0:
                count[num+1] -= 1
                count[num+2] -= 1
                end[num+2] += 1
            else:
                return False
            count[num] -= 1
        return True

Copy the code

Idea 2:

Heap + hash table

1. Start a dictionary DCT. (The ending value of a continuous subsequence is a key, and the length of a continuous subsequence is a value. Since there may be more than one continuous subsequence with the same ending, the value is stored in the heap.) 2. Loop numS with variable I: merge if possible, add continuous subsequence if not. 3. Determine whether the requirements are met.


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        dct = {}
        for i in nums:
            if i-1 not in dct:
                if i in dct:
                    heappush(dct[i], 1)
                else:
                    dct[i] = [1]
                    heapify(dct[i])
            else:
                if len(dct[i-1]) == 1:
                    p = dct[i-1][0]
                    del dct[i-1]
                else:
                    p = heappop(dct[i-1])
                if i in dct:
                    heappush(dct[i], p+1)
                else:
                    dct[i] = [p+1]
                    heapify(dct[i])
        return all(i >= 3 for i in sum(dct.values(), []))

Copy the code