algo/di-yi-zhan-da78c/shou-ba-sh-66994/ti-mu-bu-r-552fb/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-66994/ti-mu-bu-r-552fb/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！第 21 期打卡挑战 (https://opedk.xet.tech/s/4ptSo2) 开始报名！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/ti-mu-bu-r-552fb/

[outsmartchad]

c++ version using iterator:

class NestedIterator {
private:
    vector<int> res;
    vector<int>::iterator it;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for(int i=0; i<nestedList.size(); i++){
            traverse(nestedList[i]);
        }
        this->it = res.begin();
    }
    
    void traverse(NestedInteger object){
        if(object.isInteger()){
            res.push_back(object.getInteger());
            return;
        }
        else{
            vector<NestedInteger> list = object.getList();
            for(int i=0; i<list.size(); i++){
                traverse(list[i]);
            }
        }
    }
    int next() {
        int ans = *it;
        it++;
        return ans;
    }
    
    bool hasNext() {
        return it != res.end();
    }
};

Using queue:

class NestedIterator {
private:
    queue<int> res;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for(int i=0; i<nestedList.size(); i++){
            traverse(nestedList[i]);
        }
        
    }
    
    void traverse(NestedInteger object){
        if(object.isInteger()){
            res.push(object.getInteger());
            return;
        }
        else{
            auto list = object.getList();
            for(int i=0; i<list.size(); i++){
                traverse(list[i]);
            }
        }
    }
    int next() {
        int ans = res.front();
        res.pop();
        return ans;
    }
    
    bool hasNext() {
        return !res.empty();
    }
};

[GuochenLiao]

想到的一个类似于binary tree iterative traversal的code，速度一般

public class NestedIterator implements Iterator {
Deque<List> stack;
Deque indStack;
public NestedIterator(List nestedList) {
stack = new ArrayDeque<>();
indStack = new ArrayDeque<>();
stack.offerLast(nestedList);
indStack.offerLast(0);
}

@Override
public Integer next() {
    int position = indStack.pollLast();
    indStack.offerLast(position + 1);
    return stack.peekLast().get(position).getInteger();
}

@Override
public boolean hasNext() {
     while (!stack.isEmpty()) {
        if (indStack.peekLast() < stack.peekLast().size()) {
            NestedInteger next = stack.peekLast().get(indStack.peekLast());
            if (next.isInteger()) {
                return true;
            } else {
                stack.offerLast(next.getList());
                indStack.offerLast(indStack.pollLast() + 1);
                indStack.offerLast(0);
            }
        } else {
            stack.pollLast();
            indStack.pollLast();
        }
    }
    return false;
}

}

[syz6]

【通过力扣测试】

递归使用迭代器，效率低于文中进阶算法

···java
public class NestedIterator implements Iterator {
List nestedList;
int nextIndex;
NestedIterator nextIterator;

public NestedIterator(List<NestedInteger> nestedList) {
    this.nestedList = nestedList;
    nextIndex = 0;
    nextIterator = null;
}

@Override
public Integer next() {
    if (!hasNext()) throw new RuntimeException("no next");

    NestedInteger nextNestedInteger = nestedList.get(nextIndex);
    if (nextNestedInteger.isInteger()) {
        nextIndex++;
        return nextNestedInteger.getInteger();
    }

    return nextIterator.next();
}

@Override
public boolean hasNext() {
    while (nextIndex < nestedList.size()) {
        NestedInteger nextNestedInteger = nestedList.get(nextIndex);
        if (nextNestedInteger.isInteger()) return true;

        if (nextIterator == null) nextIterator = new NestedIterator(nextNestedInteger.getList());
        if(nextIterator.hasNext()) return true;

        nextIndex++;
        nextIterator = null;
    }
    return false;
}

}
···

[petercdcn]

Python:
Init the whole object first. Later I will add one for the "lazy" solution.

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        def traverse(nestedList):
            for item in nestedList:
                if item.isInteger():
                    self._res.append(item.getInteger())
                else:
                    traverse(item.getList())
        
        self._res = []
        self._position = -1
        traverse(nestedList)

    def next(self) -> int:
        self._position += 1
        return self._res[self._position]
    
    def hasNext(self) -> bool:
        return self._position + 1 < len(self._res)

Same as LC solution.

[petercdcn]

Python: 2nd solution

class NestedIterator:
    # Solution 2 is better because it doesn't load the whole memory, does it a lazy way
    def __init__(self, nestedList: [NestedInteger]):
        self._stack = []
        self._stack.append(iter(nestedList))
    
    def next(self) -> int:
        return self._nextVal
        
    def hasNext(self) -> bool:
         while self._stack:
            try:
                elem = next(self._stack[-1])
            except StopIteration:
                self._stack.pop()
                continue

            if elem.isInteger():
                self._nextVal = elem.getInteger()
                return True
            else:
                self._stack.append(iter(elem.getList()))
        
         return False