Simple C++ using a map


  • 0
    U
        /**
         * // This is the interface that allows for creating nested lists.
         * // You should not implement it, or speculate about its implementation
         * class NestedInteger {
         *   public:
         *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
         *     bool isInteger() const;
         *
         *     // 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 getInteger() const;
         *
         *     // 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
         *     const vector<NestedInteger> &getList() const;
         * };
         */
        class Solution {
        public:
            void helper(vector<NestedInteger>& nestedList, int depth, map<int,int> &M)
            {
                for(int i=0; i<nestedList.size(); i++)
                {
                    if(nestedList[i].isInteger())
                    {
                       // accumulate all integers in same depth
                        if(M.find(depth) == M.end())
                        {
                            M[depth] = nestedList[i].getInteger();
                        }
                        else
                        {
                            M[depth] += nestedList[i].getInteger();
                        }
                    }
                    else
                    {
                        helper(nestedList[i].getList(), depth + 1, M);
                    }
                }
            }
            
            int depthSumInverse(vector<NestedInteger>& nestedList) {
                int ret = 0;
                map<int,int>M;
                helper(nestedList,1,M);
                if(M.empty())return 0;
                auto it = prev(M.end(),1);
                int higestDepth = it->first, depth = 1;
                for(auto iter = M.begin(); iter != M.end(); ++iter)
                {
                    depth = higestDepth - iter->first + 1;
                    ret += depth*iter->second;
                }
                return ret;
            }
        };

Log in to reply
 

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