c++, 36 ms, using iterator.


  • 0
     * // 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 NestedIterator {
    public:
        stack<vector<NestedInteger>::iterator> p_stack_;
        vector<NestedInteger>::iterator end_;
        NestedIterator(vector<NestedInteger> &nestedList) {
            if(nestedList.size()) {
                vector<NestedInteger>::iterator it = nestedList.begin();
                end_ = nestedList.end();
                //Fina the first integer and put it at the top of the stack
                while (it != end_ && !helper2(it++));
            }
        }
        int next() {
            vector<NestedInteger>::iterator ni_p = p_stack_.top();
            int r = ni_p->getInteger();
            p_stack_.pop();
            helper(++ni_p);
            return r;
        }
    
        bool hasNext() {
            return !p_stack_.empty();
        }
        void helper(vector<NestedInteger>::iterator ni_p) {
            // If the stack is not empty and the current iterator (at the top of the stack) get to the end,
            // pop the pointer and check the next one
            if (!p_stack_.empty() && ni_p == p_stack_.top()->getList().end()) {
                ni_p = p_stack_.top();
                p_stack_.pop();
                helper(++ni_p);
            }
            else if (!p_stack_.empty() && ni_p != p_stack_.top()->getList().end()) {
                // check whether the next element is integer of NestedInteger, and put them at the right position.
                while (!helper2(ni_p) && ++ni_p != p_stack_.top()->getList().end());
                // if the current pointer reaches end, check the next one.
                if (ni_p == p_stack_.top()->getList().end()) {
                    ni_p = p_stack_.top();
                    p_stack_.pop();
                    helper(++ni_p);
                }
            }
            else if (p_stack_.empty() && ni_p != end_) {
                while (!helper2(ni_p) && ++ni_p != end_);
            }
        }
        
        bool helper2(vector<NestedInteger>::iterator ni_p) {
            p_stack_.push(ni_p);
            if (ni_p->isInteger()) {
                return true;
            } 
            else {
                for (vector<NestedInteger>::iterator it = ni_p->getList().begin(); it != ni_p->getList().end(); it++) {
                    if (helper2(it)){
                        return true;  
                    } 
                }
            }
            p_stack_.pop();
            return false;
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) cout << i.next();
     */

Log in to reply
 

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