题目描述

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例 1:
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

  • 地址：https://leetcode-cn.com/problems/flatten-nested-list-iterator/
  • 2021/03/23

  • 巨人的肩膀：https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/fu-xue-ming-zhu-xiang-jie-ti-yi-shu-li-d-n4qa/

    法一：递归 + 队列

  • 在构造函数处提前扁平化

  • 遍历嵌套列表的所有元素，判断每个元素的类型（int / list）
    • 如果当前元素是int，那么放入队尾
    • 若是list，则递归遍历该list
  • 时间复杂度 O(n)

  • 空间复杂度 O(n) 

    1. class NestedIterator(object):
    3.   def dfs(self, nests):
    4.       for nest in nests:
    5.           if nest.isInteger(): # 如果是int，则加入队列
    6.               self.queue.append(nest.getInteger())
    7.           else: # 否则就递归遍历子list
    8.               self.dfs(nest.getList())
    10.   def __init__(self, nestedList):
    11.       self.queue = collections.deque()
    12.       self.dfs(nestedList)
    14.   def next(self):
    15.       return self.queue.popleft()
    17.   def hasNext(self):
    18.       return len(self.queue)

    法二：迭代

  • 在调用hasNext() or next() 进行扁平化

    • 一边迭代一边获取当前的结果，而不是提前初始化好
    • 栈
    • 把当前list逆序放入栈中（先进后出）
    • 在hasNext() 中访问栈顶元素
      • 若是int，返回true；然后next()被调用，把栈顶int 弹出
      • 若是list 则把当前列表的各个元素逆序放入栈中
      • 若栈为空则结束，返回false
  • 时间复杂度：O(n)

  • 空间复杂度：O(n)

    1. class NestedIterator(object):
    3.   def __init__(self, nestedList):
    4.       self.stack = []
    5.       for i in range(len(nestedList) - 1, -1, -1): # range(start, stop[, step]) 逆序入栈
    6.           self.stack.append(nestedList[i])
    8.   def next(self):
    9.       cur = self.stack.pop()
    10.       return cur.getInteger()
    12.   def hasNext(self):
    13.       while self.stack:
    14.           cur = self.stack[-1]
    15.           if cur.isInteger():
    16.               return True
    17.           self.stack.pop()
    18.           for i in range(len(cur.getList()) - 1, -1, -1): # 若是子list，则入栈进行迭代
    19.               self.stack.append(cur.getList()[i])
    20.       return False
    1. class NestedIterator {
    2. private:
    3.   stack<NestedInteger> st;
    4. public:
    5.   NestedIterator(vector<NestedInteger> &nestedList) {
    6.       for (int i=nestedList.size() - 1; i>=0; --i) { // 逆序入栈
    7.           st.push(nestedList[i]);
    8.       }
    9.   }
    11.   int next() {
    12.       NestedInteger cur = st.top();
    13.       st.pop();
    14.       return cur.getInteger();
    15.   }
    17.   bool hasNext() {
    18.       while (!st.empty()) {
    19.           NestedInteger cur = st.top();
    20.           if (cur.isInteger()) {
    21.               return true;
    22.           }
    23.           st.pop();
    24.           for (int i=cur.getList().size() - 1; i>=0; --i) {
    25.               st.push(cur.getList()[i]);
    26.           }            
    27.       }
    29.       return false;
    30.   }
    31. };