NestedListWeightSumII [source code]

public class NestedListWeightSumII {
static
/******************************************************************************/
public class Solution {
    int maxDepth;

    public int depthSumInverse(List<NestedInteger> nestedList) {
        maxDepth = 0;
        for (NestedInteger root : nestedList)
            maxDepth = Math.max(maxDepth, probe(root));
        maxDepth++;
        int sum = 0;
        for (NestedInteger root : nestedList)
            sum += dfs(root, 2);
        return sum;
    }

    public int dfs(NestedInteger root, int depth) {
        if (root.isInteger()) {
            return (maxDepth - depth + 1) * root.getInteger();
        }
        int sum = 0;
        List<NestedInteger> ls = root.getList();
        for (NestedInteger node : ls)
            sum += dfs(node, depth + 1);
        return sum;
    }

    public int probe(NestedInteger root) {
        if (root.isInteger())
            return 1;
        int depth = 0;
        List<NestedInteger> ls = root.getList();
        for (NestedInteger node : ls) {
            int curDepth = probe(node);
            if (curDepth > depth)
                depth = curDepth;
        }
        return depth + 1;
    }
}
/******************************************************************************/

// This is the interface that allows for creating nested lists.
// You should not implement it, or speculate about its implementation
public interface NestedInteger {
    // Constructor initializes an empty nested list.
    // public NestedInteger();          // 这俩不知道为什么会不能compile, 如果不comment的话; 
    // Constructor initializes a single integer.
    // public NestedInteger(int value);         // 这俩不知道为什么会不能compile, 如果不comment的话; 
    // @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();
    // Set this NestedInteger to hold a single integer.
    public void setInteger(int value);
    // Set this NestedInteger to hold a nested list and adds a nested integer to it.
    public void add(NestedInteger ni);
    // @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 static void main(String[] args) {
        NestedListWeightSumII.Solution tester = new NestedListWeightSumII.Solution();
    }
}

虽然说题目不让你speculate about its implementation, 但是你实际上还是要稍微思考一下怎么implement的; 这个其实就是一个类似ListNode的常见的inductive definition;

这个题目如果站在tree的context下面就很好些, 一个recursion就能解决的事情; 不过这里之所以这么搞, 就是想考察你在一个新的context和定义下面写recursion的能力;

这个问题好像没有想象的那么简单, 直接计算height好像并不能直接解决这个题目; 因为站在某一个subtree的root的时候, 你是不知道当前这个subtree里面要乘的系数应该是多少的: 光知道你自己这个subtree的height是不够的, 你还要知道你这个root离大root有多远;

要不还是返回到depth的方法? 用那个思路好像也不难? 先一个DFS找到最大的depth, 然后? 好像是可以做的;

这个写出来了, 速度是6ms (16%), 很不理想. 这个应该算是一个笨办法了; 写的时候注意各种变量更新的边界效应, 尤其是main call的时候给你的其实是一个list, 所以你当前就已经在depth为1的位置了, 你下去的所有的DFS的call给的depth(也就是你tag给下一层的node的depth)都应该是2开始;

反正只要跟maxDepth能对应起来就行了, 换算关系自己举几个例子一看就行了;

感觉这个题目最直白的做法还是用BFS来做, 不过题目的标签非要给一个DFS, 感觉不用DFS做一下有点不舒服;

看起来很简单的一个题目还是吭哧吭哧写了半天, 丢人好吧;

这个题目考的东西是tree的depth和height, 需要想到一个技巧:

• depth和height的互换. 这里就是用了这个技巧;

另外weighted sum好像本身也是一个题型, 尤其是在recursion的context下考; 需要有两种思路:

• 乘法思路: 直接计算你的weight, 然后乘法做. weight往往并不总是那么好计算,比如这题这里的这个weight就不是很好计算;
• 加法思路: 乘法本身就可以用recursive addition来做, 所以这个weighted sum也可以考虑用recursive的思路来做: 加法思路的recursion更加好实现;

discussion里面很多人认为这个问题的表述比较模糊:

This question can easily mislead readers. This is not how we generally define the "depth" of a node in the tree. If I remember correctly, "Depth" means the length from root to a node and "height" means the length from the node to its deepest child.

Apparently, in this question, neither of them is our case. I think the question should emphasize their special definition "depth", to avoid misunderstand.

