251. Flatten 2D Vector - cocoder39/coco39_LC GitHub Wiki
iterator based solution
- python doesn't support has_next(). we have to call next() and check StopIteration exception to mimic has_next(). Since next() has side effect, we will need to preserve the result from next()
- here the assumption is that hasNext will called prior to next(). Generally speaking, we cannot enforce that. Below code doesn't honor this assumption
- hasNext should not change state
- next changes state and could throw StopIteration
class Vector2D:
def __init__(self, vec: List[List[int]]):
self.list_iterator = iter(vec)
self.sublist_iterator = iter([])
# there is no has_next in python.
# We have to call next then check if StopIteration is thrown
# given next has side effect, we will preserve the value in nextElement
self.next_element = None
self.advance_iterator()
def advance_iterator(self):
while True:
try:
element_in_list = next(self.list_iterator)
self.sublist_iterator = iter(element_in_list)
if self.sublist_has_next():
break
except StopIteration:
self.sublist_iterator = iter([])
break
def sublist_has_next(self):
try:
self.next_element = next(self.sublist_iterator)
return True
except StopIteration:
self.next_element = None
return False
# change state
# could throw StopIteration
def next(self) -> int:
if not self.hasNext():
raise StopIteration
res = self.next_element
if not self.sublist_has_next():
self.advance_iterator()
return res
# should not change state
def hasNext(self) -> bool:
return self.next_element is not None
iterator of iterator
class Vector:
def __init__(self, vec: List[int]):
self.iterator = iter(vec)
# there is no has_next in python.
# We have to call next then check if StopIteration is thrown
# given next has side effect, we will preserve the value in nextElement
self.next_element = None
self.advance_to_next()
def advance_to_next(self):
try:
self.next_element = next(self.iterator)
except StopIteration:
self.next_element = None
def next(self) -> int:
if not self.hasNext():
raise StopIteration
res = self.next_element
self.advance_to_next()
return res
def hasNext(self) -> bool:
return self.next_element is not None
class Vector2D:
def __init__(self, vec: List[List[int]]):
self.list_iterator = iter(vec)
self.sublist_iterator = Vector([])
# there is no has_next in python.
# We have to call next then check if StopIteration is thrown
# given next has side effect, we will preserve the value in nextElement
self.next_element = None
self.advance_to_next()
def advance_to_next(self):
if self.sublist_iterator.hasNext():
self.next_element = self.sublist_iterator.next()
else:
while True:
try:
sublist = next(self.list_iterator)
self.sublist_iterator = Vector(sublist)
if self.sublist_iterator.hasNext():
self.next_element = self.sublist_iterator.next()
return
except StopIteration:
self.sublist_iterator = Vector([])
self.next_element = None
return
# change state
# could throw StopIteration
def next(self) -> int:
if not self.hasNext():
raise StopIteration
res = self.next_element
self.advance_to_next()
return res
# should not change state
def hasNext(self) -> bool:
return self.next_element is not None
Beware of empty rows
class Vector2D:
def __init__(self, vec: List[List[int]]):
self.vec = vec
self.outer = 0
self.inner = 0
def advance(self):
while self.outer < len(self.vec) and self.inner == len(self.vec[self.outer]):
self.outer += 1
self.inner = 0
def next(self) -> int:
if self.hasNext():
val = self.vec[self.outer][self.inner]
self.inner += 1
return val
else:
raise StopIteration
def hasNext(self) -> bool:
self.advance()
return self.outer < len(self.vec)
============================================================
space is O(n)
class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
next_vec = 0;
for (int i = 0; i < vec2d.size(); i++) {
its.push_back(vec2d[i].begin());
ends.push_back(vec2d[i].end());
}
}
int next() {
auto &it = its[next_vec];
int res = *it++;
return res;
}
bool hasNext() {
for (int i = next_vec; i < its.size(); i++) {
if (its[i] != ends[i]) {
next_vec = i;
return true;
}
}
return false;
}
private:
vector<vector<int>::iterator> its;
vector<vector<int>::iterator> ends;
int next_vec;
};
space is O(1)
class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
next_idx = 0;
it = vec2d.begin();
end = vec2d.end();
}
int next() {
auto it1 = it->begin() + next_idx++;
return *it1;
}
bool hasNext() {
while (it != end && it->begin() + next_idx == it->end()) {
next_idx = 0;
it++;
}
return it != end;
}
private:
int next_idx;
vector<vector<int>>::iterator it, end;
};