Solution using stack c++


  • 0
    Y
    /**
     * // 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 {
        stack<NestedInteger> s;
        NestedInteger i;
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            // Initialize your data structure here.
            for(int j = nestedList.size() - 1; j >= 0; j--)
                s.push(nestedList[j]);
            while(!s.empty() && !s.top().isInteger()) {
                i = s.top();
                s.pop();
                for(int j = i.getList().size() - 1; j >= 0; j--)
                    s.push(i.getList()[j]);
            }
        }
    
        // @return {int} the next element in the iteration
        int next() {
            // Write your code here
            int ret = s.top().getInteger();
            s.pop();
            return ret;
        }
    
        // @return {boolean} true if the iteration has more element or false
        bool hasNext() {
            // Write your code here
            while(!s.empty() && !s.top().isInteger()) {
                i = s.top();
                s.pop();
                for(int j = i.getList().size() - 1; j >= 0; j--)
                    s.push(i.getList()[j]);
            }
            return !s.empty();
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) v.push_back(i.next());
     */

Log in to reply
 

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