Question

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

 364	Nested List Weight Sum II

 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.

 Different from the previous question where weight is increasing from root to leaf,
 now the weight is defined from bottom up. i.e., the leaf level integers have weight 1,
 and the root level integers have the largest weight.

 Example 1:
 Input: [[1,1],2,[1,1]]
 Output: 8
 Explanation: Four 1's at depth 1, one 2 at depth 2.

 Example 2:
 Input: [1,[4,[6]]]
 Output: 17
 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

Algorithm

This question is an extension of the previous Nested List Weight Sum. The difference is that the deeper the depth, the smaller the weight, which is just the opposite of the previous one.

But the idea of solving the problem has not changed, you can still use DFS to do it, because you don’t know how deep the final depth is when traversing, you can directly accumulate the results when you can’t traverse.

The initial idea was to create a two-dimensional array during the traversal process, save the numbers of each layer, and finally know the depth, then calculate the weight sum.

But, to do it better, we can use two variables unweighted and weighted are used, the non-weighted sum and the weighted sum, which are initialized to 0.

  • If nestedList is not empty to start the loop, declare an empty array nextLevel first, traverse the elements in nestedList,
    • If it is a number, then the non-weight sum plus this number,
    • If it is an array, add nextLevel, After the traversal is completed, the number sum of the first level is stored in unweighted, and the rest of the elements are stored in nextLevel.

At this time, unweighted is added to weighted, and nextLevel is assigned to nestedList, so that it enters the next layer of calculation.

Since the value of the previous layer is still in unweighted, when the second layer is calculated and unweighted is added to weighted, it is equivalent to the sum of the numbers of the first layer being added twice, which perfectly meets the requirements.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Nested_List_Weight_Sum_II {
    /**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public interface NestedInteger {
     *     // Constructor initializes an empty nested list.
     *     public NestedInteger();
     *
     *     // Constructor initializes a single integer.
     *     public NestedInteger(int value);
     *
     *     // @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();
     *
     *     // Set this NestedInteger to hold a single integer.
     *     public void setInteger(int value);
     *
     *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
     *     public void add(NestedInteger ni);
     *
     *     // @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();
     * }
     */


    class Solution_onePass {

        public int depthSumInverse(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            int unweighted = 0, weighted = 0;
            while (!nestedList.isEmpty()) {

                List<NestedInteger> nextLevel = new ArrayList<>();

                for (NestedInteger a : nestedList) {
                    if (a.isInteger()) {
                        unweighted += a.getInteger();
                    } else {
                        nextLevel.add(nextLevel.size(), a); // append to rear
                    }
                }

                weighted += unweighted;
                nestedList = nextLevel;
            }

            return weighted;
        }
    }

    class Solution {
        private int maxDepth = 0;
        public int depthSumInverse(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            getDepth(1, nestedList);

            return depthSumHelper(maxDepth, nestedList);
        }

        private void getDepth(int level, List<NestedInteger> nestedList) {
            maxDepth = Math.max(maxDepth, level);
            for (NestedInteger n : nestedList) {
                if (!n.isInteger()) {
                    getDepth(level + 1, n.getList());
                }
            }
        }

        private int depthSumHelper(int depth, List<NestedInteger> nestedList) {
            int sum = 0;
            for (NestedInteger n : nestedList) {
                if (n.isInteger()) {
                    sum += depth * n.getInteger();
                } else {
                    sum += depthSumHelper(depth - 1, n.getList());
                }
            }

            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