364. Nested List Weight Sum II

这个题做了一个多小时，好傻逼。

显而易见计算的话必须知道当前层是第几层，因为要乘权重，想要知道是第几层又必须知道最高是几层。。

用了好久是因为想ONE PASS，尝试过遍历的时候构建STACK，通过和顶端的距离来判定层数，但是其实最后POP的过程相当于又遍历了一次。而且STACK无法O(1) access，换成LIST需要手动来维持顺序。

最终放弃了，看答案。。发现都是先遍历一次得到最高权重。。。。。。仔细想想似乎1-PASS可以用MAP实现，但是每次发现新高权重，就必须更新以前所有的，貌似没必要1PASS。。。

如果不要求1PASS，先遍历算权重的话，这个题就很直白了。。

public class Solution {int depth;public int depthSumInverse(List<NestedInteger> nestedList) {if(nestedList.size() == 0) return 0;depth = getDepth(nestedList);return helper(nestedList,1);}public int getDepth(List<NestedInteger> list){int res = 1;for(NestedInteger n: list)if(!n.isInteger()) res = Math.max(res,getDepth(n.getList())+1);return res;}public int helper(List<NestedInteger> list, int curLevel){int res = 0;for(NestedInteger i: list)if(i.isInteger()){res += (depth+1-curLevel)*i.getInteger();}else{res +=helper(i.getList(),curLevel+1);}return res;}}

---

---

二刷。

这个题也有印象，一刷的时候尝试1-PASS的DFS，根本不可能。

BFS倒是可以，模拟level order traversal。很重要的一点就是要保留积累值，代码里我用的cum= =baby cum..cum..

重点是。。每到新的一层，返还结果都加一遍积累值，就可以满足权重weighted的关系。最早的我想法乘，DFS找到权重然后乘第几层，但是实际上这里反倒是返璞归真，加法最适合这种方式，而乘法根本难以表示这种关系。。

总共N层，最上面的一层作为积累制存在的N次，总共被加到res里N次，正好是这个题的意思。。

public class Solution {public int depthSumInverse(List<NestedInteger> nestedList) {if (nestedList.size() == 0) return 0;int res = 0;int cum = 0;List<NestedInteger> tempList = new LinkedList<>();while (true) {for (NestedInteger i : nestedList) {if (i.isInteger()) {cum += i.getInteger();} else {tempList.addAll(i.getList());}}res += cum;if (tempList.size() == 0) {return res;} else {nestedList = tempList;tempList = new ArrayList<>();}}} }

所以结果是可以1-pass的。

DFS就先走一遍，找到最深的层数，然后递归并添加一个当前参数代表当前层数，层数差表示他出现的次数。
意淫完回头一看一刷，就是这么做的，我真是毫无长进。。。

转载于:https://www.cnblogs.com/reboot329/p/5944469.html

总结

以上是生活随笔为你收集整理的364. Nested List Weight Sum II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。