嵌套列表加权和

难度: Medium

Submission

运行时间: 22 ms

内存: 16.1 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 depthSum(self, nestedList: List[NestedInteger]) -> int:
        return sum(self.dfs(n, 1) for n in nestedList)
    
    
    def dfs(self, n: NestedInteger, level: int) -> int:
        if n.isInteger():
            return n.getInteger() * level
        return sum(self.dfs(x, level + 1) for x in n.getList())

Explain

这个题解使用深度优先搜索(DFS)的方法来计算嵌套列表的加权和。主要思路是遍历嵌套列表，对于每个元素，如果是整数，则将其乘以当前的深度level并累加到结果中；如果是列表，则递归调用dfs函数，将深度level加1后继续遍历该列表。最后返回所有元素的加权和。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        return sum(self.dfs(n, 1) for n in nestedList)
    
    
    def dfs(self, n: NestedInteger, level: int) -> int:
        # 如果当前元素是整数，则返回其乘以深度level的结果
        if n.isInteger():
            return n.getInteger() * level
        # 如果当前元素是列表，则递归调用dfs函数，将深度level加1
        return sum(self.dfs(x, level + 1) for x in n.getList())

Explore

在深度优先搜索中，算法通过递归地访问每个元素来确保每个嵌套列表的所有元素都被考虑到。对于每个元素，如果它是一个整数，就直接乘以其深度并加到总和中；如果它是一个列表，就递归地调用dfs函数，增加深度，并对列表中的每个元素进行同样的处理。这种递归的结构自然地遍历了嵌套列表的所有层级，因此可以确保计算的完整性和正确性。

将 `level` 作为参数传递可以使每次递归调用都有自己的 `level` 值，这样可以保证在递归过程中各自独立地跟踪深度，避免了全局变量可能引起的混乱和错误。此外，这种方式也增强了函数的封装性和重用性，使得代码更加模块化和易于理解。

确实，如果嵌套列表非常深，递归的深度可能会非常大，导致栈溢出。为了优化这种风险，可以考虑使用迭代的方法来代替递归，如使用栈来手动模拟递归的过程，这样可以更好地控制和管理内存的使用。此外，也可以优化递归算法本身，例如使用尾递归优化（在支持的编程环境中），这样可以减少不必要的栈帧的创建。

使用生成器表达式进行求和的优点在于它不需要一次性存储所有中间结果，从而节省了存储空间。生成器表达式按需计算，仅在需要时产生值，这可以提高内存利用率并可能减少执行时间。相比之下，创建一个中间列表则需要一开始就分配足够的内存来存储所有元素，这在处理大数据量时可能导致内存使用过高。缺点是，使用生成器表达式可能使得调试更加困难，因为生成器的状态不像列表那样容易观察。