Share my C++ solutions: two-pass and BFS


  • 0
    G

    Two-pass:

    class Solution {
    private:
        void find_height(vector<NestedInteger>& nestedList, int cur_level, int& max_level) {
            max_level = max(max_level, cur_level);
            for (auto& x : nestedList)
                if (!x.isInteger()) 
                    find_height(x.getList(), cur_level + 1, max_level);
        }
        
        int level_sum(vector<NestedInteger>& nestedList, int cur_level) {
            int sum = 0;
            for (auto& x : nestedList) {
                if (x.isInteger()) sum += cur_level * x.getInteger();
                else sum += level_sum(x.getList(), cur_level - 1);
            }
            return sum;
        }
    public:
        int depthSumInverse(vector<NestedInteger>& nestedList) {
            int max_level = 0, sum = 0;
            find_height(nestedList, 1, max_level);
            return level_sum(nestedList, max_level);
        }
    };
    

    BFS:

    class Solution {
    public:
        int depthSumInverse(vector<NestedInteger>& nestedList) {
            typedef vector<NestedInteger>::iterator ListIterator;
            queue<pair<ListIterator, ListIterator>> nextQueue;
            queue<pair<ListIterator, ListIterator>> curQueue;
            int weighted = 0, unweighted = 0;
            nextQueue.push({nestedList.begin(), nestedList.end()});
            while (!nextQueue.empty()) {
                swap(curQueue, nextQueue);
                while (!curQueue.empty()) {
                    auto first = curQueue.front().first, last = curQueue.front().second;
                    curQueue.pop();
                    for (; first != last; ++first) {
                        if (first -> isInteger()) 
                            unweighted += first -> getInteger();
                        else 
                            nextQueue.push({first -> getList().begin(), first -> getList().end()});
                    }
                }
                weighted += unweighted;
            }
            return weighted;
        }
    };

Log in to reply
 

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