Chương trình kiểm tra danh sách có ở trạng thái hợp lệ hay không trong Python

Giả sử chúng ta có một danh sách các số gọi là nums, chúng ta phải kiểm tra xem mọi số có thể được nhóm bằng một trong các quy tắc sau:

1. Cặp liền kề (a, a)
2. Ba số liền kề (a, a, a)
3. Ba số liền kề (a, a + 1, a + 2)

Ví dụ, nếu đầu vào là nums = [7, 7, 3, 4, 5], thì đầu ra sẽ là True, vì chúng ta có thể nhóm [7, 7] cùng nhau và [3, 4, 5] cùng nhau.

Để giải quyết bài toán này, chúng ta sẽ thực hiện các bước sau:

• n := kích thước của nums
• dp := một danh sách kích thước n+1, giá trị đầu tiên là True, các giá trị khác là False
• với i trong khoảng 2 đến n, thực hiện:
  • nếu i >= 2 và dp[i - 2] không phải 0, thì
    • nếu nums[i - 1] bằng nums[i - 2], thì dp[i] := True
  • nếu i >= 3 và dp[i - 3] không phải 0, thì
    • nếu (nums[i - 1], nums[i - 2], nums[i - 3]) đều bằng nhau HOẶC (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2), thì dp[i] := True
• trả về dp[n]

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

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

Input

[8, 8, 4, 5, 6]

Output

True