LeetCode 솔루션 분류
[interview] 364. Nested List Weight Sum II
본문
Medium
995299Add to ListShareYou are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.
The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.
The weight of an integer is maxDepth - (the depth of the integer) + 1.
Return the sum of each integer in nestedList multiplied by its weight.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1's with a weight of 1, one 2 with a weight of 2. 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
Example 2:
Input: nestedList = [1,[4,[6]]] Output: 17 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1. 1*3 + 4*2 + 6*1 = 17
Constraints:
1 <= nestedList.length <= 50- The values of the integers in the nested list is in the range
[-100, 100]. - The maximum depth of any integer is less than or equal to
50.
관련자료
-
링크
댓글 2
Coffee님의 댓글
- 익명
- 작성일
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
int maxDepth = 0;
public int depthSumInverse(List<NestedInteger> nestedList) {
Queue<NestedInteger> queue = new LinkedList<>(nestedList);
int tempSum = 0;
int result = 0;
while(!queue.isEmpty()){
int size = queue.size();
while(size-- > 0){
NestedInteger ni = queue.remove();
if(ni.isInteger()){
tempSum += ni.getInteger();
}else{
for(NestedInteger n : ni.getList()){
queue.add(n);
}
}
}
result += tempSum;
}
return result;
}
}학부유학생님의 댓글
- 익명
- 작성일
Runtime: 66 ms, faster than 10.20% of Python3 online submissions for Nested List Weight Sum II.
Memory Usage: 14.2 MB, less than 60.98% of Python3 online submissions for Nested List Weight Sum II.
Memory Usage: 14.2 MB, less than 60.98% of Python3 online submissions for Nested List Weight Sum II.
# """
# 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]
# """
import collections
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
depth_sum = collections.defaultdict(int)
max_depth = 1
deque = collections.deque([(nestedList, 1)])
while deque:
popped, curr_depth = deque.popleft()
max_depth = max(max_depth, curr_depth)
for item in popped:
if item.isInteger(): depth_sum[curr_depth] += item.getInteger()
else:
deque.append((item.getList(), curr_depth+1))
return sum([depth_sum[depth]*(max_depth - depth+1) for depth in depth_sum.keys()])
