45. 跳跃游戏 II
3 min
题目
解法：广度优先
思路
使用广度优先搜索（BFS）按层遍历所有可达位置，首次到达终点时的层数即为最小跳跃次数。
BFS的正确性基于其按层扩展的特性：第k层的所有位置都恰好通过k次跳跃到达。由于每次跳跃可以到达任意可达位置，BFS能确保第一次访问到终点时，所用的跳跃次数是最小的。visited数组防止重复访问，保证每个位置只被处理一次，不会遗漏最优解。
- Step 1: 初始化队列和visited数组，将起点0入队
- Step 2: 循环处理每一层，step记录当前跳跃次数
- Step 3: 对于当前层的每个位置，尝试所有可能的跳跃距离
- Step 4: 将未访问的下一个位置入队并标记为已访问
- Step 5: 若到达终点则返回当前step
- Step 6: 处理完一层后step自增
复杂度
- 时间复杂度: ，每个位置最多访问一次，每次最多尝试1000次跳跃（常数）
- 空间复杂度: ，队列和visited数组的空间
代码
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
queue<int> q;
vector<bool> visited(n,false);
q.push(0);
visited[0] = true;
int step = 0;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
int cur = q.front();
q.pop();
if(cur == n-1)
return step;
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
queue<int> q;
vector<bool> visited(n,false);
q.push(0);
visited[0] = true;
int step = 0;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
int cur = q.front();
q.pop();
if(cur == n-1)
return step;
for(int j = 1; j <= nums[cur]; j++){
int next = cur + j;
if(next < n && !visited[next]){
visited[next] = true;
q.push(next);
}
}
}
step++;
}
return -1;
}
};