251. 展开二维向量 🔒
题目描述
请设计并实现一个能够展开二维向量的迭代器。该迭代器需要支持 next
和 hasNext
两种操作。
示例:
Vector2D iterator = new Vector2D([[1,2],[3],[4]]); iterator.next(); // 返回 1 iterator.next(); // 返回 2 iterator.next(); // 返回 3 iterator.hasNext(); // 返回 true iterator.hasNext(); // 返回 true iterator.next(); // 返回 4 iterator.hasNext(); // 返回 false
注意:
- 请记得 重置 在 Vector2D 中声明的类变量(静态变量),因为类变量会 在多个测试用例中保持不变,影响判题准确。请 查阅 这里。
- 你可以假定
next()
的调用总是合法的,即当next()
被调用时,二维向量总是存在至少一个后续元素。
进阶:尝试在代码中仅使用 C++ 提供的迭代器 或 Java 提供的迭代器。
解法
方法一:双指针
我们定义两个指针 $i$ 和 $j$,分别指向当前二维向量的行和列,初始时 $i = 0$,$j = 0$。
接下来,我们设计一个函数 $forward()$,用于将 $i$ 和 $j$ 向后移动,直到指向一个非空的元素。
每次调用 next
方法时,我们先调用 $forward()$,然后返回当前指向的元素,最后将 $j$ 向后移动一位。
每次调用 hasNext
方法时,我们先调用 $forward()$,然后判断 $i$ 是否小于二维向量的行数,如果是,则返回 true
,否则返回 false
。
时间复杂度 $O(1)$,空间复杂度 $O(1)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|