엔지니어 게시판
LeetCode 솔루션 분류

[interview] 364. Nested List Weight Sum II

작성자 정보

  • mingki 작성
  • 작성일

컨텐츠 정보

본문

Medium
995299Add to ListShare

You 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님의 댓글

  • 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.
# """
# 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()])
전체 178 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


  • 현재 접속자 45 명
  • 오늘 방문자 546 명
  • 어제 방문자 869 명
  • 최대 방문자 1,338 명
  • 전체 회원수 319 명
알림 0