โปรแกรมตรวจสอบว่าผู้เล่นคนแรกชนะในเกมเอาลูกอมออกหรือไม่ใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ candies สองผู้เล่นสลับกันเอาลูกอมออก ในแต่ละรอบ ผู้เล่นต้องเอาลูกอมที่ติดกันสองลูกซึ่งมีค่าเท่ากันออก ผู้ที่ไม่สามารถเอาลูกอมออกได้ถือว่าแพ้ ผู้เล่นคนแรกเริ่มก่อน ตรวจสอบว่าผู้เล่นคนแรกจะชนะหรือไม่

ตัวอย่าง

อินพุต: nums = [2, 2, 5]

เอาต์พุต: True

ผู้เล่นคนแรกเอาลูกอมสองลูกที่เป็น 2 ออก ผู้เล่นคนที่สองไม่มีลูกอมติดกันคู่ใดเหลือ จึงแพ้

ขั้นตอนการแก้ปัญหา

ใช้สแต็ก (stack) จำลองการเอาลูกอมออก:

1. สร้างสแต็กว่าง stack, ตัวนับรอบ turns = 0
2. วนลูปผ่านแต่ละ num ใน nums:
   • ถ้า stack ไม่ว่าง และค่าบนสุดเท่ากับ num ให้.pop() และเพิ่ม turns
   • มิฉะนั้น .push(num) เข้า stack
3. ถ้า turns เป็นคี่ (odd) ผู้เล่นคนแรกชนะ คืนค่า True มิฉะนั้น False

การนำไปใช้ใน 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)

ob = Solution()
nums = [2, 2, 5]
print(ob.solve(nums))

อินพุต

[2, 2, 5]

เอาต์พุต

True