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)
    
    

All Problems

All Solutions