Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में कैंडी हटाने के खेल में पहला खिलाड़ी जीतेगा या नहीं जांचने का प्रोग्राम

संख्याओं की एक सूची 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) के समतुल्य है जहां प्रत्येक जोड़ी हटाना एक चाल है। चूंकि खिलाड़ियों के पास कोई विकल्प नहीं है (केवल उपलब्ध जोड़ी हटाई जा सकती है), खेल पूरी तरह से निर्धारित है। कुल चालों की समता विजेता तय करती है।

  1. Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह जांचना है कि ट्री सममित ट्री है या नहीं। एक ट्री को सममित कहा जाएगा यदि यह उसके दर्पण छवि लेने पर समान हो। इन दो ट्री में से पहला सममित है, लेकिन दूसरा नहीं। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे। हम निम्नलिखित चरणों को रिकर्सिवली कॉल करे

  1. पायथन में बाइनरी ट्री के BST होने की जांच करने का प्रोग्राम पायथन में बाइनरी ट्री के BST होने की जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जांचना है कि क्या यह एक बाइनरी सर्च ट्री है या नहीं। जैसा कि हम जानते हैं एक BST के निम्न गुण होते हैं: इसके बाएं सबट्री के सभी नोड्स वर्तमान नोड के मान से छोटे होते हैं इसके दाएं सबट्री के सभी नोड्स वर्तमान नोड के मान से बड़े होते हैं ये गुण सभी नोड्स क

  1. पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

    मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो। उदाहरण के लिए, यदि