Chương trình kiểm tra người chơi đầu tiên thắng game bỏ kẹo trong Python

Hai người chơi luân phiên bỏ 2 kẹo liên tiếp cùng giá trị từ danh sách nums. Người không thể bỏ thua. Người chơi 1 đi trước. Xác định người chơi 1 có thắng không.

Ví dụ

Đầu vào: [2, 2, 5]

Người chơi 1 bỏ cặp (2,2) → còn [5]. Người chơi 2 không có cặp nào → Thắng (True).

Quan sát

Mỗi lần bỏ cặp giảm độ dài mảng 2. Tổng số lượt bỏ có thể thực hiện quyết định thắng thua: nếu số lượt lẻ → người chơi 1 thắng.

Thuật toán (Stack)

1. Khởi tạo stack rỗng, turns = 0.
2. Duyệt từng số num trong nums:
   • Nếu stack không rỗng và đỉnh stack == num: pop stack, turns++.
   • Ngược lại: push num vào stack.
3. Trả về turns % 2 == 1.

Triển khai Python

class Solution:
    def solve(self, nums):
        stack = []
        turns = 0
        for num in nums:
            if stack and stack[-1] == num:
                stack.pop()
                turns += 1
            else:
                stack.append(num)
        return bool(turns & 1)  # True nếu turns lẻ

# Test
ob = Solution()
print(ob.solve([2, 2, 5]))        # True
print(ob.solve([1, 2, 2, 1]))     # True (bỏ 2,2 rồi 1,1)
print(ob.solve([1, 2, 3]))        # False

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(n) cho stack.