这个是stefan在discussion里面的一个解, 非常的聪明, 用的是加法思路, 完全都没有depth这个variable的出现, 不过最后实现的总体思路其实用的是BFS:

Instead of multiplying by depth, add integers multiple times (by going level by level and adding the unweighted sum to the weighted sum after each level).

public int depthSumInverse(List<NestedInteger> nestedList) {  
    int unweighted = 0, weighted = 0;  
    while (!nestedList.isEmpty()) {  
        List<NestedInteger> nextLevel = new ArrayList<>();  
        for (NestedInteger ni : nestedList) {  
            if (ni.isInteger())  
                unweighted += ni.getInteger();  
            else  
                nextLevel.addAll(ni.getList());  
        }  
        weighted += unweighted;  
        nestedList = nextLevel;  
    }  
    return weighted;  
}

这个算法就是看准了一点, 在更高的level(depth更低)出现的所有的integer都可以被认为get added one additional time for each level under it;

严格来说这里虽然用的是加法思路, 但是实际上没有借助于recursive的思路; 不过这个算法本身真的是非常的聪明;

这个是我给出的点评:

Each integer get added one extra time for the mere existence of each one level under it.

The concept of weight here is implemented with repeated addition;

他这个算法如果说让我来设计的话, 设计的时候的核心思考方式顾及还是用BFS的level的概念来理解的; level越高的integer最后得到的weight(系数)就越大.

这个题目的这个tree其实并不是一个最普通的BST, 而是一个只有leaf有integer, 其他的internal node全都是list的tree; 这种tree在HFDP这本书的时候好像叫做composite tree: 大概意思就是node的type多于一种;

这样的一个tree的定义其实跟传统的trie的定义有点类似的, 大概是这样的:

public class Node {  
    Integer val;  
    List<Node> ls;  
}

这样的就可以完成一个向正常的BST的转换, 不过他这里的NestedInteger应该不是用这个做得. 我这里每个node里面是both都有, 他们的implementation则是只有一个: either; //感觉只要再加一个boolean的flag, 然后配合Null来做, 应该就行了;

所以其实height-weighted sum其实也可以反过来用level-weighted sum的思路来理解; 注意这个level跟depth的概念其实是不一样的;

这个是discussion里面另外一个非常类似的解:

public int depthSumInverse(List<NestedInteger> nestedList) {  
    if (nestedList == null) return 0;  
    Queue<NestedInteger> queue = new LinkedList<NestedInteger>();  
    int prev = 0;  
    int total = 0;  
    for (NestedInteger next: nestedList) {  
        queue.offer(next);  
    }  

    while (!queue.isEmpty()) {  
        int size = queue.size();  
        int levelSum = 0;  
        for (int i = 0; i < size; i++) {  
            NestedInteger current = queue.poll();  
            if (current.isInteger()) levelSum += current.getInteger();  
            List<NestedInteger> nextList = current.getList();  
            if (nextList != null) {  
                for (NestedInteger next: nextList) {  
                    queue.offer(next);  
                }  
            }  
        }  
        prev += levelSum;  
        total += prev;  
    }  
    return total;  
}

思路跟stefan这个做法其实是一样的, 不过stefan对于BFS的写法更加的有个性, 所以最后的代码简洁很多; 这个人这里的这个levelSum其实是多余的, 直接在prev上面加就行了;

当然更直接的方法是可以按照level来计算depth, 不过这个好像要预先知道maxDepth? 所以真正想要做到1pass, 就只能BFS, 而且用这个repeated addition的加法思路来做;

这个解:

The idea is to pass the current found integer sum into the next level of recursion, and return it back again. So that we don't have to count the number of levels in the nested list.

public class Solution {  
    public int depthSumInverse(List<NestedInteger> nestedList) {  
        return helper(nestedList, 0);  
    }  

    private int helper(List<NestedInteger> niList, int prev) {  
        int intSum = prev;  
        List<NestedInteger> levelBreak = new ArrayList<>();  

        for (NestedInteger ni : niList) {  
            if (ni.isInteger()) {  
                intSum += ni.getInteger();  
            } else {  
                levelBreak.addAll(ni.getList());  
            }  
        }  

        int listSum = levelBreak.isEmpty() ? 0 : helper(levelBreak, intSum);  

        return listSum + intSum;  
    }  
}

是stefan说inspire了他的解法;

