Massive Algorithms: LeetCode 339 - Nested List Weight Sum

LeetCode 339 - 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)

    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    int helper(vector<NestedInteger>& nl, int depth) {
        int res = 0;
        for (auto a : nl) {
            res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
        }
        return res;
    }

https://leetcode.com/discuss/94956/2ms-easy-to-understand-java-solution
The time complexity of my solution is O(n), n is the number of elements or Integer within the list.
the space complexity would be O(k) where k is the max level of depth.

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

public int depthSum(List<NestedInteger> nestedList) { return helper(nestedList, 1); } private int helper(List<NestedInteger> list, int depth) { int ret = 0; for (NestedInteger e: list) { ret += e.isInteger()? e.getInteger() * depth: helper(e.getList(), depth + 1); } return ret; }

https://discuss.leetcode.com/topic/41738/java-dfs-and-bfs-simple-code

    private int sum;
    public int depthSum(List<NestedInteger> nestedList) {
        if (nestedList == null) {
            return 0;
        }
        sum = 0;
        for (NestedInteger nestedInt : nestedList) {
            depthSumHelper(nestedInt, 1);
        }
        return sum;
    }
    
    private void depthSumHelper(NestedInteger nestedInt, int depth) {
        if (nestedInt.isInteger()) {
            sum += depth * nestedInt.getInteger();
            return;
        }
        for (NestedInteger innerInt : nestedInt.getList()) {
            depthSumHelper(innerInt, depth + 1);
        }
    }

X. BFS

https://leetcode.com/discuss/95207/java-solution-similar-to-tree-level-order-traversal

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; }

https://discuss.leetcode.com/topic/44325/simple-java-iterative-solution-10-lines

    public int depthSum(List<NestedInteger> nestedList) {
        int level = 1, total = 0;
        while(nestedList.size() != 0){
            List<NestedInteger> next = new LinkedList<>();
            for(NestedInteger nInt : nestedList){
                if(nInt.isInteger())
                    total += nInt.getInteger() * level;
                else
                    next.addAll(nInt.getList());
            }
            level++;
            nestedList = next;
        }
        return total;
    }

X. Using stack
https://zhengyang2015.gitbooks.io/lintcode/nested_list_weight_sum_551.html

DFS: 用一个stack来实现。遍历list，将当前元素和深度加入stack中。依次取出栈顶元素，若取出元素为数，则将其乘以其深度并加入sum，若取出元素是list，则将该list中元素依次加入stack中，同时这些元素的深度比之前取出元素深度＋1。

class Node{
    int depth;
    NestedInteger nestedInteger;
    public Node(int depth, NestedInteger nestedInteger){
        this.depth = depth;
        this.nestedInteger = nestedInteger;
    }
}
    //DFS version
    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;
    }

https://discuss.leetcode.com/topic/41357/2ms-easy-to-understand-java-solution/6

    public int depthSum(List<NestedInteger> nestedList) {
        int res = 0;
        Stack<Iterator<NestedInteger>> stk = new Stack<>();
        stk.push (nestedList.iterator());
        
        while (!stk.isEmpty()) {
            Iterator<NestedInteger> itr = stk.peek ();
            while (itr.hasNext()) {
                NestedInteger n = itr.next();
                if (n.isInteger()) res += n.getInteger() * stk.size ();
                else {
                    stk.push (n.getList().iterator());
                    break; //??
                }
            }
            if (!stk.peek ().hasNext()) stk.pop ();
        }
        return res;
    }

http://coderchen.blogspot.com/2015/11/getweight-recurseive-structure.html
1 given [1, [2,3], [[4]]], return sum. 计算sum的方法是每向下一个level权重+1，例子的sum = 1 * 1 + (2 + 3) * 2 + 4 * 3。follow up：每向下一个level 权重 - 1， sum = 3 * 1 +（2 + 3）* 2 + 4 * 1
public static class Node {}
public static class ValNode extends Node {
int val;
public ValNode(int v) {
this.val = v;
}
}

public static class ListNode extends Node {
List<Node> nodes;
public ListNode() {
nodes = new ArrayList<Node>();
}

public void addNode(Node node) {
this.nodes.add(node);
}
}

public static int getWeightIncrease(Node node, int weight) {
int res = 0;
if (node instanceof ValNode) {
res += weight * ((ValNode) node).val;
} else {
ListNode list = (ListNode) node;
for (Node child : list.nodes) {
res += getWeightIncrease(child, weight + 1);
}
}
return res;
}

1. 每个node是有个next，还有个child。
2. Leetcode 339 给了了⼀一个嵌套list⽐比如 [1,5,[3,4],2,7,[5,[8],3]]
要求输出字符串串： 1+5+(3+4)* 2+2+7+(5+(8)*3+3)*2
这个input的嵌套结构让⾃自⼰己设计
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/339_Nested_List_Weight_Sum.java

    public int depthSum(List<NestedInteger> nestedList) {
        return helper(nestedList, 1);
    }
    
    private int helper(List<NestedInteger> lists, int depth) {
        int sum = 0;
        for (int i = 0; i < lists.size(); i ++) {
            NestedInteger list = lists.get(i);
            
            if (depth > 1 && i == 0) System.out.print("(");
            if (i > 0) System.out.print(" + ");
            
            if (list.isInteger()) {
                sum += list.getInteger() * depth;
                System.out.print(list.getInteger());
            } else sum += helper(list.getList(), depth + 1);
            
            if (depth > 1 && i == lists.size() - 1)
                System.out.print(") * " + depth);
        }
        return sum;
    }

LeetCode 339 - Nested List Weight Sum

Labels

Popular Posts