341. Flatten nested list iterator

341. Flatten nested list iterators
Flatten Nested List Iterator

---

Title Description ：

Give you a nested list of integers nestedList . Each element is either an integer , Or a list ; The elements of the list may also be integers or other lists . Please implement an iterator to flatten it , So that it can traverse all integers in this list .

Implement the flat iterator class NestedIterator ：

• NestedIterator(List<NestedInteger> nestedList) Using nested lists nestedList
  Initialize iterator .
• int next() Returns the next integer of the nested list .
• boolean hasNext() If there are still integers to be iterated , return true ; otherwise , return false .

https://leetcode-cn.com/problems/flatten-nested-list-iterator/

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 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.

Example :

Method

The mathematical formula

We can traverse the entire nested list first , Store all integers in an array , Then traverse the array to achieve $\text{next}$ and $\text{hasNext}$ Method .

Java

Depth-First Search (DFS)

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
    
    private List<Integer>list;
    private int index=0;
    private void dfs(List<NestedInteger> nestedList){
    
        if(nestedList.size()==0){
    
            return;
        }
        for(NestedInteger nestedInteger:nestedList){
    
            if(nestedInteger.isInteger()){
    
                list.add(nestedInteger.getInteger());
            }else{
    
                List<NestedInteger>nestedList1=nestedInteger.getList();
                dfs(nestedList1);
            }
        }
    }

    public NestedIterator(List<NestedInteger> nestedList) {
    
        list=new ArrayList<>();
        dfs(nestedList);
    }

    @Override
    public Integer next() {
    
        return list.get(index++);
    }

    @Override
    public boolean hasNext() {
    
        return index<list.size();
    }
}

/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */

Queue

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
    
    private Queue<Integer>q;
    private void dfs(List<NestedInteger> nestedList){
    
        if(nestedList.size()==0){
    
            return;
        }
        for(NestedInteger nestedInteger:nestedList){
    
            if(nestedInteger.isInteger()){
    
                q.offer(nestedInteger.getInteger());
            }else{
    
                List<NestedInteger>nestedList1=nestedInteger.getList();
                dfs(nestedList1);
            }
        }
    }

    public NestedIterator(List<NestedInteger> nestedList) {
    
        q=new LinkedList<>();
        dfs(nestedList);
    }

    @Override
    public Integer next() {
    
        return q.poll();
    }

    @Override
    public boolean hasNext() {
    
        return q.size()!=0;
    }
}

/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */

Stack

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
    
    private Stack<NestedInteger>st;
    public NestedIterator(List<NestedInteger> nestedList) {
    
        st=new Stack<>();
        for(int i=nestedList.size()-1;i>=0;i--){
    
            st.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
    
        return st.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
    
        while(!st.isEmpty()){
    
            NestedInteger cur=st.peek();
            if(cur.isInteger()){
    
                return true;
            }
            st.pop();
            List<NestedInteger> list=cur.getList();
            for(int i=list.size()-1;i>=0;i--){
    
                st.push(list.get(i));
            }
        }
        return false;
    }
}

/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */

C++

Depth-First Search (DFS)

/** * // 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 {
    
private:
    vector<int>list;
    int index=0;
    void dfs(vector<NestedInteger> nestedList){
    
        if(nestedList.size()==0){
    
            return;
        }
        for(NestedInteger nestedInteger:nestedList){
    
            if(nestedInteger.isInteger()){
    
                list.push_back(nestedInteger.getInteger());
            }else{
    
                vector<NestedInteger>nestedList1=nestedInteger.getList();
                dfs(nestedList1);
            }
        }
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
    
        dfs(nestedList);
    }
    
    int next() {
    
        return list[index++];
    }
    
    bool hasNext() {
    
        return index<list.size();
    }
};

/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */

Queue

/** * // 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 {
    
private:
    queue<int>q;
    int index=0;
    void dfs(vector<NestedInteger> nestedList){
    
        if(nestedList.size()==0){
    
            return;
        }
        for(NestedInteger nestedInteger:nestedList){
    
            if(nestedInteger.isInteger()){
    
                q.push(nestedInteger.getInteger());
            }else{
    
                vector<NestedInteger>nestedList1=nestedInteger.getList();
                dfs(nestedList1);
            }
        }
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
    
        dfs(nestedList);
    }
    
    int next() {
    
        int front=q.front();
        q.pop();
        return front;
    }
    
    bool hasNext() {
    
        return !q.empty();
    }
};

/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */

Stack

class NestedIterator {
    
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
    
        for (int i = nestedList.size() - 1; i >= 0; --i) {
    
            st.push(nestedList[i]);
        }
    }

    int next() {
    
        NestedInteger cur = st.top(); st.pop();
        return cur.getInteger();
    }

    bool hasNext() {
    
        while (!st.empty()) {
    
            NestedInteger cur = st.top();
            if (cur.isInteger()) {
    
                return true;
            }
            st.pop();
            for (int i = cur.getList().size() - 1; i >= 0; --i) {
    
                st.push(cur.getList()[i]);
            }
        }
        return false;
    }
private:
    stack<NestedInteger> st;
};


 author ：fuxuemingzhu
 link ：https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/fu-xue-ming-zhu-xiang-jie-ti-yi-shu-li-d-n4qa/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Through screenshots