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:
- Given the list [[1,1],2,[1,1]]
- return 10. (four 1's at depth 2, one 2 at depth 1)
Example:
- Given the list [1,[4,[6]]]
- return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27)
Python Solution:
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# 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(object):
def _depthSum(self, nestedList, level):
sum = 0
for elm in nestedList:
if elm.isInteger():
sum += level * elm.getInteger()
else:
sum += self._depthSum(elm.getList(), level + 1)
return sum
def depthSum(self, nestedList):
"""
:type nestedList: List[NestedInteger]
:rtype: int
"""
return self._depthSum(nestedList, 1);
C Solution:
/**
* *********************************************************************
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* *********************************************************************
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool NestedIntegerIsInteger(struct NestedInteger *);
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int NestedIntegerGetInteger(struct NestedInteger *);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
*
* // Return the nested list's size that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* int NestedIntegerGetListSize(struct NestedInteger *);
* };
*/
int _depthSum(struct NestedInteger **nestedList, int nestedListSize, int level) {
int i, sum = 0;
for (i = 0; i < nestedListSize; i++) {
if (NestedIntegerIsInteger(nestedList[i])) {
sum += level * NestedIntegerGetInteger(nestedList[i]);
}
else {
sum += _depthSum(NestedIntegerGetList(nestedList[i]), NestedIntegerGetListSize(nestedList[i]), level + 1);
}
}
return sum;
}
int depthSum(struct NestedInteger** nestedList, int nestedListSize) {
return _depthSum(nestedList, nestedListSize, 1);
}
Summary:
- Recusive
LeetCode: 339. Nested List Weight Sum
近期评论