LC: 364. Nested List Weight Sum II
https://leetcode.com/problems/nested-list-weight-sum-ii/


The Essence:
Anders als das erste Problem kann man nicht am Anfang wissen, mit welchem Wert man eine Zahl aus den Listen multiplizieren muss, da der Wert zu der Tiefe relativ negativ proportional ist. Man braucht also die maximale Tiefe.
Details:
Dafür gibt es 2 Wege:
Die ganze verschachtelte Liste durchlaufen und finden, was die maximale Tiefe ist. Danach alle Werte summieren, weil der Tiefenunterschied jetzt zu berechnen ist.
Sei die Summe der ersten Schicht der verschachtelten Liste eine Zahl S. Der eigentliche Wert wird durch Multiplikation mit der maximalen Tiefe berechnet. Dann kann man den Wert einer Schicht bis zu der tiefsten Schicht anhäufen. Bei jeder Tiefe wird diese Werte zu der gesamten Summe addiert. Das entspricht einer Breitensuche und kann durch Warteschlangen oder Hashtabellen implementiert werden.
Solutions:
https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/nestedlistweightsum2 Default Code:
Last updated