पूर्णांकों की एक नेस्टेड सूची दी गई है, सूची में सभी पूर्णांकों का योग उनकी गहराई से भारित करके लौटाएं। प्रत्येक तत्व या तो एक पूर्णांक है, या एक सूची -- जिसके तत्व भी पूर्णांक या अन्य सूचियां हो सकते हैं। पिछले प्रश्न से अलग जहां वजन रूट से लीफ की ओर बढ़ता है, अब वजन नीचे से ऊपर परिभाषित है। यानी, लीफ लेवल के पूर्णांकों का वजन 1 होता है, और रूट लेवल के पूर्णांकों का सबसे बड़ा वजन होता है।
उदाहरण के लिए, यदि इनपुट [[1,1],2,[1,1]] है, तो आउटपुट 8 होगा, क्योंकि चार 1 गहराई 1 पर हैं, एक 2 गहराई 2 पर है।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक फंक्शन
depthSumInverse()परिभाषित करें जोnestedListलेता है flats :=एक नई सूची (तत्व, गहराई) जोड़े स्टोर करने के लिएmaxd := 0(अधिकतम गहराई)- एक फंक्शन
flatten()परिभाषित करें जोnlst, distलेता है:dist := dist + 1maxd := 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