संख्याओं की एक सूची candies दी गई है। दो खिलाड़ी बारी-बारी से खेलते हैं। प्रत्येक चाल में, एक खिलाड़ी लगातार दो समान मान वाली कैंडी हटा सकता है। जो खिलाड़ी चाल नहीं चल सकता, हार जाता है। खिलाड़ी 1 पहले शुरू करता है। जांचें कि खिलाड़ी 1 जीतेगा या नहीं।
उदाहरण
इनपुट: nums = [2, 2, 5]
आउटपुट: True
खिलाड़ी 1 दोनों 2 को हटा देता है, बचता है [5]। खिलाड़ी 2 कोई चाल नहीं चल सकता, इसलिए खिलाड़ी 1 जीतता है।
मुख्य अंतर्दृष्टि (स्टैक आधारित)
यह खेल स्टैक का उपयोग करके हल किया जा सकता है। जब हम सूची को पार करते हैं:
- यदि स्टैक खाली नहीं है और शीर्ष तत्व वर्तमान तत्व के बराबर है, तो शीर्ष को पॉप करें (एक जोड़ी हट गई) और चाल काउंटर बढ़ाएं।
- अन्यथा, वर्तमान तत्व को स्टैक पर पुश करें।
कुल चालों की संख्या निर्धारित करती है कि कौन जीतता है: यदि चालें विषम हैं, तो खिलाड़ी 1 जीतता है; यदि सम, तो खिलाड़ी 2 जीतता है।
पायथन कार्यान्वयन
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
# परीक्षण
ob = Solution()
print(ob.solve([2, 2, 5])) # True
print(ob.solve([1, 2, 2, 1])) # True (चालें: 2, 1)
print(ob.solve([1, 1, 2, 2])) # False (चालें: 2)
print(ob.solve([1, 2, 3])) # False (चालें: 0)
समय जटिलता
- O(n) समय, O(n) स्थान (स्टैक)।
- प्रत्येक तत्व को अधिकतम एक बार पुश/पॉप किया जाता है।
खेल सिद्धांत व्याख्या
यह खेल निम (Nim) के समतुल्य है जहां प्रत्येक जोड़ी हटाना एक चाल है। चूंकि खिलाड़ियों के पास कोई विकल्प नहीं है (केवल उपलब्ध जोड़ी हटाई जा सकती है), खेल पूरी तरह से निर्धारित है। कुल चालों की समता विजेता तय करती है।