[LintCode] Flatten Nested List Iterator 压平嵌套链表迭代器
2024-09-13 07:19:49
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example
Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
LeetCode上的原题，请参见我之前的博客Flatten Nested List Iterator。但是不太明白的是，那篇博客中的解法三可以通过LeetCode的OJ，在LintCode上跑就有错误，不知道啥原因。
解法一：
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i = nestedList.size() - ; i >= ; --i) {
s.push(nestedList[i]);
}
}
int next() {
NestedInteger t = s.top(); s.pop();
return t.getInteger();
}
bool hasNext() {
while (!s.empty()) {
NestedInteger t = s.top();
if (t.isInteger()) return true;
s.pop();
for (int i = t.getList().size() - ; i >= ; --i) {
s.push(t.getList()[i]);
}
}
return false;
}
private:
stack<NestedInteger> s;
};
解法二：
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto a : nestedList) {
d.push_back(a);
}
}
int next() {
NestedInteger t = d.front(); d.pop_front();
return t.getInteger();
}
bool hasNext() {
while (!d.empty()) {
NestedInteger t = d.front();
if (t.isInteger()) return true;
d.pop_front();
for (int i = ; i < t.getList().size(); ++i) {
d.insert(d.begin() + i, t.getList()[i]);
}
}
return false;
}
private:
deque<NestedInteger> d;
};
最新文章
- Mybatis框架 的快速入门
- tp框架的增删改查
- UTC时间和本地时间的区别
- 【JUC】JDK1.8源码分析之ReentrantLock（三）
- Java避免创建不必要的对象
- Blend 2015 教程 （四）控件模板
- shell 中 &&和||的方法
- http://www.cnblogs.com/0201zcr/p/4987561.html
- WEB前端的原理及组成
- canvas API ，通俗的canvas基础知识（二）
- 夺命雷公狗---DEDECMS----33dedecms自定义搜索以及分页功能完成
- Dockpanel的控件加载问题
- (转)Redis 集群方案
- Php开源项目大全
- [项目记录] 用c语言完成的一个学生成绩管理系统
- XenServer多网卡绑定
- Kb和KB的区别
- 安卓开发----TextView控件属性列表（转）
- List集合实现简易学生管理
- 工作中用到和应该知道的eclipse快捷键