251. Flatten 2D Vector
题目:
Implement an iterator to flatten a 2d vector.
For example,
Given 2d vector =
[
[1,2],
[3],
[4,5,6]
]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6]
.
Hint:
- How many variables do you need to keep track?
- Two variables is all you need. Try with
x
andy
. - Beware of empty rows. It could be the first few rows.
- To write correct code, think about the invariant to maintain. What is it?
- The invariant is
x
andy
must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it? - Not sure? Think about how you would implement
hasNext()
. Which is more complex? - Common logic in two different places should be refactored into a common method.
Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.
链接: http://leetcode.com/problems/flatten-2d-vector/
题解:
构造一个2D的iterator。不太理解iterator的原理,第一想法是把vec2d里面的元素都读到Queue里 ,然后再逐个读取。这样的话初始化需要O(n), next和hasNext都为O(1),Space Complexity也是O(n),虽然能ac,但是当vec2d足够大的时候会出问题。
Time Complexity - constructor - O(n), hasNext - O(1), next() - O(1), Space Complexity - O(n)。
public class Vector2D {
private Queue<Integer> vec1d; public Vector2D(List<List<Integer>> vec2d) {
vec1d = new LinkedList<>();
for(List<Integer> list : vec2d) {
for(int i : list) {
vec1d.offer(i);
}
}
} public int next() {
if(hasNext())
return vec1d.poll();
else
return Integer.MAX_VALUE;
} public boolean hasNext() {
return vec1d.size() > 0;
}
} /**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Update: 保存两个变量来遍历vec2d
public class Vector2D {
private List<List<Integer>> list;
private int listIndex;
private int elemIndex; public Vector2D(List<List<Integer>> vec2d) {
list = vec2d;
listIndex = 0;
elemIndex = 0;
} public int next() {
return list.get(listIndex).get(elemIndex++);
} public boolean hasNext() {
while(listIndex < list.size()) {
if(elemIndex < list.get(listIndex).size()) {
return true;
} else {
listIndex++;
elemIndex = 0;
}
} return false;
}
} /**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
二刷:
使用了ArrayList的iterator,这个算不算作弊...思路就是,一开始把vec2d里面每个list的iterator都加入到一个iters的ArrayList里。之后就可以很简单地写好hasNext()和next()两个方法了。
Java:
public class Vector2D implements Iterator<Integer> {
private List<Iterator<Integer>> iters;
private int curLine = 0; public Vector2D(List<List<Integer>> vec2d) {
this.iters = new ArrayList<>();
for (List<Integer> list : vec2d) {
iters.add(list.iterator());
}
} @Override
public Integer next() {
return iters.get(curLine).next();
} @Override
public boolean hasNext() {
while (curLine < iters.size()) {
if (iters.get(curLine).hasNext()) return true;
else curLine++;
}
return false;
}
} /**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Update:
还是使用两个元素来遍历
public class Vector2D implements Iterator<Integer> {
private List<List<Integer>> list;
private int curLine = 0;
private int curElem = 0; public Vector2D(List<List<Integer>> vec2d) {
this.list = vec2d;
} @Override
public Integer next() {
return list.get(curLine).get(curElem++);
} @Override
public boolean hasNext() {
while (curLine < list.size()) {
if (curElem < list.get(curLine).size()) {
return true;
} else {
curLine++;
curElem = 0;
}
}
return false;
}
} /**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Reference:
http://web.cse.ohio-state.edu/software/2231/web-sw2/extras/slides/17a.Iterators.pdf
http://docs.oracle.com/javase/7/docs/api/
http://stackoverflow.com/questions/21988341/how-to-iterate-through-two-dimensional-arraylist-using-iterator
http://www.cs.cornell.edu/courses/cs211/2005fa/Lectures/L15-Iterators%20&%20Inner%20Classes/L15cs211fa05.pdf
https://leetcode.com/discuss/50292/7-9-lines-added-java-and-c-o-1-space
https://leetcode.com/discuss/55199/pure-iterator-solution-additional-data-structure-list-get
https://leetcode.com/discuss/57984/simple-and-short-java-solution-with-iterator
https://leetcode.com/discuss/50356/my-concise-java-solution
https://leetcode.com/discuss/68860/java-o-1-space-solution
https://leetcode.com/discuss/71002/java-solution-beats-60-10%25
最新文章
- spider RPC插件化体系
- php-fpm优化
- JavaSript模块规范 - AMD规范与CMD规范介绍(转)
- java中string内存的相关知识点
- win2003远程桌面端口修改
- java中DriverManager跟DataSource获取getConnection有什么不同?
- Capturing Audio &; Video in HTML5
- hdu 4258 Covered Walkway
- Angularjs 通过WebApi 下载excel
- Python、C和Java对比
- 【小丸类库系列】Excel操作类
- jquery元素查找方法集锦
- Guava API学习之Multimap
- 用正交多项式作最小二乘拟合的java实现(转)
- 关于video.js
- 软工+C(9): 助教指南,持续更新...
- [Swift]LeetCode81. 搜索旋转排序数组 II | Search in Rotated Sorted Array II
- 学习 vue 源码 -- 响应式原理
- 区间dp好题cf149d 括号匹配
- android 地图
热门文章
- 通过获取客户端Json数据字符串,反序列化为实体对象的一段代码
- [转]Linux中find常见用法示例
- 编写php拓展实例--slime项目(用户登录会话类)
- SQLserver利用系统时间生成“2015-11-30 00:00:00.000”类型的时间
- odp.net以及oracle oledb安装
- DBus接口文档
- 【iOS】屏幕旋转,屏幕自适应方向变化
- android 开发上传图片遇到返回 FileNotFoundException
- Javascript核心概述 - 深入了解javascript
- java 把URL中的中文转换成utf-8编码