Leetcode 扁平化嵌套列表迭代器
2021-03-23 本文已影响0人
Yohann丶blog
WechatIMG603.jpeg
题目描述
leetcode 第341题:扁平化嵌套列表迭代器
给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例:
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。
解题方法
栈
参照题解
- 解题思路
创建栈
stack
来存储整型列表nestedList
中的所有整数
因为返回整数的顺序是从左到右,所以需要将nestedList
反转后压栈
在hasNext
中,当stack
有值,且栈顶元素是列表时
弹出栈顶元素,反转后再依次压栈,直到栈顶元素为整数
每次调用hasNext
时,就能保证栈顶元素是整数,直到栈为空
每次调用next
时,弹出栈顶的整数即可
- 复杂度
时间复杂度:初始化和next为O(1),hasNext为均摊O(1)
空间复杂度:O(n)
- 代码实现
python3
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stack = nestedList[::-1]
def next(self) -> int:
return self.stack.pop().getInteger()
def hasNext(self) -> bool:
while self.stack and not self.stack[-1].isInteger():
self.stack += self.stack.pop().getList()[::-1]
return self.stack
php
class NestedIterator {
function __construct($nestedList) {
krsort($nestedList);
$this->stack = $nestedList;
}
function next() {
return array_pop($this->stack)->getInteger();
}
function hasNext() {
while($this->stack && !end($this->stack)->isInteger()){
$list = array_pop($this->stack)->getList();
krsort($list);
$this->stack = array_merge($this->stack,$list);
}
return $this->stack;
}
}