[LeetCode] 659. Split Array into Consecutive Subsequences

轉自LeetCode 

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.

 

Constraints:

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000
• nums is sorted in non-decreasing order.

Solution

這題沒有那麼直覺，需要反覆思考一下

有個重點要先掌握，這題要求可以分成 一個或多個 subsequences

也就是，[1,2,3,4,5,6] 這樣也是正解，可以回傳 true

因此，可以用 greedy 的想法來解，先去把一個subsequence 長長，不行才找下一個

在實作上，用兩個 map 來處理

freqMap: key 是數值，也就是 nums[i]，value 是此數值出現的次數

appendMap: key 也是 nums[i]，value 是 nums[i] 可以被放到多少個 subsequence 之後

每次loop，檢查 nums[i] 是否被用完了

沒被用完，先看看是否可以被放到某個 subsequence 後 (greedy)

不能被放到某個 subsequence，看看能不能形成一個新的 subsequence

如果上述都不行，直接回傳 false

順利歷遍完的話，回傳 true

kotlin

	class Solution {
	fun isPossible(nums: IntArray): Boolean {
	val freqMap = mutableMapOf<Int,Int>()
	val appendMap = mutableMapOf<Int,Int>()
	for(n in nums) {
	freqMap[n] = freqMap[n]?.let {it+1} ?: 1
	}
	for(n in nums) {
	if(freqMap[n]!! == 0) {
	continue
	}
	when {
	appendMap[n] != null && appendMap[n]!! > 0 -> {
	appendMap[n] = appendMap[n]!! - 1
	appendMap[n+1] = appendMap[n+1]?.let{it+1} ?: 1
	}
	freqMap[n+1] != null && freqMap[n+2] != null && freqMap[n+1]!! > 0 && freqMap[n+2]!! > 0 -> {
	freqMap[n+1] = freqMap[n+1]!! - 1
	freqMap[n+2] = freqMap[n+2]!! - 1
	appendMap[n+3] = appendMap[n+3]?.let{it+1} ?: 1
	}
	else -> return false
	}
	freqMap[n] = freqMap[n]!! - 1
	}
	return true
	}
	}

view raw split_array_into_consecutive_subsequences.kt hosted with ❤ by GitHub