整体的思路跟Stefan那个解的思路其实是一样的; 只不过这里是用recursion的思路来做, 如果不确定可以自己跑一个小trace(不用太大的, 只要梁三层的就可以了. 另外注意这里这个是一个composite tree, internal node是没有val的);

这个是对于我这种2pass recursion的解法的一个优化:

HashMap solution

We have to find the maxDepth before we can do the sum calculation. So we use a HashMap to record the
integer we visited so far.

After we visited all inputs and got the maxDepth, we can start to calculate the sum.
In the HashMap we don't need to record all integers we visited, we just need to record the sum of integers
in current depth

Time complexity: O(N), N is num of inputs we have
Space complexity: O(H), H is maxDepth

int maxDepth = 0;  

public int depthSumInverse(List<NestedInteger> nestedList) {  
    //HashMap solution. We use HashMap to store nums in each depth before we find the maxDepth  
    //we will do the sum calculation in the last  

    HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>();  

    DFS( nestedList, 1, hs );  

    int sum = 0;  

    //get sum   
    for( int i = 1; i <= maxDepth; i++ ){  
        //put a checker here in case we dont have integer in one layer  
        if( hs.containsKey(i ) ) sum += hs.get(i) * (maxDepth + 1 -i);  
    }  

    return sum;  
}  

private void DFS(List<NestedInteger> nestedList, int depth,  HashMap<Integer, Integer> hs ){  
    //boundary check  

    if(nestedList.isEmpty()) return;  

    //update maxDepth if possible  
    maxDepth = Math.max(maxDepth, depth);  

    for( NestedInteger temp : nestedList ){  
        if( temp.isInteger() ){  
            //if temp is integer  
            if( !hs.containsKey(depth) ){  
                hs.put( depth, temp.getInteger()  );  
            }else{  
                hs.put( depth, hs.get(depth) + temp.getInteger()  );  
            }  
        }else{  
            //if temp is list  
            DFS(  temp.getList(), depth + 1, hs  );  
        }  
    }  
}

他的思路就很简单, 我们如果专门走一个recursion就为了获得maxDepth, 还是太奢侈了, 所以变通一下, 我们就走一个recursion, 在走的过程中先把这个tree整个记录在一个Map里面(depth as key), 然后最后这个recursion结束了以后我们有maxDepth了, 我们就可以计算我们的weighted sum了;

反正sum的计算和maxDepth的计算是没有办法同步进行的, 这里他这个只是跟我这个换了一个思路; 按理说是比我的这种做法快的, 毕竟处理Map比多走一个DFS应该还是快不少的;

这个是另外一个类似的:

Simple one pass dfs solution. Store the values per level in a list, then traverse the result list backwards and multiply by the level number.

public class Solution {  
    public int depthSumInverse(List<NestedInteger> nestedList) {  
        List<Integer> result = dfs(nestedList, 0, new ArrayList<>());  

        int total = 0;  
        for (int index = result.size() - 1; index >= 0; index--) {  
            total += result.get(index) * (result.size() - index);  
        }  

        return total;  
    }  

    List<Integer> dfs(Iterable<NestedInteger> list, int depth, List<Integer> result) {  
        if (depth == result.size()) {  
            result.add(0);  
        }  

        for (NestedInteger integer : list) {  
            if (integer.isInteger()) {  
                result.set(depth, result.get(depth) + integer.getInteger());  
            } else {  
                dfs(integer.getList(), depth + 1, result);  
            }  
        }  

        return result;  
    }  
}

这个可能就是受了LeetCode里面那么多做level list的题目的影响, 他这里就是按照这个思路, 把不同的level的信息保存下来(并不是全部保存, 只保存sum就行了; 另外这个过程是完全可以用DFS来做的, 当时做这类level list的题目这种DFS的解其实见得还是很多的);

这也算是学以致用吧.

反正看到这么多的解, 要么就是2pass, 要么就是BFS的概念来做; 不过这个题目比其他的题目好的一点是, 如果你看到了repeated addition这个intuition, 那么你可以想到一个最优秀的解法, 但是如果你没有想到这个intuition, 你这一题用2pass的笨办法也可以做, 这种题目就比较讲道理;

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.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

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

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

Difficulty:Medium
Total Accepted:14.2K
Total Submissions:27.2K
Contributor: LeetCode
Companies
linkedin
Related Topics
depth-first search
Similar Questions
Nested List Weight Sum Array Nesting