โปรแกรมตรวจสอบ List ว่า Valid ตามกฎการจัดกลุ่ม (Python)

ปัญหา

กำหนด list ของตัวเลข nums ตรวจสอบว่าสามารถจัดกลุ่มทุกตัวเลขได้ตามกฎ 3 ข้อ:

1. คู่ติดกัน (a, a)
สามตัวติดกันเหมือนกัน (a, a, a) สามตัวติดกันเรียงลำดับ (a, a+1, a+2)

ตัวอย่าง: nums = [7, 7, 3, 4, 5] → True (จัดกลุ่ม [7,7] และ [3,4,5])

วิธีแก้: Dynamic Programming

ใช้ DP array ขนาด n+1 โดย dp[i] = True หมายถึง subarray แรก i ตัวจัดกลุ่มได้

อัลกอริทึม

1. dp[0] = True (empty array valid)
2. วน i = 2 ถึง n:
   • ถ้า dp[i-2] เป็น True และ nums[i-1] == nums[i-2] → dp[i] = True (กฎที่ 1)
   • ถ้า dp[i-3] เป็น True และ (nums[i-1]==nums[i-2]==nums[i-3] หรือ nums[i-1]==nums[i-2]+1==nums[i-3]+2) → dp[i] = True (กฎที่ 2,3)
3. คืนค่า dp[n]

โค้ด Python

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [True] + [False] * n
        
        for i in range(2, n + 1):
            # กฎที่ 1: คู่ (a, a)
            if i >= 2 and dp[i - 2]:
                if nums[i - 1] == nums[i - 2]:
                    dp[i] = True
            
            # กฎที่ 2,3: สามตัว (a,a,a) หรือ (a,a+1,a+2)
            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()
print(ob.solve([8, 8, 4, 5, 6]))  # True
print(ob.solve([7, 7, 3, 4, 5]))  # True
print(ob.solve([1, 2, 3, 4]))     # False

ความซับซ้อน

• Time: O(n)
• Space: O(n)

การทำงานของตัวอย่าง [8, 8, 4, 5, 6]

1. i=2: dp[0]=True, nums[1]==nums[0] (8==8) → dp[2]=True
2. i=5: dp[2]=True, nums[4]==nums[3]+1==nums[2]+2 (6==5+1==4+2) → dp[5]=True
3. คืนค่า True