用 Python 检查给定列表是否处于有效状态的程序

pythonserver side programmingprogramming更新于 2026/2/8 17:16:17

假设我们有一个名为 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
对于范围为 2 到 n 的 i，执行
- 如果 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))