边工作边刷题:70天一遍leetcode: day 84

时间:2022-04-19 07:19:20

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())