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

पायथन में लीफ नोड्स की सूची से न्यूनतम सम ट्री खोजने का प्रोग्राम


मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। यह सूची एक ट्री के इनऑर्डर ट्रैवर्सल में लीफ नोड्स को दर्शाती है। यहां आंतरिक नोड्स के 2 बच्चे होते हैं और उनका मान उनके बाएं सबट्री के सबसे बड़े लीफ मान और दाएं सबट्री के सबसे बड़े लीफ मान के गुणनफल के बराबर होता है। हमें न्यूनतम मान वाले ट्री के मानों का योग ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [3, 5, 10] है, तो आउटपुट 83 होगा।

पायथन में लीफ नोड्स की सूची से न्यूनतम सम ट्री खोजने का प्रोग्राम

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • res := nums के सभी तत्वों का योग
  • जब तक len(nums) > 1:
    • i := nums में न्यूनतम तत्व का इंडेक्स
    • left := nums[i-1] यदि i > 0 अन्यथा इनफिनिटी
    • right := nums[i+1] यदि i < len(nums)-1 अन्यथा इनफिनिटी
    • res := res + min(left, right) * nums.pop(i)
  • res लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums):
        res = sum(nums)
        while len(nums) > 1:
            i = nums.index(min(nums))
            left = nums[i - 1] if i > 0 else float("inf")
            right = nums[i + 1] if i < len(nums) - 1 else float("inf")
            res += min(left, right) * nums.pop(i)
        return res

ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums))

इनपुट

[3, 5, 10]

आउटपुट

83

  1. Python प्रोग्राम में ऐरे का योग खोजना Python प्रोग्राम में ऐरे का योग खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक ऐरे दिया गया है, हमें ऐरे का योग निकालने की आवश्यकता है। पूरे ऐरे को पार करने और प्रत्येक इंडेक्स पर तत्व को जोड़कर योग प्राप्त करने का ब्रूट-फोर्स दृष्टिकोण नीचे चर्चा किया गया है। उदाहरण # sum फ़ंक्शन def

  1. पायथन प्रोग्राम: लिस्ट का संचयी योग ज्ञात करें पायथन प्रोग्राम: लिस्ट का संचयी योग ज्ञात करें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक लिस्ट दी गई है, हमें संचयी योग के साथ एक लिस्ट बनानी है। उदाहरण # संचयी योग def Cumulative(l): new = [] cumsum = 0 for element in l: cumsum += element new.append(cumsum) return new # ड्राइवर

  1. पायथन प्रोग्राम: ऐरे का योग ढूंढें पायथन प्रोग्राम: ऐरे का योग ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट इनपुट के रूप में एक ऐरे दिए जाने पर, हमें दिए गए ऐरे का योग निकालने की आवश्यकता है। यहां हम ब्रूट-फोर्स दृष्टिकोण का पालन कर सकते हैं यानी एक लिस्ट को ट्रैवर्स करना और प्रत्येक एलिमें