สมมติว่าเรามีรายการหมายเลขที่เรียกว่าลูกกวาดและมีคนกำลังเล่นเกมกับเพื่อนของเขา/เธอ ในแต่ละรอบ ผู้เล่นสามารถถอดลูกอมสองอันที่ต่อเนื่องกันที่มีค่าเท่ากันได้ และใครก็ตามที่ไม่สามารถหยิบลูกกวาดได้จะแพ้และผู้เล่นคนนั้นที่ 1 เริ่มก่อน เราต้องตรวจสอบว่าผู้เล่นที่ 1 จะชนะหรือไม่
ดังนั้น หากอินพุตเป็น nums =[2, 2, 5] เอาต์พุตจะเป็น True ราวกับว่าผู้เล่น 1 เลือก 2s ผู้เล่นอีกคนจะไม่สามารถเลือกแคนดี้ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
stack :=สแต็คใหม่
-
เปลี่ยน :=0
-
สำหรับแต่ละ num เป็น num ทำ
-
ถ้า stack ไม่ว่างและด้านบนของ stack เหมือนกับ num แล้ว
-
ป๊อปจากสแต็ก
-
เทิร์น :=เทิร์น + 1
-
-
มิฉะนั้น
-
ดัน num เข้า stack
-
-
-
คืนค่า จริง เมื่อผลัดกันเป็นคี่ มิฉะนั้น เท็จ
ตัวอย่าง
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
