当前位置:网站首页>341. Flatten nested list iterator
341. Flatten nested list iterator
2022-07-06 12:43:00 【Zhang Wenhao】
341. Flatten nested list iterators
Flatten Nested List Iterator
List of articles
Title Description :
Give you a nested list of integers nestedList . Each element is either an integer , Or a list ; The elements of the list may also be integers or other lists . Please implement an iterator to flatten it , So that it can traverse all integers in this list .
Implement the flat iterator class NestedIterator :
NestedIterator(List<NestedInteger> nestedList)
Using nested lists nestedList
Initialize iterator .int next()
Returns the next integer of the nested list .boolean hasNext()
If there are still integers to be iterated , return true ; otherwise , return false .
https://leetcode-cn.com/problems/flatten-nested-list-iterator/
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:
- NestedIterator(List nestedList) Initializes the
iterator with the nested listnestedList
. - int next() Returns the next integer in the nested list.
- boolean hasNext() Returns true if there are still some integers in
the nested list and false otherwise.
Example :
Method
The mathematical formula
We can traverse the entire nested list first , Store all integers in an array , Then traverse the array to achieve next \texttt{next} next and hasNext \texttt{hasNext} hasNext Method .
Java
Depth-First Search (DFS)
/** * // 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 empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
private List<Integer>list;
private int index=0;
private void dfs(List<NestedInteger> nestedList){
if(nestedList.size()==0){
return;
}
for(NestedInteger nestedInteger:nestedList){
if(nestedInteger.isInteger()){
list.add(nestedInteger.getInteger());
}else{
List<NestedInteger>nestedList1=nestedInteger.getList();
dfs(nestedList1);
}
}
}
public NestedIterator(List<NestedInteger> nestedList) {
list=new ArrayList<>();
dfs(nestedList);
}
@Override
public Integer next() {
return list.get(index++);
}
@Override
public boolean hasNext() {
return index<list.size();
}
}
/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */
Queue
/** * // 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 empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
private Queue<Integer>q;
private void dfs(List<NestedInteger> nestedList){
if(nestedList.size()==0){
return;
}
for(NestedInteger nestedInteger:nestedList){
if(nestedInteger.isInteger()){
q.offer(nestedInteger.getInteger());
}else{
List<NestedInteger>nestedList1=nestedInteger.getList();
dfs(nestedList1);
}
}
}
public NestedIterator(List<NestedInteger> nestedList) {
q=new LinkedList<>();
dfs(nestedList);
}
@Override
public Integer next() {
return q.poll();
}
@Override
public boolean hasNext() {
return q.size()!=0;
}
}
/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */
Stack
/** * // 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 empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */
public class NestedIterator implements Iterator<Integer> {
private Stack<NestedInteger>st;
public NestedIterator(List<NestedInteger> nestedList) {
st=new Stack<>();
for(int i=nestedList.size()-1;i>=0;i--){
st.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return st.pop().getInteger();
}
@Override
public boolean hasNext() {
while(!st.isEmpty()){
NestedInteger cur=st.peek();
if(cur.isInteger()){
return true;
}
st.pop();
List<NestedInteger> list=cur.getList();
for(int i=list.size()-1;i>=0;i--){
st.push(list.get(i));
}
}
return false;
}
}
/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */
C++
Depth-First Search (DFS)
/** * // 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 {
private:
vector<int>list;
int index=0;
void dfs(vector<NestedInteger> nestedList){
if(nestedList.size()==0){
return;
}
for(NestedInteger nestedInteger:nestedList){
if(nestedInteger.isInteger()){
list.push_back(nestedInteger.getInteger());
}else{
vector<NestedInteger>nestedList1=nestedInteger.getList();
dfs(nestedList1);
}
}
}
public:
NestedIterator(vector<NestedInteger> &nestedList) {
dfs(nestedList);
}
int next() {
return list[index++];
}
bool hasNext() {
return index<list.size();
}
};
/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */
Queue
/** * // 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 {
private:
queue<int>q;
int index=0;
void dfs(vector<NestedInteger> nestedList){
if(nestedList.size()==0){
return;
}
for(NestedInteger nestedInteger:nestedList){
if(nestedInteger.isInteger()){
q.push(nestedInteger.getInteger());
}else{
vector<NestedInteger>nestedList1=nestedInteger.getList();
dfs(nestedList1);
}
}
}
public:
NestedIterator(vector<NestedInteger> &nestedList) {
dfs(nestedList);
}
int next() {
int front=q.front();
q.pop();
return front;
}
bool hasNext() {
return !q.empty();
}
};
/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */
Stack
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i = nestedList.size() - 1; i >= 0; --i) {
st.push(nestedList[i]);
}
}
int next() {
NestedInteger cur = st.top(); st.pop();
return cur.getInteger();
}
bool hasNext() {
while (!st.empty()) {
NestedInteger cur = st.top();
if (cur.isInteger()) {
return true;
}
st.pop();
for (int i = cur.getList().size() - 1; i >= 0; --i) {
st.push(cur.getList()[i]);
}
}
return false;
}
private:
stack<NestedInteger> st;
};
author :fuxuemingzhu
link :https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/fu-xue-ming-zhu-xiang-jie-ti-yi-shu-li-d-n4qa/
source : Power button (LeetCode)
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
Through screenshots
边栏推荐
- Gateway 根据服务名路由失败,报错 Service Unavailable, status=503
- The master of double non planning left the real estate company and became a programmer with an annual salary of 25W. There are too many life choices at the age of 25
- How to add music playback function to Arduino project
- Easy to use shortcut keys in idea
- FairyGUI摇杆
- [leetcode15] sum of three numbers
- ES6 grammar summary -- Part I (basic)
- About using @controller in gateway
- Pytorch: tensor operation (I) contiguous
- (1) Introduction Guide to R language - the first step of data analysis
猜你喜欢
(五)R语言入门生物信息学——ORF和序列分析
(5) Introduction to R language bioinformatics -- ORF and sequence analysis
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
Redis cache update strategy, cache penetration, avalanche, breakdown problems
Basic operations of databases and tables ----- modifying data tables
History object
Naive Bayesian theory derivation
(1) Introduction Guide to R language - the first step of data analysis
数据库课程设计:高校教务管理系统(含代码)
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
随机推荐
Get the position of the nth occurrence of the string
Office prompts that your license is not genuine pop-up box solution
Fairygui joystick
Knowledge summary of request
Custom view puzzle getcolor r.color The color obtained by colorprimary is incorrect
ES6 grammar summary -- Part I (basic)
JS数组常用方法的分类、理解和运用
By v$rman_ backup_ job_ Oracle "bug" caused by details
Important methods of array and string
ESP8266连接onenet(旧版MQTT方式)
js题目:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。
MySQL占用内存过大解决方案
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
[offer9] implement queues with two stacks
Redis 缓存更新策略,缓存穿透、雪崩、击穿问题
关于Gateway中使用@Controller的问题
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
Particle system for introduction to unity3d Foundation (attribute introduction + case production of flame particle system)
Game 280 weekly
FairyGUI人物状态弹窗