Share my 2ms intuitive-one pass-no multiplication solution


  • 28
    L

    The idea is to pass the current found integer sum into the next level of recursion, and return it back again. So that we don't have to count the number of levels in the nested list.

    I think code itself is quite self explanatory.

    public class Solution {
        public int depthSumInverse(List<NestedInteger> nestedList) {
            return helper(nestedList, 0);
        }
        
        private int helper(List<NestedInteger> niList, int prev) {
            int intSum = prev;
            List<NestedInteger> levelBreak = new ArrayList<>();
            
            for (NestedInteger ni : niList) {
                if (ni.isInteger()) {
                    intSum += ni.getInteger();
                } else {
                    levelBreak.addAll(ni.getList());
                }
            }
            
            int listSum = levelBreak.isEmpty()? 0 : helper(levelBreak, intSum);
    
            return listSum + intSum;
        }
    }

  • 0

    Nice, though I like it better this way.


  • 0
    L

    Thanks, Stefan.


  • 0

    Wrong answer with the test case of [1,[4,[6,[[[]]] ] ]]


  • 0
    L

    @yubad2000 I am not sure this is a valid test case given the problem specification.


  • 0

    @StefanPochmann I don't know why your iteration version is much slower than his recursion version. Can you explain some?


  • 0

    @zhugejunwei No idea what you're talking about. I just retested both three times, @lzb700m's solution got 5ms, 7ms and 5ms while mine got 5ms, 5ms and 5ms.


  • 0

    @StefanPochmann Well, maybe it's leetcode issue when I tested it. Sry about that.


  • 1

    Share:

        public int depthSumInverse(List<NestedInteger> nestedList) {
                    
                return helper(nestedList, 0);
        }
        
        private int helper(List<NestedInteger> nestedList, int sum){
                
                List<NestedInteger> nextList = new ArrayList();
                for(NestedInteger nestedInt: nestedList){
                    if(nestedInt.isInteger()){
                        sum += nestedInt.getInteger();        
                    }else{
                        nextList.addAll(nestedInt.getList());
                    }
                }   
                
                // 从第1层加到第n层,每一次递归,前面的sum被重复添加一次。
                sum += nextList.isEmpty()? 0 : helper(nextList, sum);
                return sum;
        }

  • 0
    J

    Very nice! Here is the python code:

    def depthSumInverse(self, nestedList, prev = 0):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        isum = prev
        ilist = []
        for i in nestedList:
            if i.isInteger():
                isum += i.getInteger()
            else:
                ilist.extend(i.getList())
        lsum = 0 if not ilist else self.depthSumInverse(ilist, isum)
        return isum + lsum
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.