嵌套列表加权和 II
难度:
标签:
题目描述
代码结果
运行时间: 28 ms, 内存: 0.0 MB
/*
* 题目思路：
* 1. 使用Java Stream API来解决这个问题。
* 2. 先计算最大深度，然后使用递归函数和Stream来计算加权和。
*/
import java.util.List;
public class NestedListWeightSumIIStream {
public int depthSumInverse(List<NestedInteger> nestedList) {
int maxDepth = getMaxDepth(nestedList);
return helper(nestedList, maxDepth);
}
private int getMaxDepth(List<NestedInteger> nestedList) {
return nestedList.stream().mapToInt(ni -> ni.isInteger() ? 1 : getMaxDepth(ni.getList()) + 1).max().orElse(1);
}
private int helper(List<NestedInteger> nestedList, int depth) {
return nestedList.stream().mapToInt(ni -> ni.isInteger() ? ni.getInteger() * depth : helper(ni.getList(), depth - 1)).sum();
}
}
解释
方法:
这个题解的思路是使用深度优先搜索（DFS）遍历嵌套列表，将每个整数元素及其对应的深度存储在字典 d 中。在 DFS 过程中，记录嵌套列表的最大深度 depth。最后，遍历字典 d，对于每个深度 k 的元素，将其值乘以 (depth-k+1)，并累加到结果 res 中。这样就可以得到嵌套列表的加权和，其中深度越大的元素权重越小。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在处理嵌套列表时，DFS函数似乎假设每个元素要么是一个整数要么是另一个嵌套列表。如果遇到不带任何元素的嵌套列表，该如何处理？
▷🦆
在代码中，`self.depth`用于记录最大深度。如果嵌套列表非常深，这种方法的递归深度是否可能导致栈溢出错误？
▷🦆
你是如何保证在字典`d`中以深度为键，所有同一深度的整数为值的列表是按顺序访问的？是否有可能出现访问顺序对结果有影响的情况？
▷🦆
在计算最终的加权和时，你使用了`(self.depth - k + 1) * v`作为加权因子。这种加权方法背后的逻辑是什么？为什么选择这样的加权方式？
▷相关问题
数组嵌套
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示：
1 <= nums.length <= 1050 <= nums[i] < nums.lengthA中不含有重复的元素。