题目不让我干什么，我偏要干什么 :: labuladong的算法小抄

[labuladong]

文章链接点这里：题目不让我干什么，我偏要干什么

评论礼仪 见这里，违者直接拉黑。

[jswxwxf]

一个 js 版的简单的数组扁平懒迭代器。

class NestedIterator {
  constructor(nestedList) {
    this._list = nestedList;
  }

  [Symbol.iterator]() {
    return this;
  }

  next() {
    // 循环拆分列表元素，直到列表第一个元素是整数类型
    while (this._list.length > 0 && Array.isArray(this._list[0])) {
      // 当列表开头第一个元素是列表类型时
      // 将第一个列表打平并按顺序添加到开头
      this._list.unshift(...this._list.shift());
    }
    const done = this._list.length === 0;
    return { value: this._list.shift(), done };
  }
}

let nestedList = new NestedIterator([[1, [7, 8], 3], 2, [4, 6]]);
for (const i of nestedList) {
  console.log(i);
}

[PanggNOTlovebean]

我觉得无论是dfs先扁平所有数字还是每次拉平首个元素，都没有很好得利用【迭代器】和【递归】的性质。
更合理的实现是【递归】利用每一个NestedInteger自己的【迭代器】，使用cursor来指示下一个位置，如果下一个位置是数字，则输出，否则使用下一个NestedInteger的迭代器访问。

public class NestedIterator implements Iterator<Integer> {
    List<NestedInteger> nestedList;
    NestedIterator iterator;
    int cursor;
    int size;
    public NestedIterator(List<NestedInteger> nestedList) {
        this.nestedList=nestedList;
        iterator=null;
        size=nestedList.size();
        cursor=-1;
    }

    @Override
    public Integer next() {
        if(iterator==null) return nestedList.get(cursor).getInteger();
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        if(iterator!=null && iterator.hasNext()) return true;
        while(++cursor<size){
            if(nestedList.get(cursor).isInteger()){
                iterator=null;
                return true;
            }
            iterator=new NestedIterator(nestedList.get(cursor).getList());
            if(iterator.hasNext()) return true;
        }
        return false;
    }
}

[Hyuvo]

有点不太明白为什么hasNext那里add的时候要从后面数然后addFirst呢？正着数然后add不可以吗？是addFirst() 比 add()复杂度低吗？

[Hyuvo]

噢我知道了，是把nested list unnest然后按原顺序放回去

[1103337638]

将最后的hasnext改了改，时间复杂度大幅度降低
@OverRide
public boolean hasNext() {
while(!list.isEmpty() && !list.get(0).isInteger()){
LinkedList temp =new LinkedList(list.remove(0).getList());
while(!temp.isEmpty()){
list.addFirst(temp.removeLast());//这里复杂度应该还有点儿高吧
}
}
//还是我改进后的时间复杂度低一些
return !list.isEmpty();

}

[zhangmuwuge]

可以看看lisp