扁平化嵌套列表迭代器

递归+队列

  1. 解题思路：

    • 提供的方法，3 个内置的 API：
      • isInteger()：判断元素是否为数字
      • getInteger()：获取数字元素
      • getList()：获取非数字元素
    • 嵌套的整型列表是一个树形结构，树上的叶子节点对应一个整数，非叶节点对应一个列表；
    • 做了预处理，直接将 nestedList[] 扁平化处理；
    • 严格意义上，不算是迭代器，迭代器是一步一步操作的，而不是在执行构造函数的时候预处理直接全部处理完；

  2. 复杂度：

    • 时间复杂度：初始化为 O(n)，next 和 hasNext 为 O(1)，其中 n 是嵌套的整型列表中的元素个数；
    • 空间复杂度：O(n)，需要一个数组存储嵌套的整型列表中的所有元素；

  3. 代码实现：

    TS
    js
    class NestedIterator {
    queue: Array<number | Array<number>>;

    constructor(nestedList: NestedInteger[]) {
        this.queue = [];
        this.flatArray(nestedList);
    }

    flatArray(arr): void {
        for (let i = 0; i < arr.length; i++) {
            if (arr[i].isInteger()) {
                this.queue.push(arr[i].getInteger());
            } else {
                this.flatArray(arr[i].getList());
            }
        }
    }

    hasNext(): boolean {
        return this.queue.length > 0;
    }

    next(): number {
        return this.queue.shift() as number;
    }
}

    var NestedIterator = function (nestedList) {
    this.queue = []
    this.flatArray(nestedList)
};

NestedIterator.prototype.flatArray = function (arr) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i].isInteger()) {
            this.queue.push(arr[i].getInteger())
        } else {
            this.flatArray(arr[i].getList())
        }
    }
}

NestedIterator.prototype.hasNext = function () {
    return this.queue.length > 0
};

NestedIterator.prototype.next = function () {
    return this.queue.shift()
};

迭代+栈

  1. 解题思路：

    • 在构造函数中应该初始化，把当前列表的各个元素（不用摊平）逆序放入栈中；
    • 在 hasNext() 方法中，访问（不弹出）栈顶元素，判断是否为「数字」：
      • 如果是「数字」那么说明有下一个元素，返回 true；然后 next() 就会被调用，把栈顶的「数字」弹出；
      • 如果是 list 需要把当前列表的各个元素（不用摊平）逆序放入栈中；
      • 如果栈为空，那么说明原始的嵌套列表已经访问结束了，返回 false；

  2. 复杂度：

    • 时间复杂度：初始化和 next 为 O(1)，hasNext 为均摊 O(1)；
    • 空间复杂度：O(n)，最坏情况下嵌套的整型列表是一条链，需要一个 O(n) 大小的栈来存储链上的所有元素；

  3. 代码实现：

    var NestedIterator = function (nestedList) {
    this.stack = [];
    // 将 nestedList 逆序放入 栈中
    for (let i = nestedList.length - 1; i >= 0; i--) {
        this.stack.push(nestedList[i]);
    }
};

NestedIterator.prototype.next = function () {
    return this.hasNext() ? this.stack.pop().getInteger() : -1;
};

NestedIterator.prototype.hasNext = function () {
    if (this.stack.length === 0) {
        return false;
    }
    let stackTop = this.stack[this.stack.length - 1];
    if (stackTop.isInteger()) {
        return true;
    } else {
        stackTop = this.stack.pop();
        let list = stackTop.getList();
        for (let i = list.length - 1; i >= 0; i--) {
            this.stack.push(list[i]);
        }
        return this.hasNext();
    }
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 扁平化嵌套列表迭代器
  2. 2. 递归+队列
  3. 3. 迭代+栈