题目来源

• leetcode：339 嵌套列表权重和

题目描述

给定一个嵌套的整数列表，请返回该列表按深度加权后所有整数的总和。
每个元素要么是整数，要么是列表。同时，列表中元素同样也可以是整数或者是另一个列表。

示例 1:
输入: [[1,1],2,[1,1]]
输出: 10
解释: 因为列表中有四个深度为 2 的 1 ，和一个深度为 1 的 2。

示例 2:
输入: [1,[4,[6]]]
输出: 27
解释: 一个深度为 1 的 1，一个深度为 2 的 4，一个深度为 3 的 6。所以，1 + 42 + 63 = 27。

  // This is the interface that allows for creating nested lists.
  // You should not implement it, or speculate about its implementation
  class NestedInteger {
    
    public:
      // Constructor initializes an empty nested list.
      NestedInteger();
 
      // Constructor initializes a single integer.
      NestedInteger(int value);
 
      // Return true if this NestedInteger holds a single integer, rather than a nested list.
      bool isInteger() const;
 
      // Return the single integer that this NestedInteger holds, if it holds a single integer
      // The result is undefined if this NestedInteger holds a nested list
      int getInteger() const;
 
      // Set this NestedInteger to hold a single integer.
      void setInteger(int value);
 
      // Set this NestedInteger to hold a nested list and adds a nested integer to it.
      void add(const NestedInteger &ni);
 
      // Return the nested list that this NestedInteger holds, if it holds a nested list
      // The result is undefined if this NestedInteger holds a single integer
      const vector<NestedInteger> &getList() const;
 };
class Solution {
    
public:
    int depthSum(vector<NestedInteger>& nestedList) {
    
  
    }
};

题目解析

实现一

class Solution {
    
    int process(NestedInteger ni, int depth){
    
        if(ni.isInteger()){
    
            return depth* ni.getInteger();
        }
        
        int ans = 0;
        for(auto a : ni.getList()){
    
            ans += process(a, depth + 1);
        }
        return ans;
    }
public:
    int depthSum(vector<NestedInteger>& nestedList) {
    
        int ans = 0;
        for(auto a : nestedList){
    
            ans += process(a, 1);
        }
        return ans;
    }
};

实现二

class Solution {
    
public:
    int depthSum(vector<NestedInteger>& nestedList) {
    
        return helper(nestedList, 1);
    }
    int helper(vector<NestedInteger>& nl, int depth) {
    
        int res = 0;
        for (auto a : nl) {
    
            res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
        }
        return res;
    }
};