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

            while (!list.isEmpty()) {
                NestedInteger curr = list.remove(0);
                if (curr.isInteger()) {
                    sum += curr.getInteger() * depth;
                } else {
                    sum += depthSumHelper(curr.getList(), depth + 1);
                }
            }

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

All Problems

All Solutions