Leetcode 339. Nested List Weight Sum

题目

Given a nested list of integers, return the sum of all integerss 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:

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

Example 2:

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

思路

题目要求我们对nestedList进行求和。仔细读题我们发现,nestedList中要么为普通的Integer(我们可以直接求和), 要么为下一层nestedList(需要我们继续用相同的方法求和)。这提示我们应用递归的思想,因为我们在不断的处理性质相同的问题。 不过,值得注意的是,求和时需要将每个元素按照其深度加权。递归恰好能帮我们完成这一点:我们只需要在递归/DFS时,记录当前层数即可。

解答

/**
 * // 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 {

    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }

    // Recursively unnest list and find sum
    private int dfs(List<NestedInteger> nestedList, int level) {
        if (nestedList.size() == 0) return 0;
        int sum = 0;
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {                
                sum += (ni.getInteger() * level);
            }
            else {
                sum += dfs(ni.getList(), level + 1);
            }
        }
        return sum;
    }
}

Complexity Analysis:

  • Time Complexity: O(n). 我们需要通过DFS遍历所有的NestedElement(包括Integer和NestedList)。

  • Space Complexity: O(n). 递归每往下一层就需要占用一次stack space,因此最坏情况下需要O(n)的栈空间。

拓展

  • 如果不用递归,而仅采用循坏,我们可以解决这道题吗?两者有什么区别呢?

总结

这类题目相对基础,但是依然需要我们核心的两个步骤:一为判断出这道题目考察知识点为Graph, DFS和递归; 二为我们熟练地bug-free地完成代码的书写。

Reference

Last updated

Was this helpful?