LeetCode 筆記 - 2369. Check if There is a Valid Partition For The Array

題目在此 2369. Check if There is a Valid Partition For The Array

給一個數列,請問是否可以讓所有 subarray 皆符合以下三個條件:

  1. subarray 的長度為 2,且數字相同
  2. subarray 的長度為 3,且數字相同
  3. subarray 的長度為 3,且相鄰元素為相差 1 的遞增,例如 [1, 2, 3] 為合法 subarray,[1, 4, 5] 則不是。

解題思維

名詞解說:

我相信 Dynamic Programming 會是多數人的魔王,因為他的解法很多時候都是看不懂的,鬼才看得懂
當然你也可以很直覺地用 Depth First Search 來解,但是這題的 DFS 會超時,所以我們還是來看 DP 吧!image 106

step 1: 讓 dp[i] 代表以 i 為結尾的 subarray 是否合法,如果合法則為 True,否則為 False。
step 2: 所以如果在任意 i 時,當 dp[i - 2] 為 True 時,表示可以檢查 nums[i - 1] == nums[i],如果是的話,則 dp[i] 為 True。
dp[i - 3] 為 True 時,表示可以檢查 nums[i - 2] == nums[i - 1] == nums[i],如果是的話,則 dp[i] 為 True。
nums[i - 2] == nums[i - 1] - 1 and nums[i - 1] == nums[i] - 1,如果是的話,則 dp[i] 為 True。
step 3: 最後回傳 dp[-1] 即可。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:

def validPartition(self, nums: List[int]) -> bool:

if (size := len(nums)) == 2:
return nums[0] == nums[1]

dp = [False] * size
dp[1] = nums[0] == nums[1]
dp[2] = nums[0] == nums[1] - 1 and nums[1] == nums[2] - 1
if not dp[2]:
dp[2] = nums[0] == nums[1] == nums[2]

for i in range(3, size):
if dp[i - 2] and nums[i - 1] == nums[i]:
dp[i] = True
elif dp[i - 3]:
if nums[i - 2] == nums[i - 1] == nums[i]:
dp[i] = True
elif nums[i - 2] == nums[i - 1] - 1 and nums[i - 1] == nums[i] - 1:
dp[i] = True

return dp[-1]
image 106

也許你也會想看看