Question

Formatted question description: https://leetcode.ca/all/339.html

 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)

Algorithm

Traverse the given nested linked list array, for each nested linked list object, call the dfs function, assign a depth value of 1, and add up and return. In the dfs function, first determine whether it is an integer,

If yes, it returns the current depth multiplied by an integer
If not, then we traverse the nested array again, call the recursive function for each nested linked list, and add up the return value to return

Code

Java

import java.util.List;

public class Nested_List_Weight_Sum {
    /**
     * // 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 class Solution_dfs {
        public int depthSum(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            return depthSumHelper(nestedList, 1);
        }

        private int depthSumHelper(List<NestedInteger> list, int depth) {
            if (list.isEmpty()) {
                return 0;
            }

            int sum = 0;

            for (NestedInteger curr: list){
                // for each in list, perform a dfs
                if (curr.isInteger()) {
                    sum += curr.getInteger() * depth;
                } else {
                    sum += depthSumHelper(curr.getList(), depth + 1);
                }
            }

            return sum;
        }
    }

    public class Solution_stack {

        /*
            用一个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;
            }
        }

        public int depthSum(List<NestedInteger> nestedList) {

            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 current = stack.pop();
                if (current.nestedInteger.isInteger()) {
                    sum += current.depth * current.nestedInteger.getInteger();
                } else {
                    List<NestedInteger> list = current.nestedInteger.getList();
                    for (int i = 0; i < list.size(); i++) {
                        stack.push(new Node(current.depth + 1, list.get(i)));
                    }
                }
            }

            return sum;
        }
    }

    // This is the interface that allows for creating nested lists.
    // You should not implement it, or speculate about its implementation
    private 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();
    }
}

// OJ: https://leetcode.com/problems/nested-list-weight-sum/
// Time: O(N)
// Space: O(D) where D is the max depth of the list.
class Solution {
private:
    int depthSum(vector<NestedInteger>& nestedList, int depth) {
        int sum = 0;
        for (auto &i : nestedList) {
            if (i.isInteger()) sum += i.getInteger() * depth;
            else sum += depthSum(i.getList(), depth + 1);
        }
        return sum;
    }
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return depthSum(nestedList, 1);
    }
};

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class Solution(object):
  def depthSum(self, nestedList):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """

    def helper(root, depth):
      res = 0
      for nested in root:
        if nested.isInteger():
          res += depth * nested.getInteger()
        else:
          res += helper(nested.getList(), depth + 1)
      return res

    return helper(nestedList, 1)

339 - Nested List Weight Sum

Question

Algorithm

Code

All Problems

All Solutions