How to Compute Nested List Weight Sum of Any Arrays?

  • 时间：2020-10-06 11:32:45
  • 分类：网络文摘
  • 阅读：142 次

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:
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.

This is the interface that allows for creating nested lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

Depth First Search using Recursion

We can use Depth First Search (easy to implement using recursion) to iterate the list. If it is an integer, we update the sum with the value times depth, otherwise, it is a list, we can recursively call the function to get the partial sum.

In order to do this, we need a helper function which passes the current depth. When recursion calls finish/exit, the stack will restore the depth variable before it invokes the recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    
    int helper(vector<NestedInteger>& nestedList, int depth) {
        int r = 0;
        for (const auto &n: nestedList) {
            if (n.isInteger()) {
                r += n.getInteger() * depth;
            } else {
                r += helper((vector<NestedInteger> &)n.getList(), depth + 1); // depth first search - recursion
            }
        }
        return r;        
    }
};
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    
    int helper(vector<NestedInteger>& nestedList, int depth) {
        int r = 0;
        for (const auto &n: nestedList) {
            if (n.isInteger()) {
                r += n.getInteger() * depth;
            } else {
                r += helper((vector<NestedInteger> &)n.getList(), depth + 1); // depth first search - recursion
            }
        }
        return r;        
    }
};

The above algorithm to compute the nested weight list sum runs at O(N) time where N is the number of integers in the list including the sub-list as each integer is visited exactly once. In the worst case for inputs like [1, [1, [1, [1, ..] .. ] .. ] ..] There will be N depths, thus the space complexity will be O(N) via compiler-generated stacks through recursion.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
如图平行四边形ABCD的周长为72厘米　 每个人都和其他人握了一次手　 客车和货车同时从甲、乙两地的中点反向行驶　 数学题：把一个圆锥沿着高切开，得到了个如下图所示的物体　 数学题：49个桶，32个扁担，问有几个人挑水，几个人抬水？　 学校合唱队有205名学生如果女同学减少25人　 两瓶香水甲瓶用去九分之五　 把含糖5%和含糖8%的两种糖水混合成含糖6%的糖水　 长方形折成梯形求梯形AFDC的面积　 求梯形的腰长是多少米　
评论列表
添加评论