难度: Medium
Submission
运行时间: 28 ms
内存: 0.0 MB
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
if not nestedList:
return 0
#pass level number to helper function
self.depth = 0
self.d = collections.defaultdict(list)
def helper(curr_list,level):
if curr_list.isInteger():
self.d[level].append(curr_list.getInteger())
self.depth = max(self.depth,level)
return
for ele in curr_list.getList():
helper(ele,level+1)
return
for nested in nestedList:
helper(nested,1)
res = 0
for k in self.d:
for v in self.d[k]:
res+=(self.depth-k+1)*v
return res
Explain
这个题解的思路是使用深度优先搜索（DFS）遍历嵌套列表，将每个整数元素及其对应的深度存储在字典 d 中。在 DFS 过程中，记录嵌套列表的最大深度 depth。最后，遍历字典 d，对于每个深度 k 的元素，将其值乘以 (depth-k+1)，并累加到结果 res 中。这样就可以得到嵌套列表的加权和，其中深度越大的元素权重越小。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
if not nestedList:
return 0
self.depth = 0
self.d = collections.defaultdict(list)
def helper(curr_list, level):
"""
DFS 遍历嵌套列表，将整数元素及其对应的深度存储在字典 d 中
"""
if curr_list.isInteger():
self.d[level].append(curr_list.getInteger())
self.depth = max(self.depth, level)
return
for ele in curr_list.getList():
helper(ele, level+1)
return
# 对每个嵌套列表进行 DFS 遍历
for nested in nestedList:
helper(nested, 1)
res = 0
# 遍历字典 d，计算加权和
for k in self.d:
for v in self.d[k]:
res += (self.depth - k + 1) * v
return res
Explore
在DFS遍历中，当遇到一个空的嵌套列表时，由于列表中没有任何元素（整数或更深的列表），该函数不会进一步递归或添加任何内容到字典d中。这种情况下，空的嵌套列表简单地被忽略，不会对最大深度或最终的加权和产生影响。处理空嵌套列表的策略是合理的，因为它们不包含任何数值，因此不应该对结果有贡献。
是的，递归实现的深度优先搜索可能在处理非常深的嵌套列表时导致栈溢出错误，这是因为每进入更深一层的嵌套列表，都会增加一次递归调用堆栈。在实际应用中，如果预期嵌套结构非常深，可以考虑使用迭代的方法和显式的栈来代替递归调用，以避免栈溢出问题。
在字典`d`中，以深度为键，同一深度的整数存储为列表的形式，这些整数是按照DFS遍历的顺序添加的。在计算加权和时，遍历这些列表的顺序并不影响最终结果，因为最终结果是基于整数值和其深度的加权和，而与整数在列表中的顺序无关。因此，只要保证所有的整数都被正确地加入并计算，顺序就不会影响最终的加权和结果。
这种加权方法的逻辑是反转传统的加权和方法，其中通常最内层的元素（深度最大）权重最低。在此题解中，最内层的元素（深度最大）获得的权重最高，即`(self.depth - k + 1)`最大，这样可以强调更深层次的元素的重要性。这种加权策略可能是为了解决特定问题或满足题目的特定要求，使得深层次的数据具有更高的影响力。