[刷题防痴呆] 0659 - 分割数组为连续子序列 (Split

题目地址

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

题目描述

659. Split Array into Consecutive Subsequences

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.
Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

 

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5
Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5
Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

思路

• 贪心. 具体贪心策略为如果可以拼接到前面就优先拼接到前面而不用创建一个新的序列. (Determine if it is possible to split nums into one or more subsequences)
• 创建两个hashmap. 一个存储count, 一个存储对应尾部元素的序列有多少个.
• init countMap.
• 对于每一个num, 看count是否仍大于0. 如果大于0, 表示当前的数需要加入到一个序列中.
• 优先查看是否能拼接到前面的序列.
• 如果不能拼接到前面, 看一下是否能创建一个新序列.
• 如果都不能, 则return false.

关键点

• 也可使用count数组代替map. 因为num的范围固定.

代码

• 语言支持：Java

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        Map<Integer, Integer> tailMap = new HashMap<>();
        for (int num: nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        for (int num: nums) {
            int count = countMap.get(num);
            if (count <= 0) {
                continue;
            }
            if (tailMap.getOrDefault(num - 1, 0) > 0) {
                countMap.put(num, count - 1);
                tailMap.put(num - 1, tailMap.get(num - 1) - 1);
                tailMap.put(num, tailMap.getOrDefault(num, 0) + 1);
            } else if (countMap.getOrDefault(num + 1, 0) > 0 && countMap.getOrDefault(num + 2, 0) > 0) {
                countMap.put(num, count - 1);
                countMap.put(num + 1, countMap.get(num + 1) - 1);
                countMap.put(num + 2, countMap.get(num + 2) - 1);
                tailMap.put(num + 2, tailMap.getOrDefault(num + 2, 0) + 1);
            } else {
                return false;
            }
        }

        return true;
    }
}

// 使用count数组
class Solution {
    public boolean isPossible(int[] nums) {
        int[] map = new int[2004];
        int[] tail = new int[2004];
        int n = 1001;
        for (int num: nums) {
            map[num + n]++;
        }
        for (int num: nums) {
            int count = map[num + n];
            if (count <= 0) {
                continue;
            }
            if (tail[num + n - 1] > 0) {
                map[num + n]--;
                tail[num + n - 1]--;
                tail[num + n]++;
            } else if (map[num + n + 1] > 0 && map[num + n + 2] > 0) {
                map[num + n]--;
                map[num + n + 1]--;
                map[num + n + 2]--;
                tail[num + n + 2]++;
            } else {
                return false;
            }
        }

        return true;
    }
}