Shortest C++ solution


  • 0
    Q
    //the critical part is hasNext() which consists of three parts:
    //    1) find the next valid NestedInteger, say p
    //    2) if p is an integer or we can't find one, then break
    //    3) if p is a list, push it into stack and goto step 1
    
    class NestedIterator {
    public:
        stack<pair<vector<NestedInteger>,int>>s;
        
        NestedIterator(vector<NestedInteger> &nestedList) {
            s.push(make_pair(nestedList, -1));
        }
        
        int next() {
            return s.top().first[s.top().second].getInteger();
        }
    
        bool hasNext() {
            while(s.size()){
                while(s.size() && ++s.top().second == s.top().first.size()) s.pop();
                if(s.empty() || s.top().first[s.top().second].isInteger()) break;
                s.push(make_pair(s.top().first[s.top().second].getList(), -1));
            }
            return s.size();
        }
    };

  • 0
    A

    If you use reference instead of copying every vector<NestedInteger>, the performance will be better, both time and space.


  • 0
    X

    Can you post a modified version that uses reference? Seems to me I just need to add a '&' in:

    stack<pair<vector<NestedInteger> &,int>>s;
    

    but that didn't work.


Log in to reply
 

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