659. Split Array into Consecutive Subsequences


Posted by hata0833 on 2022-08-21

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).

大意:
給定的數組是否能拆分為包含連續數字的子集,且每個子集的長度都要 > 3。
ps. 自己也是自己的子集
一開始題目的意思理解錯了,寫了好多種錯方法才搞懂題目的意思

解題思路:
既然是要把數組拆分為子集,那就拆的同時讓他們結隊,有兩種結隊方式:

  • 存在一個子集,可以直接加入,譬如4可以加入123
  • 不存在可以加入的子集,找後面兩個人來結隊,譬如4要找56

使用兩個哈希表來記錄,一個countMap記錄數字使用的次數,tailMap紀錄已經結隊的子集的最後一個數字

代碼

var isPossible = function(nums) {
    const count = new Map();
    // 先遍歷一次數組,紀錄每個數字出現的次數
    for (const x of nums) {
        if (count.has(x)) {
            count.set(x, count.get(x) + 1);
        } else {
            count.set(x, 1);
        }
    }
    const tail = new Map();
    for (const x of nums) {
        // 確認該數字還有沒有使用次數
        const time = count.get(x);
        if (time > 0) {
            count.set(x, time - 1);
            // 看有沒有已存在的隊列可以加入 -> 查找以x - 1為結尾的隊列
            const pre = tail.get(x - 1);
            if (pre > 0) {
                tail.set(x - 1, pre - 1);
                tail.set(x, (tail.get(x) || 0) + 1);
            } else {
                // 沒有隊列可以加入,找兩個人自己組隊
                const c1 = count.get(x + 1);
                const c2 = count.get(x + 2);
                if (c1 > 0 && c2 > 0) {
                    count.set(x + 1, c1 - 1);
                    count.set(x + 2, c2 - 1);
                    tail.set(x + 2, (tail.get(x + 2) || 0) + 1);
                } else {
                    return false;
                }
            }
        }

    }
    return true;
};

#Leetcode







Related Posts

〈 演算法與資料結構 #1〉Recursion 遞迴函式

〈 演算法與資料結構 #1〉Recursion 遞迴函式

CH5. 大師級函式:閉包與範圍

CH5. 大師級函式:閉包與範圍

25. Design Principles - SOLID

25. Design Principles - SOLID


Comments