【python】Leetcode每日一题-扁平化嵌套列表迭代器
【python】Leetcode每日一题-扁平化嵌套列表迭代器
【题目描述】
给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例1:
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例2:
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。
【分析】
-
AC代码:
# """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ #class NestedInteger: # def isInteger(self) -> bool: # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # """ # # def getInteger(self) -> int: # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # """ # # def getList(self) -> [NestedInteger]: # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # """ global nested nested = [] class NestedIterator: def __init__(self, nestedList): for x in nestedList: if x.isInteger(): nested.append(x.getInteger()) else: NestedIterator(x.getList()) def next(self) -> int: return nested.pop(0) def hasNext(self) -> bool: if(len(nested) == 0): return False return True
-
有兄弟是用正则表达式直接写的
-
官方:
-
dfs
-
public class NestedIterator implements Iterator
{ private Stack stack; public NestedIterator(List nestedList) { stack = new Stack<>(); for (int i=nestedList.size()-1;i>=0;i--) { stack.push(nestedList.get(i)); } } @Override public Integer next() { NestedInteger temp = stack.pop(); return temp.getInteger(); } @Override public boolean hasNext() { while (!stack.isEmpty()) { NestedInteger temp = stack.peek(); if (temp.isInteger()) return true; stack.pop(); for (int i=temp.getList().size()-1;i>=0;i--) { stack.push(temp.getList().get(i)); } } return false; } }
-