题目描述
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
样例
Example 1:
Input: [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1.
Example 2:
Input: [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.
算法1
(DFS) O(n)
top down DFS. 每层累加当前数与depth的乘积
时间复杂度
时间复杂度O(n)
空间复杂度O(n),recursion需要分配stack
参考文献
C++ 代码
class Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
return helper(nestedList,1);
}
int helper(vector<NestedInteger>& list, int depth)
{
int res=0;
for(auto a:list)
{
res+=a.isInteger()? a.getInteger()*depth: helper(a.getList(),depth+1);
}
return res;
}
};
算法2
(BFS) O(n)
层序遍历,每层累加数值与depth的乘积放入res中,非数值的nestedList放入tmp数组中,进入下一层遍历前update原数组并depth++
时间复杂度
时间复杂度O(n)
空间复杂度O(n),tmp数组
参考文献
C++ 代码
class Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
int res=0, depth=1;
while(!nestedList.empty())
{
vector<NestedInteger> tmp;
for(auto node: nestedList)
{
if(node.isInteger())
{
res+=node.getInteger()*depth;
}
else
{
for(auto list: node.getList())
tmp.push_back(list);
}
}
depth++;
nestedList=tmp;
}
return res;
}
};
I’m a random forest, haha
树先生,是你吗