Python 程式檢查給定列表是否處於有效狀態

假設我們有一個名為 nums 的數字列表，我們需要檢查每個數字是否可以使用以下規則之一進行分組：1. 連續對 (a, a) 2. 連續三元組 (a, a, a) 3. 連續三元組 (a, a + 1, a + 2)

因此，如果輸入類似於 nums = [7, 7, 3, 4, 5]，則輸出將為 True，因為我們可以將 [7, 7] 和 [3, 4, 5] 分組在一起。

為了解決這個問題，我們將遵循以下步驟：

• n := nums 的大小

• dp := 一個大小為 n+1 的列表，第一個值為 True，其他值為 False

• 對於 i 從 2 到 n，執行以下操作：

  • 如果 i >= 2 且 dp[i − 2] 不為 0，則

    • 如果 nums[i − 1] 與 nums[i − 2] 相同，則

      • dp[i] := True

  • 如果 i >= 3 且 dp[i − 3] 不為 0，則

    • 如果 (nums[i − 1]，nums[i − 2]，nums[i − 3]) 相同或 (nums[i − 1]，nums[i − 2] + 1，nums[i − 3] + 2) 相同，則

      • dp[i] := True

• 返回 dp[n]

讓我們看看以下實現以獲得更好的理解：

示例

 即時演示

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [True] + [False] * n
      for i in range(2, n + 1):
         if i >= 2 and dp[i − 2]:
            if nums[i − 1] == nums[i − 2]:
               dp[i] = True
         if i >= 3 and dp[i − 3]:
            if (nums[i − 1] == nums[i − 2] == nums[i − 3]) or (nums[i − 1] == nums[i − 2] + 1 == nums[i − 3] + 2):
               dp[i] = True
         return dp[n]
ob = Solution()
nums = [8, 8, 4, 5, 6]
print(ob.solve(nums))

輸入

[8, 8, 4, 5, 6]

輸出

True

Arnab Chakraborty

更新於: 2020-10-21

314 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習