Flatten 2D Vector
要点：
- 这题是2d的iterator，一般对于1d的情况，hasNext()是不需要做移动的。而2d不同，core iterator是j向的，而i向要在hasNext()中移动以保证call next()的时候j是available的。
- hasNext()如何移动？首先的思路是not j.hasNext()是触发i移动的条件，同时j本身也可能是None（比如Null 2d list）。简单的说就是不算移动i直到j没超界，如果i都超界了，那么return False.
这个条件下还要判断i.hasNext()，然后移动i，赋值j iterator。当这步之后还是not j.hasNext()。那么说明遍历完毕。 - 同样这题无论是用iterator还是index都是同样思路，index的时候hasNext()要先判断i，然后才有机会判断j。而iterator version，一个0元素list仍然有iterator，但是i.hasNext()为False。用j iterator为None来表示i根本没初始化
# 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 and y.
# 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 and y 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.
# Hide Company Tags Google Airbnb Twitter Zenefits
# Hide Tags Design
# Hide Similar Problems (M) Binary Search Tree Iterator (M) Zigzag Iterator (M) Peeking Iterator (M) Flatten Nested List Iterator
class Vector2D(object):
def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
self.vec = vec2d
self.i = 0
self.j = 0
def next(self):
"""
:rtype: int
"""
ret = self.vec[self.i][self.j]
self.j+=1
return ret
def hasNext(self):
"""
:rtype: bool
"""
while self.i<len(self.vec):
if self.j<len(self.vec[self.i]):
return True
self.i+=1
self.j=0
return False
# Your Vector2D object will be instantiated and called as such:
# i, v = Vector2D(vec2d), []
# while i.hasNext(): v.append(i.next())