查找嵌套列表权重和 II

给定一个整数嵌套列表 INLINECODE40cc31a8。每个元素要么是一个整数，要么是一个列表，而列表中的元素也可以是整数或其他列表。整数的“深度”是指它所在的列表层数。例如，在嵌套列表 INLINECODE010ecc8c 中，每个整数的深度值已经确定。

让我们定义 maxDepth 为任意整数的最大深度。一个整数的权重定义为 maxDepth – (整数的深度) + 1。

我们的任务是找出 nestedList 中每个整数乘以其权重后的总和。

示例：

> 输入： nestedList = [[1, 1], 2, [1, 1]]

> 输出： 8

> 解释： 四个 1 的权重为 1，一个 2 的权重为 2。 11 + 11 + 22 + 11 + 1*1 = 8

>

>

>

> 输入： nestedList = [1, [3, [5]]]

> 输出： 14

> 解释： 一个 1 的深度为 3，一个 3 的深度为 2，一个 5 的深度为 1； 13 + 32 + 5*1 = 14)

算法思路： 为了解决这个问题，我们可以遵循以下思路：

> 我们可以通过 递归地展平嵌套列表来解决这个问题，同时跟踪每个元素的深度并计算遇到的最大深度。然后，遍历展平后的列表，利用最大深度和每个元素的深度来计算其深度和权重。最后，返回这些深度和权重的总和。

分步算法：

• 初始化一个空列表 flats，用于存储展平后的元素及其深度。
• 初始化 max_depth 用于存储遇到的最大深度。
• 定义一个函数 INLINECODEfd3bc7d1，接收嵌套列表、当前深度、INLINECODEc2873737 列表和 max_depth 作为参数。
• 遍历嵌套列表中的每个元素：
• 如果该元素是整数，将其及其对应的深度添加到 flats 中。
• 如果该元素是一个嵌套列表，则递归调用 INLINECODEe77c5998，传入该列表、深度加 1、INLINECODEca8b396e 和 max_depth。
• 将 INLINECODE48144031 更新为当前深度和 INLINECODEec6c8ac7 中的最大值。
• 定义一个函数 depth_sum_inverse，接收嵌套列表并返回深度和权重的结果。
• 调用 INLINECODEc74edc0d 函数，传入嵌套列表、初始深度 0、INLINECODEf2b3b095 列表和 max_depth。
• 通过遍历 INLINECODEec10ea0d 来计算深度和权重，将每个元素与 INLINECODE5a79ea21 的乘积相加。
• 返回计算出的深度和权重。

下面是算法的实现：

C++

`

#include 
#include 
#include 

// 表示嵌套整数的抽象基类，它可以是
// 一个整数，也可以是一个整数的嵌套列表。
class NestedInteger {
public:
    virtual ~NestedInteger() {}
    // 如果此 NestedInteger 持有单个整数，
    // 则返回 true，而不是嵌套列表。
    virtual bool isInteger() const = 0;
    // 如果此 NestedInteger 持有单个整数，
    // 则返回该整数。
    virtual int getInteger() const = 0;
    // 如果此 NestedInteger 持有嵌套列表，
    // 则返回该列表。
    virtual const std::vector&
    getList() const = 0;
};

// NestedInteger 的具体实现，用于持有单个整数。
class Integer : public NestedInteger {
    int value;

public:
    Integer(int value)
        : value(value)
    {
    }
    bool isInteger() const override { return true; }
    int getInteger() const override { return value; }
    const std::vector&
    getList() const override
    {
        throw std::runtime_error("This is not a list");
    }
};

// NestedInteger 的具体实现，用于持有
// NestedInteger 对象的列表。
class List : public NestedInteger {
    std::vector list;

public:
    List(const std::vector& list)
        : list(list)
    {
    }
    ~List()
    {
        for (auto item : list) {
            delete item; // 清理内存以防止泄漏
        }
    }
    bool isInteger() const override { return false; }
    int getInteger() const override
    {
        throw std::runtime_error("This is not an integer");
    }
    const std::vector&
    getList() const override
    {
        return list;
    }
};

// 将嵌套列表展平为简单的整数列表，
// 并记录它们关联的深度。
void flatten(const NestedInteger& ni, int depth,
             std::vector<std::pair >& flatList,
             int& maxDepth)
{
    if (ni.isInteger()) {
        flatList.push_back({ ni.getInteger(), depth });
        maxDepth = std::max(maxDepth, depth);
    }
    else {
        for (auto item : ni.getList()) {
            flatten(*item, depth + 1, flatList, maxDepth);
        }
    }
}

// 计算嵌套列表的逆向深度和。
int depthSumInverse(
    const std::vector& nestedList)
{
    std::vector<std::pair > flatList;
    int maxDepth = 0;
    for (auto item : nestedList) {
        flatten(*item, 0, flatList, maxDepth);
    }

    int sum = 0;