341-扁平化嵌套列表迭代器(Flatten Nested List Iterator)
发表于：2021-12-03 | 分类： 中等
字数统计: 2.4k | 阅读时长: 9分钟 | 阅读量：

原文链接: 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<NestedInteger> 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.

Your code will be tested with the following pseudocode:

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

If res matches the expected flattened list, then your code will be judged as correct.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 

Constraints:

  • 1 <= nestedList.length <= 500
  • The values of the integers in the nested list is in the range [-106, 106].

中文题目

给你一个嵌套的整数列表 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
  • 嵌套列表中的整数值在范围 [-106, 106] 内

通过代码

高赞题解

各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 58 天。今天力扣上的每日一题是「341. 扁平化嵌套列表迭代器」。

题意解析

今天的题意略难理解，需要我翻译一下，理解题意的朋友请跳过。

本题定义了一个类 NestedInteger ，这个类可以存储 int  或 List<NestedInteger> ；所以称它是一个「嵌套列表」。类似于一棵多叉树，每个节点都可以有很多子节点。

它有三个方法：

  • isInteger() ，判断当前存储的对象是否为 int；
  • getInteger() , 如果当前存储的元素是 int 型的，那么返回当前的结果 int，否则调用会失败；
  • getList() ，如果当前存储的元素是 List<NestedInteger> 型的，那么返回该 List，否则调用会失败。

而「扁平化嵌套列表迭代器」说的是，我们需要设计一个迭代器，这个迭代器是把「嵌套列表」铺平（拆包）成各个 int，然后每次调用 hasNext() 来判断是否有下一个整数，通过 next() 返回下一个整数。

注意迭代器是一种按照特定顺序对数据结构遍历的方式，它的调用方式是：

i, v = NestedIterator(nestedList), []
while i.hasNext():
	v.append(i.next())

解题思路

本文有两种主要的思路：

  1. 在构造函数中提前「扁平化」整个嵌套列表；
  2. 在调用 hasNext() 或者 next() 方法的时候扁平化当前的嵌套的子列表。

一、递归：构造函数中提前「扁平化」整个嵌套列表

这是最简单的方法，但是我认为这不是面试官想要的方法。

在构造函数中提前扁平化整个嵌套列表。那么在 hasNext() 或者 next() 可以很简单地返回迭代器位置的 int。

因为这个嵌套的数据结构有点类似于多叉树，所以我们可以按照类似地遍历思路：递归。

承载遍历结果的数据结构可以使用数组，那么另外需要一个整数标记当前的迭代器指向的位置；也可以使用一个队列，每次调用 next() 方法的时候从队列的开头弹出一个元素。

递归的思路比较简单，我用的是队列：

  • 遍历输入的「嵌套列表」所有的元素，判断每个元素是 int 还是 list；
    • 如果当前元素是 int，放入队列尾部；
    • 如果当前元素是 list，那么需要对当前 子list 继续递归；

其余代码比较简单，不作赘述。

[]
class NestedIterator(object):
    def dfs(self, nests):
        for nest in nests:
            if nest.isInteger():
                self.queue.append(nest.getInteger())
            else:
                self.dfs(nest.getList())
                    
    def __init__(self, nestedList):
        self.queue = collections.deque()
        self.dfs(nestedList)

    def next(self):
        return self.queue.popleft()

    def hasNext(self):
        return len(self.queue)
  • 时间复杂度：构造函数的时间复杂度是 $O(N)$； next() 和 hasNext() 的时间复杂度是 $O(1)$。
  • 空间复杂度：$O(N)$。

二、迭代：调用 hasNext() 或者 next() 方法的时候扁平化当前的嵌套的子列表

这个方法更加有挑战性，也是这个题最正确的解法。因为对于大部分情况，我们希望迭代器能够一边迭代一边获取当前的结果，而不是提前初始化好。

把递归方法 转 迭代方法，我们需要用到「栈」。

在递归方法中，我们在遍历时如果遇到一个嵌套的 子list，就立即处理该 子list，直到全部展开；
在迭代方法中，我们不需要全部展开，只需要把 当前list 的所有元素放入 list 中。

由于「栈」的先进后出的特性，我们需要逆序在栈里放入各个元素。

处理流程分为两步：

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

算法整体的流程，通过举例说明。假如输入 [1, [2,3]] 。

1. 在构造函数中：栈里面放的应该是 stack = [[2, 3], 1]
2. 在调用 hasNext() 方法时，访问栈顶元素是 1，为 int，那么直接返回 true;
3. 然后调用 next() 方法，弹出栈顶元素 1；
4. 再调用 hasNext() 方法时，访问栈顶元素是 [2,3]，为 list，那么需要摊平，继续放到栈中。
        当前的栈是 stack = [3, 2]
5. 然后调用 next() 方法，弹出栈顶元素 2；
6. 然后调用 next() 方法，弹出栈顶元素 3；
7. 再调用 hasNext() 方法时，栈为空，因此返回 false，迭代器运行结束。

这里需要说一下为什么在 hasNext() 方法中摊平 list，而不是在 next() 方法中。比如对于 [[]] 的输入， hasNext()  方法是判断其中是否有 int 元素了，则必须把内层的 list 摊平来看，发现是空的，返回 false。

代码如下：

[]
class NestedIterator(object):

    def __init__(self, nestedList):
        self.stack = []
        for i in range(len(nestedList) - 1, -1, -1):
            self.stack.append(nestedList[i])
        

    def next(self):
        cur = self.stack.pop()
        return cur.getInteger()

    def hasNext(self):
        while self.stack:
            cur = self.stack[-1]
            if cur.isInteger():
                return True
            self.stack.pop()
            for i in range(len(cur.getList()) - 1, -1, -1):
                self.stack.append(cur.getList()[i])
        return False
[]
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;
};
  • 时间复杂度：构造函数的最坏时间复杂度是 $O(N)$； next() 和 hasNext() 的最坏时间复杂度是 $O(N)$。
  • 空间复杂度：$O(N)$。

刷题心得

面试的时候需要写出方法二，今天的题目很好，请务必掌握呀。

参考资料：
力扣官方题解
341. Flatten Nested List Iterator

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

统计信息

通过次数 提交次数 AC比率
53229 73216 72.7%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
展开二维向量 中等
锯齿迭代器 中等
迷你语法分析器 中等
数组嵌套 中等
深度优先搜索 树 设计 栈 队列 迭代器
上一篇:
338-比特位计数(Counting Bits)
下一篇:
342-4的幂(Power of Four)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo