Swift 解法详解 LeetCode 364：嵌套列表加权和 II

摘要

这道题听名字就知道，是跟“加权”有关的。但跟之前的「嵌套列表加权和」不一样，这次的权重不是随着深度增加，而是随着深度减少。换句话说，最外层的数权重最大，最里层的权重最小。

其实这就很像我们的工作汇报：

• 老板最看重大方向（外层的东西），权重很大。
• 具体的小细节（深层次的东西）虽然也重要，但加的分不多。

接下来，我们就通过代码来一步一步把问题拆解。

描述

题目要求：给你一个嵌套的整数列表，每个元素要么是整数，要么是列表。
需要计算所有整数的 加权和，其中权重是 最大深度减去当前深度 + 1。

举个例子：

输入: nestedList = [[1,1],2,[1,1]]
输出: 8

解释:
- 最大深度是 2
- 最外层元素的权重 = 2
- 最里层元素的权重 = 1
=> (1+1+1+1)*1 + 2*2 = 8

再比如：

输入: nestedList = [1,[4,[6]]]
输出: 17

解释:
- 最大深度是 3
- 权重分布：
  - 1 在第一层，权重 3
  - 4 在第二层，权重 2
  - 6 在第三层，权重 1
=> 1*3 + 4*2 + 6*1 = 17

题解答案

我们先想下解题套路：

1. 第一步，得知道整个嵌套列表的最大深度。
2. 第二步，遍历列表里的每个整数，算出它的权重并累加。
3. 最后得到总和。

所以解题的思路可以分为 两次遍历：

• 第一次找最大深度。
• 第二次用最大深度来反推每个数的权重，再算和。

题解代码分析

下面是 Swift 的完整代码（带详细注释和 Demo）：

import Foundation

// 模拟 NestedInteger 接口
class NestedInteger {
    private var integer: Int?
    private var list: [NestedInteger]?

    init(_ value: Int) {
        self.integer = value
    }

    init(_ list: [NestedInteger]) {
        self.list = list
    }

    func isInteger() -> Bool {
        return integer != nil
    }

    func getInteger() -> Int? {
        return integer
    }

    func getList() -> [NestedInteger]? {
        return list
    }
}

class Solution {
    // 主函数：计算加权和
    func depthSumInverse(_ nestedList: [NestedInteger]) -> Int {
        // 第一步：获取最大深度
        let maxDepth = getMaxDepth(nestedList)
        // 第二步：计算加权和
        return getWeightedSum(nestedList, depth: 1, maxDepth: maxDepth)
    }

    // 获取最大深度
    private func getMaxDepth(_ nestedList: [NestedInteger]) -> Int {
        var depth = 1
        for ni in nestedList {
            if let list = ni.getList() {
                depth = max(depth, 1 + getMaxDepth(list))
            }
        }
        return depth
    }

    // 根据最大深度反推权重
    private func getWeightedSum(_ nestedList: [NestedInteger], depth: Int, maxDepth: Int) -> Int {
        var sum = 0
        for ni in nestedList {
            if ni.isInteger() {
                let weight = maxDepth - depth + 1
                sum += (ni.getInteger() ?? 0) * weight
            } else if let list = ni.getList() {
                sum += getWeightedSum(list, depth: depth + 1, maxDepth: maxDepth)
            }
        }
        return sum
    }
}

// MARK: - Demo 演示
let solution = Solution()

// 示例 1: [[1,1],2,[1,1]]
let nested1 = [
    NestedInteger([NestedInteger(1), NestedInteger(1)]),
    NestedInteger(2),
    NestedInteger([NestedInteger(1), NestedInteger(1)])
]
print("结果1: \(solution.depthSumInverse(nested1))") // 8

// 示例 2: [1,[4,[6]]]
let nested2 = [
    NestedInteger(1),
    NestedInteger([NestedInteger(4), NestedInteger([NestedInteger(6)])])
]
print("结果2: \(solution.depthSumInverse(nested2))") // 17

代码拆解

1. NestedInteger 类：
   因为 LeetCode 提供的是一个接口，我们自己写 Demo 就模拟了一个简单的类，方便测试。

2. 获取最大深度：
   递归遍历每个子列表，把最深的深度返回。

3. 加权和计算：
   再次递归，算每个整数的权重，权重公式是 (maxDepth - 当前深度 + 1)。

4. Demo 测试：
   分别跑了两组样例，结果正确。

示例测试及结果

运行结果：

结果1: 8
结果2: 17

说明算法是对的。

你也可以自己加一个：

// 示例 3: [ [2], [3, [1]] ]
let nested3 = [
    NestedInteger([NestedInteger(2)]),
    NestedInteger([NestedInteger(3), NestedInteger([NestedInteger(1)])])
]
print("结果3: \(solution.depthSumInverse(nested3))")

时间复杂度

• 遍历两次整个嵌套列表。
• 假设总共有 n 个整数，时间复杂度就是 O(n)。

空间复杂度

• 递归调用栈的深度，最坏情况下等于最大嵌套深度。
• 所以空间复杂度是 O(d)，其中 d 是最大深度。

总结

这道题的精髓是「权重和深度的反向关系」。
做法也很清晰：

1. 先算最大深度。
2. 再用最大深度来算权重。

这类题在实际开发里也能举一反三：
比如做项目预算的时候，外层的大块预算占比更高，细节的小预算影响相对较小。
又或者做日志分析，越靠前的日志信息（外层）可能权重更大，越靠后的细枝末节影响就小一点。