题目描述
为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。
示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。
话有点多，大意就是：
- 给出jump数组，jump[i]表示小球可以从 i 位置跳到 i+jump[i]
- 当小球在位置 i 时，可以跳到左侧的任意位置
- 问题：从下标0位置开始，最少几次可以跳出数组？
解题思路
其实，看到这个问题的时候最好是能联想到"迷宫问题"，因为“迷宫问题”和这个问题里面都很明显地涉及到路径
再则，因为是求最少次数，相应的应该想到地是BFS而不是DFS
接下来就完善一下思路：
- 初始化队列queue、记录到达位置i的最少次数的数组 dp[n]
- 只要队列不空，循环取出队首元素 x，并让其向左、向右跳跃
- 小球从x位置向右跳跃：若小球第一次到达x+jump[x]位置，则需要更新dp并把x+jump[x]加入queue（PS：若x+jump[x] >= n，则优先return dp[x]+1）
- 小球从x位置向左跳跃：检查x左侧所有位置 k，若小球之前未达到，则需要更新dp并把k加入queue
但是，这边其实还有一个问题！
---- 在小球向左跳跃时，如果简单遍历x左侧所有位置k会导致超时（时间复杂度是O(n*n)）
解决的方法说起来也很简单，但要想到这个方法其实还是有点难的
本弱鸡也是参考AK大神的代码。。。代码如下，可以先体会一下
// C++
class Solution {
int d[1000005],q[1000005],he,ta;
public:
int minJump(vector<int>& jump) {
int n=jump.size(),i,l=0;
fill(d,d+n,-1);
d[0]=0;
he=ta=0;
q[ta++]=0;
while(he!=ta)
{
i=q[he++];
if(i+jump[i]>=n)break;
if(!~d[i+jump[i]])d[q[ta++]=i+jump[i]]=d[i]+1;
for(;l<i;l++)if(!~d[l])d[q[ta++]=l]=d[i]+1; // 小球向左跳的处理在这
}
return d[i]+1;
}
};
可以看到，AK大神对小球向左跳跃的处理时，遍历是从位置 l 到 位置i，且变量 l 一直沿用。
之所以能这样处理是建立在BFS中第一次达到该位置时跳跃的次数一定是最少的，因此，如果在之前对位置 l 左侧的所有位置检查一次后，下次再检查的时候只需要从位置 l 后面继续检查就行。（当然还有其他的一些剪枝的方法，不过个人觉得这个算是最简单易懂的）
最终自己的代码：
# pytho3
class Solution:
def minJump(self, jump: List[int]) -> int:
n = len(jump)
INF = 99999999999
dp = [INF for i in range(n)]
l = 0
dp[0] = 0
index = 0
queue = [0]
while index < len(queue):
x = queue[index] # 取队首元素
index += 1 # 指针向后移动
if x+jump[x] >= n: # 已经跳出数组
return dp[x] + 1
elif dp[x+jump[x]] == INF: # 小球向右跳，第一次到达该位置
queue.append(x+jump[x]) # 加入队列
dp[x+jump[x]] = dp[x] + 1 # 更新dp数组
# 小球向左跳
while l < x: # 点睛之笔 -- 亮点在于 变量 l 可以一直延用
if dp[l] == INF: # 第一次到达该位置
dp[l] = dp[x] + 1 # 更新dp
queue.append(l) # 加入队列
l += 1 # 向后移动一位
题库链接：LCP 09. 最小跳跃次数
网友评论