Nested List Weight Sum

题目

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 + 4*2 + 6*3 = 27)

解析

1. 这道题定义了一种嵌套链表的结构，链表可以无限往里嵌套，规定每嵌套一层，深度加1，让我们求权重之和，就是每个数字乘以其权重，再求总和

2. 这题考察在短时间内读懂给定的interface的能力（读API的能力）

3. 可以有两种写法：Recursion: 遍历list，当前元素如果是数，则将其乘以当前深度并加到sum里，若当前元素是list，则递归遍历该list，并将深度加1。DFS: 用一个stack来实现。遍历list，将当前元素和深度加入stack中。依次取出栈顶元素，若取出元素为数，则将其乘以其深度并加入sum，若取出元素是list，则将该list中元素依次加入stack中，同时这些元素的深度比之前取出元素深度＋1。

思路

1. after reading the given interface, we know that each level, it comes either integer or list
2. So if it comes to an integer, we multipy its depth, then add the sum to the result
3. If it comes to a list, we use recursive traversal, meanwhile, updating its depth as current depth plus 1

图解

代码

//时间 O(n) 空间 O(k) where k is the max level of depth

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        if(nestedList == null) return 0;
        return dfs(nestedList, 1);
    }
    public int dfs (List<NestedInteger> nestedList, int depth){
        int result = 0;
        for(NestedInteger level : nestedList){
            if(level.isInteger()){
                result += level.getInteger()*depth;
            }else{
                result += dfs(level.getList(), depth+1);
            }
        }
        return result;
    }
}

  //DFS version using stack 
    public int depthSum(List<NestedInteger> nestedList) {
        // Write your code here
        Stack<Node> stack = new Stack<Node>();
        for(int i = 0; i < nestedList.size(); i++){
            stack.push(new Node(1, nestedList.get(i)));
        }

        int sum = 0;
        while(!stack.isEmpty()){
            Node curt = stack.pop();
            if(curt.nestedInteger.isInteger()){
                sum += curt.depth * curt.nestedInteger.getInteger();
            }else{
                List<NestedInteger> list = curt.nestedInteger.getList();
                for(int i = 0; i < list.size(); i++){
                    stack.push(new Node(curt.depth + 1, list.get(i)));
                }
            }
        }

        return sum;
    }
}