| comments | difficulty | edit_url | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
给你一个嵌套的整数列表 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]内
根据题意要求可以将 NestedInteger 数据结构视作一个 N 叉树，当元素为一个整数时，该节点是 N 叉树的叶子节点，当元素为一个整数数组时，该节点是 N 叉树的非叶子节点，数组中的每一个元素包含子树的所有节点。故直接递归遍历 N 叉树并记录所有的叶子节点即可。
# """
# 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
# """
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
def dfs(nestedList):
for e in nestedList:
if e.isInteger():
self.vals.append(e.getInteger())
else:
dfs(e.getList())
self.vals = []
dfs(nestedList)
self.cur = 0
def next(self) -> int:
res = self.vals[self.cur]
self.cur += 1
return res
def hasNext(self) -> bool:
return self.cur < len(self.vals)
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
private List<Integer> vals;
private Iterator<Integer> cur;
public NestedIterator(List<NestedInteger> nestedList) {
vals = new ArrayList<>();
dfs(nestedList);
cur = vals.iterator();
}
@Override
public Integer next() {
return cur.next();
}
@Override
public boolean hasNext() {
return cur.hasNext();
}
private void dfs(List<NestedInteger> nestedList) {
for (NestedInteger e : nestedList) {
if (e.isInteger()) {
vals.add(e.getInteger());
} else {
dfs(e.getList());
}
}
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*//**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class NestedIterator {
public:
NestedIterator(vector<NestedInteger>& nestedList) {
dfs(nestedList);
}
int next() {
return vals[cur++];
}
bool hasNext() {
return cur < vals.size();
}
private:
vector<int> vals;
int cur = 0;
void dfs(vector<NestedInteger>& nestedList) {
for (auto& e : nestedList) {
if (e.isInteger()) {
vals.push_back(e.getInteger());
} else {
dfs(e.getList());
}
}
}
};
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
*//**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (this NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (this NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (this *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (this NestedInteger) GetList() []*NestedInteger {}
*/
type NestedIterator struct {
iterator []int
index, length int
}
func Constructor(nestedList []*NestedInteger) *NestedIterator {
result := make([]int, 0)
var traversal func(nodes []*NestedInteger)
traversal = func(nodes []*NestedInteger) {
for _, child := range nodes {
if child.IsInteger() {
result = append(result, child.GetInteger())
} else {
traversal(child.GetList())
}
}
}
traversal(nestedList)
return &NestedIterator{iterator: result, index: 0, length: len(result)}
}
func (this *NestedIterator) Next() int {
res := this.iterator[this.index]
this.index++
return res
}
func (this *NestedIterator) HasNext() bool {
return this.index < this.length
}/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
class NestedIterator {
private vals: number[];
private index: number;
constructor(nestedList: NestedInteger[]) {
this.index = 0;
this.vals = [];
this.dfs(nestedList);
}
dfs(nestedList: NestedInteger[]) {
for (const v of nestedList) {
if (v.isInteger()) {
this.vals.push(v.getInteger());
} else {
this.dfs(v.getList());
}
}
}
hasNext(): boolean {
return this.index < this.vals.length;
}
next(): number {
return this.vals[this.index++];
}
}
/**
* Your ParkingSystem object will be instantiated and called as such:
* var obj = new NestedIterator(nestedList)
* var a: number[] = []
* while (obj.hasNext()) a.push(obj.next());
*/// #[derive(Debug, PartialEq, Eq)]
// pub enum NestedInteger {
// Int(i32),
// List(Vec<NestedInteger>)
// }
struct NestedIterator {
index: usize,
vals: Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl NestedIterator {
fn dfs(nestedList: &Vec<NestedInteger>, vals: &mut Vec<i32>) {
for ele in nestedList.iter() {
match ele {
NestedInteger::Int(val) => vals.push(*val),
NestedInteger::List(list) => Self::dfs(list, vals),
}
}
}
fn new(nestedList: Vec<NestedInteger>) -> Self {
let mut vals = vec![];
Self::dfs(&nestedList, &mut vals);
Self {
vals,
index: 0,
}
}
fn next(&mut self) -> i32 {
let res = self.vals[self.index];
self.index += 1;
res
}
fn has_next(&self) -> bool {
self.index < self.vals.len()
}
}/**
* Your NestedIterator object will be instantiated and called as such:
* let obj = NestedIterator::new(nestedList);
* let ret_1: i32 = obj.next();
* let ret_2: bool = obj.has_next();
*/调用 hasNext 时，如果 nestedList 的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型。 调用 Next 方法时，由于 hasNext() 方法已确保 nestedList 第一个元素为整数类型，直接返回即可。
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (this NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (this NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (this *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (this NestedInteger) GetList() []*NestedInteger {}
*/
type NestedIterator struct {
nested *list.List
}
func Constructor(nestedList []*NestedInteger) *NestedIterator {
nested := list.New()
for _, v := range nestedList {
nested.PushBack(v)
}
return &NestedIterator{nested: nested}
}
func (this *NestedIterator) Next() int {
res := this.nested.Front().Value.(*NestedInteger)
this.nested.Remove(this.nested.Front())
return res.GetInteger()
}
func (this *NestedIterator) HasNext() bool {
for this.nested.Len() > 0 && !this.nested.Front().Value.(*NestedInteger).IsInteger() {
front := this.nested.Front().Value.(*NestedInteger)
this.nested.Remove(this.nested.Front())
nodes := front.GetList()
for i := len(nodes) - 1; i >= 0; i-- {
this.nested.PushFront(nodes[i])
}
}
return this.nested.Len() > 0
}