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

Posted on

題目在此 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

也許你也會想看看