0341. 扁平化嵌套列表迭代器【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归展开

1. 📝 题目描述

• leetcode

给你一个嵌套的整数列表 nestedList。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

• NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
• int next() 返回嵌套列表的下一个整数。
• boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false。

你的代码将会用下述伪代码检测：

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

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

---

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

---

提示：

• 1 <= nestedList.length <= 500
• 嵌套列表中的整数值在范围 [-10^6, 10^6] 内

2. 🎯 s.1 - 递归展开

c

struct NestedIterator {
    int* data;
    int size;
    int index;
};

void flatten(struct NestedInteger** nestedList, int nestedListSize, int** data, int* size, int* cap) {
    for (int i = 0; i < nestedListSize; i++) {
        if (NestedIntegerIsInteger(nestedList[i])) {
            if (*size == *cap) { *cap *= 2; *data = realloc(*data, sizeof(int) * (*cap)); }
            (*data)[(*size)++] = NestedIntegerGetInteger(nestedList[i]);
        } else {
            int subSize;
            struct NestedInteger** sub = NestedIntegerGetList(nestedList[i], &subSize);
            flatten(sub, subSize, data, size, cap);
        }
    }
}

struct NestedIterator* nestedIterCreate(struct NestedInteger** nestedList, int nestedListSize) {
    struct NestedIterator* iter = (struct NestedIterator*)malloc(sizeof(struct NestedIterator));
    int cap = 64;
    iter->data = (int*)malloc(sizeof(int) * cap);
    iter->size = 0;
    iter->index = 0;
    flatten(nestedList, nestedListSize, &iter->data, &iter->size, &cap);
    return iter;
}

bool nestedIterHasNext(struct NestedIterator* iter) {
    return iter->index < iter->size;
}

int nestedIterNext(struct NestedIterator* iter) {
    return iter->data[iter->index++];
}

void nestedIterFree(struct NestedIterator* iter) {
    free(iter->data); free(iter);
}

js

/**
 * @param {NestedInteger[]} nestedList
 */
var NestedIterator = function (nestedList) {
  this.stack = []
  const flatten = (list) => {
    for (const item of list) {
      if (item.isInteger()) this.stack.push(item.getInteger())
      else flatten(item.getList())
    }
  }
  flatten(nestedList)
  this.index = 0
}

/**
 * @return {number}
 */
NestedIterator.prototype.next = function () {
  return this.stack[this.index++]
}

/**
 * @return {boolean}
 */
NestedIterator.prototype.hasNext = function () {
  return this.index < this.stack.length
}

py

class NestedIterator:
    def __init__(self, nestedList):
        self.data = []
        def flatten(lst):
            for item in lst:
                if item.isInteger():
                    self.data.append(item.getInteger())
                else:
                    flatten(item.getList())
        flatten(nestedList)
        self.index = 0

    def next(self) -> int:
        val = self.data[self.index]
        self.index += 1
        return val

    def hasNext(self) -> bool:
        return self.index < len(self.data)

• 时间复杂度：初始化 $O(n)$，next/hasNext 均为 $O(1)$，其中 $n$ 是所有整数个数
• 空间复杂度：$O(n)$

算法思路：

• 初始化时递归展开所有嵌套列表，将所有整数存入一个数组
• next 和 hasNext 直接操作数组索引