与えられたリストがPythonで有効な状態にあるかどうかをチェックするプログラム

numsという番号のリストがあるとすると、次のいずれかのルールを使用してすべての番号をグループ化できるかどうかを確認する必要があります。1.連続するペア（a、a）2.連続するトリプレット（a、a、a）3.連続するトリプレット（a、a + 1、a + 2）

したがって、入力がnums =[7、7、3、4、5]のような場合、[7、7]をグループ化し、[3、4、5]をグループ化できるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• 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))

入力

[8, 8, 4, 5, 6]

出力

True