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

更新于: 2020-10-21

314 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告