Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/251.html
Design an iterator to flatten a 2D vector. It should support the next
and hasNext
operations.
Implement the Vector2D
class:
Vector2D(int[][] vec)
initializes the object with the 2D vectorvec
.next()
returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls tonext
are valid.hasNext()
returnstrue
if there are still some elements in the vector, andfalse
otherwise.
Example 1:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False
Constraints:
0 <= vec.length <= 200
0 <= vec[i].length <= 500
-500 <= vec[i][j] <= 500
- At most
105
calls will be made tonext
andhasNext
.
Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.
Algorithm
Maintain two variables x and y, and initialize x and y to 0.
For the hasNext()
function, check whether the current x is less than the total number of rows, and whether y is the same as the number of columns in the current row,
- If the same, it means that you want to go to the next line, then x increments by 1, y is initialized to 0
- If x is still less than the total number of rows at this time, indicating that the next value can be taken out, then in the next function, you can directly take out the row x, list the number as y, and increment y by 1
Note: special case for empty list
[
[1,2],
[3],
[4,5,6],
[],
[],
[]
]
Code
-
import java.util.List; public class Flatten_2D_Vector { public class Vector2D { private int x; // which list private int y; // which index of current list private List<List<Integer>> list; /* constructor */ public Vector2D(List<List<Integer>> vec2d) { this.x = 0; this.y = 0; this.list = vec2d; } /* API: next */ public int next() { int result = list.get(x).get(y); if (y + 1 >= list.get(x).size()) { y = 0; x++; } else { y++; } return result; } /* API: hasNext */ public boolean hasNext() { if (list == null) { return false; } /* @note: special case for empty list [ [1,2], [3], [4,5,6], [], [], [] ] */ while (x < list.size() && list.get(x).size() == 0) { x++; y = 0; } if (x >= list.size()) { return false; } if (y >= list.get(x).size()) { return false; } return true; } } } ############ class Vector2D { private int i; private int j; private int[][] vec; public Vector2D(int[][] vec) { this.vec = vec; } public int next() { forward(); return vec[i][j++]; } public boolean hasNext() { forward(); return i < vec.length; } private void forward() { while (i < vec.length && j >= vec[i].length) { ++i; j = 0; } } } /** * Your Vector2D object will be instantiated and called as such: * Vector2D obj = new Vector2D(vec); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */
-
// OJ: https://leetcode.com/problems/flatten-2d-vector/ // Time: // Vector2D: O(N) // next: O(1) amortized // hasNext: O(1) // Space: O(1) class Vector2D { vector<vector<int>> v; int i = 0, j = 0; void move() { while (i < v.size() && j == v[i].size()) { ++i; j = 0; } } public: Vector2D(vector<vector<int>>& v) : v(v) { move(); } int next() { int ans = v[i][j++]; move(); return ans; } bool hasNext() { return i < v.size(); } };
-
""" @note: special case for empty list [ [1,2], [3], [4,5,6], [], [], [] ] """ class Vector2D: def __init__(self, vec: List[List[int]]): self.flatten = [] for item in vec: for e in item: self.flatten.append(e) self.cur = -1 def next(self) -> int: self.cur += 1 return self.flatten[self.cur] def hasNext(self) -> bool: return self.cur < len(self.flatten) - 1 class Vector2D: def __init__(self, v: List[List[int]]): self.i = 0 # which list self.j = 0 # which index of current list self.vector = v def next(self) -> int: self.hasNext() value = self.vector[self.i][self.j] self.j += 1 # in hasNext() guaranteed not end of row return value def hasNext(self) -> bool: while self.i < len(self.vector): if self.j < len(self.vector[self.i]): return True self.i += 1 self.j = 0 return False # Your Vector2D object will be instantiated and called as such: # obj = Vector2D(vec) # param_1 = obj.next() # param_2 = obj.hasNext() ############ class Vector2D(object): def __init__(self, vec2d): """ Initialize your data structure here. :type vec2d: List[List[int]] """ self.x = self.y = 0 self.m = vec2d def next(self): """ :rtype: int """ self.y += 1 return self.m[self.x][self.y - 1] def hasNext(self): """ :rtype: bool """ m = self.m while self.x < len(m) and self.y >= len(m[self.x]): self.x += 1 self.y = 0 return self.x < len(m) # Your Vector2D object will be instantiated and called as such: # i, v = Vector2D(vec2d), [] # while i.hasNext(): v.append(i.next())
-
type Vector2D struct { i, j int vec [][]int } func Constructor(vec [][]int) Vector2D { return Vector2D{vec: vec} } func (this *Vector2D) Next() int { this.forward() ans := this.vec[this.i][this.j] this.j++ return ans } func (this *Vector2D) HasNext() bool { this.forward() return this.i < len(this.vec) } func (this *Vector2D) forward() { for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) { this.i++ this.j = 0 } } /** * Your Vector2D object will be instantiated and called as such: * obj := Constructor(vec); * param_1 := obj.Next(); * param_2 := obj.HasNext(); */
-
class Vector2D { i: number; j: number; vec: number[][]; constructor(vec: number[][]) { this.i = 0; this.j = 0; this.vec = vec; } next(): number { this.forward(); return this.vec[this.i][this.j++]; } hasNext(): boolean { this.forward(); return this.i < this.vec.length; } forward(): void { while (this.i < this.vec.length && this.j >= this.vec[this.i].length) { ++this.i; this.j = 0; } } } /** * Your Vector2D object will be instantiated and called as such: * var obj = new Vector2D(vec) * var param_1 = obj.next() * var param_2 = obj.hasNext() */