341. Flatten Nested List Iterator -M !!!!!!!!!!!!!!! 方法2，简洁多了

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 

Constraints:

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-106, 106].

A:

在stack中保持 List

/**
 * // 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:
    NestedIterator(vector<NestedInteger>& nestedList) {
        Slist.push(nestedList);
        Sindex.push(0);
    }
    int next() {
        int res = Slist.top()[Sindex.top()].getInteger();
        Sindex.top() += 1;
        return res;
    }
    bool hasNext() { // need allow multiple hasNext() while for a single integer
        while (!Slist.empty()) {
            if (Sindex.top() < Slist.top().size()) {
                auto topVal = Slist.top()[Sindex.top()];
                if (topVal.isInteger()) {
                    return true;
                } else { // now is a list
                    Slist.push(topVal.getList());
                    Sindex.push(0);
                }
            } else { // now we go beyond the current list
                Sindex.pop();
                Slist.pop();
                if (!Sindex.empty()) {
                    Sindex.top() += 1;
                }
            }
        }
        return false;
    }
private:
    stack<vector<NestedInteger>> Slist;
    stack<int> Sindex;
};
/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

******************************************************************

在stack中，直接保持了NestedInteger

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for(int i = nestedList.size()-1; i >= 0 ; i--){
            S.push(nestedList[i]);
        }
    }
    
    int next() {
        auto res =  S.top().getInteger();
        S.pop();
        return res;
    }
    
    bool hasNext() {
        if(S.empty()){
            return false;
        }
        if(S.top().isInteger()){
            return true;
        }else{
            auto top = S.top().getList();
            S.pop();
            for(int i = top.size()-1; i >= 0 ; i--){
                S.push(top[i]);
            }
            return hasNext();
        }
    }
private: 
    stack<NestedInteger> S;
};