पायथन में अंतिम पत्थर का वजन

मान लीजिए हमारे पास कुछ चट्टानें हैं, प्रत्येक चट्टान का एक पॉजिटिव इंटीजर वजन है। प्रत्येक चाल में, हम दो सबसे भारी चट्टानों को लेंगे और उन्हें एक साथ तोड़ेंगे। मान लीजिए पत्थरों का वजन x और y है और x <= y। इस तोड़ का परिणाम दो प्रकार का हो सकता है।

• यदि x = y, तो दोनों पत्थर पूरी तरह से नष्ट हो जाते हैं;
• अन्यथा जब x != y, तो वजन x का पत्थर पूरी तरह से नष्ट हो जाता है, और वजन y के पत्थर का नया वजन y-x हो जाता है।

अंत में, अधिकतम 1 पत्थर बचता है। हमें इस पत्थर का वजन ढूंढना है (0 जब कोई पत्थर न बचे।)

इसलिए यदि पत्थरों के वजन [2,7,4,1,8,1] हैं, तो परिणाम 1 होगा। पहले 7 और 8 चुनें, फिर 1 प्राप्त करें, तो ऐरे [2,4,1,1,1] होगा, दूसरी बार 2 और 4 लें। ऐरे [2,1,1,1] होगा, उसके बाद 2 और 1 चुनें, ऐरे [1,1,1] होगा, फिर वजन 1 के दो पत्थर चुनें, तो दोनों नष्ट हो जाएंगे, तो ऐरे [1] होगा। यह उत्तर है।

समाधान के चरण

• यदि पत्थर वजन ऐरे W में कोई एलिमेंट नहीं है, तो 0 लौटाएं
• यदि W में केवल एक एलिमेंट है तो W[0] लौटाएं
• जब तक W में एक से अधिक एलिमेंट्स हैं
  • W को सॉर्ट करें
  • s1 := W का अंतिम एलिमेंट, s2 := W का अंतिम से दूसरा एलिमेंट
  • यदि s1 = s2, तो s1 और s2 को W से हटा दें
  • अन्यथा s1 := |s1 - s2|, W से अंतिम एलिमेंट हटाएं, फिर s1 को W का अंतिम एलिमेंट सेट करें
• यदि W में एक एलिमेंट है, तो वह एलिमेंट लौटाएं, अन्यथा 0 लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        if len(stones) == 0:
            return 0
        if len(stones) == 1:
            return stones[0]
        while len(stones) > 1:
            stones.sort()
            s1, s2 = stones[-1], stones[-2]
            if s1 == s2:
                stones.pop(-1)
                stones.pop(-1)
            else:
                s1 = abs(s1 - s2)
                stones.pop(-1)
                stones[-1] = s1
        if len(stones):
            return stones[-1]
        return 0

ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))

इनपुट

[2,7,4,1,6,1]

आउटपुट

1