Giả sử chúng ta có một danh sách các số được gọi là kẹo và ai đó đang chơi trò chơi với bạn của anh ấy / cô ấy. Trong mỗi vòng, người chơi có thể loại bỏ hai viên kẹo liên tiếp bất kỳ có cùng giá trị. Và ai không nhặt được kẹo sẽ thua và người chơi 1 bắt đầu trước, chúng ta phải kiểm tra xem người chơi 1 có thắng hay không.
Vì vậy, nếu đầu vào là nums =[2, 2, 5], thì đầu ra sẽ là Đúng, như thể người chơi 1 chọn 2s thì người chơi kia không thể chọn bất kỳ viên kẹo nào.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
stack:=một ngăn xếp mới
-
lượt:=0
-
đối với mỗi số trong số, thực hiện
-
nếu ngăn xếp không trống và đầu ngăn xếp giống num, thì
-
bật ra từ ngăn xếp
-
lượt:=lượt + 1
-
-
nếu không,
-
đẩy num vào ngăn xếp
-
-
-
trả về true khi lượt là số lẻ, ngược lại là false
Ví dụ
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))
Đầu vào
[2, 2, 5]
Đầu ra
True