NestedListWeightSum [source code]

public class NestedListWeightSum {
    public int depthSum(List<NestedInteger> nestedList) {
        if (nestedList.size() == 0) return 0;
        int res = 0;
        for (NestedInteger i : nestedList) res += helper(1, i);
        return res;
    }

    // This is the interface that allows for creating nested lists.
    // You should not implement it, or speculate about its implementation
    public interface NestedInteger {
        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();
        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();
        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }

    public int helper(int accum, NestedInteger nestedInteger) {
        if (nestedInteger.isInteger()) return accum * nestedInteger.getInteger();
        int res = 0;
        for (NestedInteger node : nestedInteger.getList()) res += helper(accum + 1, node);
        return res;
    }
}

读题的时候注意这句话:

return the sum of all integers in the list weighted by their depth

这个其实就是return weighted sum的意思, 不要以为就是简单的 sum;

另外注意这里这个NestedInteger的 API 的设计思路: 其实这个结构也是一个recursive definition, or inductive definition; base case就是 integer;

题外话, 如果这里的这个参数是一个 String, 这个问题其实是非常简单的, 直接从左到右扫一遍, 然后一个map 保存结果(可以用 array 如果知道这些 number 在某一个范围以内); 每个 number 的 weight 就是(按照 steam 算法的思路)扫到目前为止所出现的"["的个数减去"]"的个数. 这个算法真的是秒杀速度就想出来的.

这个题目其实跟一个普通的 tree 的问题非常类似;

分析的时候, 用小的例子开始分析, 比如[1,2]这样的;

刚开始的时候认为 helper 的参数也应该是List, 不过这个就有问题了, 你作为一个 recursive的函数,或者你这样想, 如果我们做的是 TreeNode 的问题, 你的 recursive 函数的参数会是List吗?

这里碰到一个问题: 在意识到我对于 helper 的设计有问题的时候, 我就开始改. 但是因为不知道到底哪些地方要改, 我就先自己改了一个大概, 然后直接就丢到OJ 里面, 类似于让 compiler 来帮我改.
这个做法现在我是初期刷题阶段, 可能倒无所谓. 不过如果以后面类似 FG 这样的公司, 不停的compiler error肯定是说不过去的. 所以现在开始要养成自己眼睛扫一遍代码, 捕捉错误的习惯.

速度是2ms, 最优解的代码跟这个差不多, 都是fold right 的recursion. 之所以必须用FOLD_right, 是因为站在每一个root 自己的角度, 它能知道的其实只有自己往下的深度, 所以如果直接返回的 sum 是基于自己往下的深度计算出来的, 这个结果返回上去之后, 上面的 level 是没有办法使用的;

当然有一个折衷的办法, 就是还是一个普通的...好像没有折衷的办法(我想说的是一个普通的 traversal 走一遍, 记录深度withmap, 最后走一遍 map 来计算 sum);

另外这个问题, 类似于 tree 的问题, 也是可以用一个iterative BFS完成的, 下面是代码:

public int depthSum(List<NestedInteger> nestedList) {  
    if(nestedList == null){  
        return 0;  
    }  

    int sum = 0;  
    int level = 1;  

    Queue<NestedInteger> queue = new LinkedList<NestedInteger>(nestedList);  
    while (queue.size() > 0) {  
        int size = queue.size();  

        for (int i = 0; i < size; i++) {  
            NestedInteger ni = queue.poll();  

            if (ni.isInteger()) {  
                sum += ni.getInteger() * level;  
            } else {  
                queue.addAll(ni.getList());  
            }  
        }  

        level++;  
    }      
    return sum;  
}

事实上, BFS 是这类问题最 intuitive 的思路, 不过写的时候可能有点麻烦就是了;

反过头来想想, 这个问题跟之前的max depth of binary tree有什么不同的地方? 导致那个题目就可以用left fold, 这里就只能用right fold? 我感觉主要的区别就是left fold无法完成乘法, 只能完成加法;

好像其实我这个跟fold left/right没有什么关系? 好像记混淆概念了. 那就用 accum 思路来记忆好了. 反正就是如果涉及加法以外的计算, 很可能不实用 accum 就没有办法完成了(?有待考证);

Problem Description

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27)

Hide Company Tags LinkedIn
Hide Tags Depth-first Search
Hide Similar Problems (M) Nested List Weight Sum II (M) Array Nesting