zl程序教程

您现在的位置是:首页 >  其他

当前栏目

LeetCode_优先级队列_回溯_659.分割数组为连续子序列

LeetCode序列队列数组队列 分割 连续 优先级
2023-09-27 14:25:45 时间

1.题目

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个长度至少为 3 的子序列,其中每个子序列都由连续整数组成。

如果可以完成上述分割,则返回 true ;否则,返回 false。

示例 1:
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

示例 2:
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5

示例 3:
输入: [1,2,3,4,4,5]
输出: False

提示:
1 <= nums.length <= 10000

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/split-array-into-consecutive-subsequences
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2.思路

(1)哈希表 & 优先级队列
思路参考本题官方题解

① 定义一个哈希表 hashMap ,键为子序列的最后一个数字,值为一个优先级队列,用于存储所有的以该数字结尾的子序列长度,由于优先级队列满足队首的元素是最小的,所以队首的元素即为以该数字结尾的最小的子序列长度;

② 遍历数组 nums,记当前遍历到的元素为 num:
1)如果 hashMap 不存在以 num 结尾的子序列,那么将 num 加入到 hashMap 中,并创建一个优先级队列(暂时为空)作为其对应的值;
2)如果 hashMap 存在以 num - 1 结尾的子序列,那么取出以 num − 1 结尾的最小的子序列长度,将子序列长度加 1 之后作为以 num 结尾的子序列长度。此时,以 num − 1 结尾的子序列减少了一个,而以 x 结尾的子序列增加了一个;
3)如果 hashMap 不存在以 num - 1 结尾的子序列,那么新建一个只包含 num 的子序列,长度为 1

③ 数组 nums 遍历结束后,检查 hashMap 中存储的每个子序列的长度是否都大于等于 3,由于优先级队列的特性,故只用检查每个优先级队列的队首元素是否都大于等于 3 即可,如果存在小于 3 的情况,则直接返回 false;否则返回 true。

(2)回溯
思路参考谁能想到,斗地主也能玩出算法

3.代码实现(Java)

//思路1————哈希表 & 优先级队列
class Solution {
    public static boolean isPossible(int[] nums) {
        int length = nums.length;
        /*
            键为子序列的最后一个数字,值为一个优先级队列,用于存储所有的以该数字结尾的子序列长度,
            优先级队列满足队首的元素是最小的,因此队首的元素即为最小的子序列长度
        */
        Map<Integer, PriorityQueue<Integer>> hashMap = new HashMap<>();
        for (int num : nums) {
            if (!hashMap.containsKey(num)) {
                hashMap.put(num, new PriorityQueue<>());
            }
            if (hashMap.containsKey(num - 1)) {
                int preLen = hashMap.get(num - 1).poll();
                if (hashMap.get(num - 1).isEmpty()) {
                    hashMap.remove(num - 1);
                }
                //以 num 结尾的子序列的长度为 preLen + 1
                hashMap.get(num).offer(preLen + 1);
            } else {
                //新建一个只包含 num 的子序列,长度为 1
                hashMap.get(num).offer(1);
            }
        }
        Set<Map.Entry<Integer, PriorityQueue<Integer>>> entrySet = hashMap.entrySet();
        for (Map.Entry<Integer, PriorityQueue<Integer>> entry : entrySet) {
            PriorityQueue<Integer> priorityQueue = entry.getValue();
            if (priorityQueue.peek() < 3) {
                return false;
            }
        }
        return true;
    }
}
//思路2————回溯
class Solution {
    public static boolean isPossible(int[] nums) {
        int length = nums.length;
        //键/值:数组 nums 中的元素/对应出现的次数
        HashMap<Integer, Integer> freq = new HashMap<>();
        //统计数组 nums 中各元素出现的次数
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        // need 记录哪些元素可以被接到其他子序列后面
        HashMap<Integer, Integer> need = new HashMap<>();
        for (int num : nums) {
            if (freq.get(num) == 0) {
                //当前元素 num 已经被用到一个子序列中
                continue;
            }
            //先判断 num 能否接到一个子序列后面
            if (need.containsKey(num) && need.get(num) > 0) {
                // num 可以接到之前的某个序列后面
                freq.put(num, freq.get(num) - 1);
                //对 num 的需求减一
                need.put(num, need.get(num) - 1);
                //对 num + 1 的需求加一
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (freq.get(num) != null && freq.get(num) > 0 
                    && freq.get(num + 1) != null && freq.get(num + 1) > 0 
                    && freq.get(num + 2) != null && freq.get(num + 2) > 0) {
                //将 num 作为另一个子序列的开头,新建一个长度为 3 的子序列 [num, num + 1, num + 2]
                freq.put(num, freq.get(num) - 1);
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                //对 num + 3 的需求加一
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            } else {
                return false;
            }
        }
        return true;
    }
}