Skip to content

Latest commit

 

History

History
281 lines (216 loc) · 6.26 KB

README.md

File metadata and controls

281 lines (216 loc) · 6.26 KB
Raw
comments difficulty edit_url tags
true
中等
设计
数组
双指针
迭代器

251. 展开二维向量 🔒

English Version

题目描述

请设计并实现一个能够展开二维向量的迭代器。该迭代器需要支持 next 和 hasNext 两种操作。

实现 Vector2D 类：

  • Vector2D(int[][] vec) 使用二维向量 vec 初始化对象
  • next() 从二维向量返回下一个元素并将指针移动到下一个位置。你可以假设对 next 的所有调用都是合法的。
  • hasNext() 当向量中还有元素返回 true，否则返回 false。

 

示例 1：

输入：
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
输出：
[null, 1, 2, 3, true, true, 4, false]

解释：
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

 

提示：

  • 0 <= vec.length <= 200
  • 0 <= vec[i].length <= 500
  • -500 <= vec[i][j] <= 500
  • 最多调用 next 和 hasNext 105 次。

 

进阶：尝试在代码中仅使用 C++ 提供的迭代器 或 Java 提供的迭代器。

解法

方法一：双指针

我们定义两个指针 $i$ 和 $j$，分别指向当前二维向量的行和列，初始时 $i = 0$，$j = 0$。

接下来，我们设计一个函数 $forward()$，用于将 $i$ 和 $j$ 向后移动，直到指向一个非空的元素。

每次调用 next 方法时，我们先调用 $forward()$，然后返回当前指向的元素，最后将 $j$ 向后移动一位。

每次调用 hasNext 方法时，我们先调用 $forward()$，然后判断 $i$ 是否小于二维向量的行数，如果是，则返回 true，否则返回 false。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

Python3

class Vector2D:
    def __init__(self, vec: List[List[int]]):
        self.i = 0
        self.j = 0
        self.vec = vec

    def next(self) -> int:
        self.forward()
        ans = self.vec[self.i][self.j]
        self.j += 1
        return ans

    def hasNext(self) -> bool:
        self.forward()
        return self.i < len(self.vec)

    def forward(self):
        while self.i < len(self.vec) and self.j >= len(self.vec[self.i]):
            self.i += 1
            self.j = 0


# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Java

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();
 */

C++

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec) {
        this->vec = move(vec);
    }

    int next() {
        forward();
        return vec[i][j++];
    }

    bool hasNext() {
        forward();
        return i < vec.size();
    }

private:
    int i = 0;
    int j = 0;
    vector<vector<int>> vec;

    void forward() {
        while (i < vec.size() && j >= vec[i].size()) {
            ++i;
            j = 0;
        }
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(vec);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Go

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();
 */

TypeScript

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