পাইথনে নেস্টেড লিস্ট ওয়েইটেড সম II (বটম-আপ ডেপথ ওয়েইট)

একটি ইন্টিজারের নেস্টেড লিস্ট দেওয়া আছে, সব ইন্টিজারের যোগফল বের করতে হবে যাদের ওয়েইট (ওজন) তাদের ডেপথ (গভীরতা) অনুযায়ী নির্ধারিত। প্রতিটি এলিমেন্ট হয় একটি ইন্টিজার, অথবা একটি লিস্ট — যাদের এলিমেন্টও আবার ইন্টিজার বা অন্য লিস্ট হতে পারে। আগের প্রশ্নের বিপরীতে যেখানে ওয়েইট রুট থেকে লিফ পর্যন্ত বাড়ত, এখানে ওয়েইট বটম-আপ থেকে নির্ধারিত। অর্থাৎ, লিফ লেভেলের ইন্টিজারগুলোর ওয়েইট ১, আর রুট লেভেলের ইন্টিজারগুলোর সবচেয়ে বড় ওয়েইট।

উদাহরণস্বরূপ, যদি ইনপুট হয় [[1,1],2,[1,1]], তবে আউটপুট হবে 8, কারণ চারটি ১ ডেপথ ১-এ, একটি ২ ডেপথ ২-এ।

• একটি depthSumInverse() ফাংশন ডিফাইন করুন যা nestedList নেবে।
• flats := একটি নতুন তালিকা
• maxd := 0
• একটি flatten() ফাংশন ডিফাইন করুন যা nlst, dist নেবে।
  • dist := dist + 1
  • maxd := max(maxd, dist)
  • প্রতিটি node এর জন্য nlst-এ:
    • যদি node ইন্টিজার হয় (নন-জিরো), তবে (node, dist) কে flats-র শেষে ঢুকান।
    • অন্যথায়, flatten(node, dist) কল করুন।
• flatten(nestedList, 0) কল করুন।
• summ := 0
• প্রতিটি v, d এর জন্য flats-এ:
  • summ := summ + v * (maxd + 1 - d)
• summ রিটার্ন করুন।

class Solution(object):
    def depthSumInverse(self, nestedList):
        flats = []
        self.maxd = 0
        def flatten(nlst, dist):
            if isinstance(nlst, list):
                nlst = nlst
            dist += 1
            self.maxd = max(self.maxd, dist)
            for node in nlst:
                if isinstance(node, int):
                    flats.append((node, dist))
                else:
                    flatten(node, dist)
        flatten(nestedList, 0)
        summ = 0
        for v, d in flats:
            summ += v * (self.maxd + 1 - d)
        return summ

ob = Solution()
print(ob.depthSumInverse([[1,1],2,[1,1]]))

[[1,1],2,[1,1]]

8