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;
};