栈专题

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;
    }
}
上一篇下一篇

猜你喜欢

热点阅读