LeetCode高频题55,45类似的1306. 跳跃游戏 III：从start位置跳到end位置，至少需要多少步，不行返回-1
LeetCode高频题55,45类似的1306. 跳跃游戏 III：从start位置跳到end位置，至少需要多少步，不行返回-1
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
基础知识：
【1】LeetCode高频题55. 跳跃游戏
【2】LeetCode高频题55加类似新题45：跳跃游戏 II：最少需要跳多少步才能抵达终点
【3】机器人从轨道长N上的起点M出发，走到P点，必须走K步，请问有多少种走法
本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了
本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了
本题！是互联网大厂考过的笔试原题，202204月的笔试，好像是京东还是字节考的，我忘了
文章目录
- LeetCode高频题55,45类似的1306. 跳跃游戏 III：从start位置跳到end位置，至少需要多少步，不行返回-1
-
- 题目
- 一、审题
- 笔试AC解用BFS，耗费一定的额外空间，速度也还勉强，毕竟map操作起来比较耗时
- 面试最优解前奏：DFS，用暴力递归尝试，从i位置到end位置，walk标记走过的位置，看看至少需要多少步，再转动态规划代码
- 面试最优解前奏：DFS之尝试2：上面这个方法，不行啊，因为walk标记情况太多，它是一个数组变量，不是单一变量，没法让我们轻松改出动态规划的转移方程，因此不符合我们暴力递归的尝试
- 面试最优解：DFS：正经地将上面g改为动态规划，写好转移方程，填dp表
- 本题LeetCode倒是没有问你要：走最少的步数？它问你能去0位置吗？
- 总结
文章目录
- LeetCode高频题55,45类似的1306. 跳跃游戏 III：从start位置跳到end位置，至少需要多少步，不行返回-1
- 题目
- 一、审题
- 笔试AC解用BFS，耗费一定的额外空间，速度也还勉强，毕竟map操作起来比较耗时
- 面试最优解前奏：DFS，用暴力递归尝试，从i位置到end位置，walk标记走过的位置，看看至少需要多少步，再转动态规划代码
- 面试最优解前奏：DFS之尝试2：上面这个方法，不行啊，因为walk标记情况太多，它是一个数组变量，不是单一变量，没法让我们轻松改出动态规划的转移方程，因此不符合我们暴力递归的尝试
- 面试最优解：DFS：正经地将上面g改为动态规划，写好转移方程，填dp表
- 本题LeetCode倒是没有问你要：走最少的步数？它问你能去0位置吗？
- 总结
题目
给你一个数组arr
给你一个起点start，终点end
在任意位置i，可以往左跳[i]步，也可以往右跳[i]步，请问你从start跳到end，有几种跳法
LeetCode原题！
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、审题
示例：
笔试AC解用BFS，耗费一定的额外空间，速度也还勉强，毕竟map操作起来比较耗时
本题两大解法，笔试AC解用BFS，面试最优解用DFS
本题非常重要的仨基础知识：
【1】LeetCode高频题55. 跳跃游戏
【2】LeetCode高频题55加类似新题45：跳跃游戏 II：最少需要跳多少步才能抵达终点
【3】机器人从轨道长N上的起点M出发，走到P点，必须走K步，请问有多少种走法
一定都要看看，非常类似，非常重要！！！
本题和【3】非常像，但是我们不要求走法，只要求至少多少步？？？
解题方法：
宽度优先遍历BFS，遇到重复的节点，不要再玩了，否则死循环了
比如start=3，出发，我走了0步
用一个map记住start位置，它走了0步，也就是0层
同时BFS的队列queue加入start位置！！队列里面加整个arr的位置！
start弹出来作为cur位置，它走左边left，右边right，去这俩位置
只要map中没有这俩位置，就可以将left将right加入BFS的队列，作为下一层，也就是步数+1的那层去【1层】
然后每个节点继续BFS，各自走自己的left和right，不重复就添加进入队列。
啥时候cur弹出来遇到end位置，就是此时map中记录的cur的层数就是它走过的步数
这个BFS的思想要熟悉，将左右两种走法转化为二叉树，就跟折叠纸出现两个分支一样
将来还有题目，走多个分支也行的，反正就是沿着各个分支走，最早遇到end，此时我经过的步数就是咱们最少的步数！！！
手撕代码试试
//改编，走几步呢：
public int canReachStepLeast(int[] arr, int start, int end) {
if (arr == null || arr.length == 0) return -1;
//本题是要找到0位置下标作为end
int N = arr.length;
//然后BFS找我从start去end至少需要几步？
//能遇到end就true，否则false
LinkedList<Integer> queue = new LinkedList<>();//队列BFS的
queue.add(start);
HashMap<Integer, Integer> map = new HashMap<>();//key：位置i，走了几步来的？value
map.put(start, 0);//map刚刚来到start位置，走了0步
//看看能能否遇到end
while (!queue.isEmpty()){
int cur = queue.poll();//弹出操作
if (cur == end) return map.get(cur);//有其一到达即可
int level = map.get(cur);//找到走了多少步来到的cur？
//看看cur左右子的情况，没出现在map，不越界就可以
int left = cur - arr[cur];//往左，下标
int right = cur + arr[cur];//往右，下标
if (left >= 0 && !map.containsKey(left)){
queue.add(left);
map.put(left, level + 1);//层数必然增加，就是步数增加
}
if (right < N && !map.containsKey(right)){
queue.add(right);
map.put(right, level + 1);//层数增加，就是步数增加
}
}
//中途一直没有遇到end下标，发现挂了
return -1;
}
测试：
public static void test(){
int[] arr = {0,3,0,6,3,3,4};
int start = 6;
int end = 2;
Solution solution = new Solution();
System.out.println(solution.canReach(arr, start));
System.out.println(solution.canReachStepLeast(arr, start, end));
}
public static void main(String[] args) {
test();
}
true
1
没错，start=6，一步就可以去2,6-4即可
关键就是理解，我左走去left下标，右走去right下标，能走才行
这种二分支，特别像二叉树，这种就首要想到DFS或者BFS，才能破解题目。
而且我还从当前i位置，没去过下标才行，否则就死循环了，2021秋招考过本题的
从cur发出，每走一步，level都增加1，这就是步数多了一步，用map记录，
笔试面试也都尽量先把问题搞搞清楚，不要担心用空间的事情
为啥不能去了j位置，之后就不能再往j走了，你想啊，来到j了，下次还有步骤能来j，即使j能到end，它也不是最优走法
比如
绿色i到j，你又想从j到i，算了吧，不行的
即使你从i到j，又到i，再到end，走了3步，不是最优的走法
从i往左，或者往右，反正只能走一个方向，一定有一个方向是最早到end的
比如i直接去4，那就是走了一步，
不会重复去哪里的！
面试最优解前奏：DFS，用暴力递归尝试，从i位置到end位置，walk标记走过的位置，看看至少需要多少步，再转动态规划代码
定义f(arr,end,i,walk)为：从i发出，去end位置，需要多少步？
walk必须用来标记走过的位置，否则就死循环了，去年考的时候，我就犯了这个错误！
咱们看看f怎么写？
实际上就两个分支：
i位置，可以左走，可以右走
（0）I<0或者i>=N，越界了，或者walk[i]=true，走过这个点i，返回-1，肯定不是有效的步骤
（1）base case：就是i==end，返回0步，有效的
默认step=0步；
尝试往左走left=i-arr[i],right=i+[i]
（2）去递归走左边，返回从左边可以走，最少的步数
（3）去递归走右边，返回从右边可以走，最少的步数
int left = f(arr, end, i - arr[i], walk);
int right = f(arr, end, i + arr[i], walk);
标记我i走过了
（4）left<0了，不好意思，失效了，返回-1步
（5）right<0了，不好意思，失效了，返回-1步
看看左右哪个小？取小的步数返回【注意这里是看看往左，或者往右，有效咱们返回步数，否则还是-1】
//定义f(arr,end,i,walk)为：从i发出，去end位置，需要多少步？
//walk必须用来标记走过的位置，否则就死循环了，去年考的时候，我就犯了这个错误！
public static int f(int[] arr, int end, int i, boolean[] walk){
if (i < 0 || i >= arr.length) return -1;//越界了
//i位置，可以左走，可以右走
if (walk[i]) return -1;
//（0）walk[i]=true，走过这个点i，返回-1，肯定不是有效的步骤
//（1）base case：就是i==end，返回0步，有效的
//默认step=0步；
if (i == end) return 0;
//尝试往左走left=i-arr[i],right=i+[i]
//（2）去递归走左边，返回从左边可以走，最少的步数
//（3）去递归走右边，返回从右边可以走，最少的步数
walk[i] = true;//我i就算走过了
int left = f(arr, end, i - arr[i], walk);
int right = f(arr, end, i + arr[i], walk);
//（4）left<0了，不好意思，失效了，返回-1步
//（5）right<0了，不好意思，失效了，返回-1步
int step = 0;
//看看左右哪个小？取小的步数返回
if (left != -1 && right != -1) step = Math.min(left, right);//对比要小的那个步数
else if (left != -1) step = left;//如果左边OK
else if (right != -1) step = right;//如果左边OK
return left == -1 && right == -1 ? -1 :step + 1;//算我刚刚i走出去的步数
}
//改编，走几步呢：
public int canReachStepLeastDP1(int[] arr, int start, int end) {
if (arr == null || arr.length == 0) return -1;
//本题是要找到0位置下标作为end
int N = arr.length;
boolean[] walk = new boolean[N];//标记各个
return f(arr, end, start, walk);
}
注意 DFS往往涉及恢复现场：
walk[i] = false;//最后要清楚现场，考虑走法各种各样，这是DFS
这个的意思是啥呢？
左边可以去7，右边也能去7，
但是左边不是最优解，刚刚标记了7位true
后面回来尝试别的方案时，要让7的walk变false，才能尝试别的方法！！！
测试：
public static void test(){
int[] arr = {0,3,0,6,3,3,4};
int start = 6;
int end = 2;
Solution solution = new Solution();
System.out.println(solution.canReach(arr, start));
System.out.println(solution.canReachStepLeast(arr, start, end));
System.out.println(solution.canReachStepLeastDP1(arr, start, end));
}
public static void main(String[] args) {
test();
}
true
1
1
稳的
面试最优解前奏：DFS之尝试2：上面这个方法，不行啊，因为walk标记情况太多，它是一个数组变量，不是单一变量，没法让我们轻松改出动态规划的转移方程，因此不符合我们暴力递归的尝试
我们要想办法让变量尽量变少，而且变量要尽量简单，最好是还是int类型，Boolean类型，而不能是数组类型
如果是数组类型，你完全无法枚举它的状况！因此修改动态规划没法弄！
之前讲过那个背包问题，我们考虑剩下多少空间rest，类似这种思想
【4】背包问题：货物有重量或体积，有价值，书包最多装bag这么多，请问书包能最大装多少价值的货物
我们重新设计一个尝试：
当前来到i，已经走过了k步：最后至少能走多少步，到达end
这个k是有限制的，你从s=4，想去end=2
其实k最多最多走maxStep=5步
为啥呢？
s出发，最多最多跳除了end之外的几个点，最后跳到end，一共N-1步最多，这是铁的限制
有答案step一定小于等于maxStep
没答案一定超过了maxStep
业务限制了，这就是业务限制类的模型，这是DP的四种尝试模型4
完全可以直接在上面的暴力递归上修改代码：
问题不大：
//定义f(arr,end,i,walk)为：从i发出，去end位置，
//已经走过了k步：最后至少能走多少步，到达end
public static int g(int[] arr, int end, int i, int k){
if (i < 0 || i >= arr.length) return -1;//越界了
//i位置，可以左走，可以右走
if(k > arr.length - 1) return -1;//最多能走N - 步，到达目的地，中途不会重复
//（0）walk[i]=true，走过这个点i，返回-1，肯定不是有效的步骤
//（1）base case：就是i==end，返回0步，有效的
//默认step=0步；
if (i == end) return k;//到了k步就是结果
//尝试往左走left=i-arr[i],right=i+[i]
//（2）去递归走左边，返回从左边可以走，最少的步数
//（3）去递归走右边，返回从右边可以走，最少的步数
int left = g(arr, end, i - arr[i], k + 1);//走一步，加一
int right = g(arr, end, i + arr[i], k + 1);//走一步，加一
//（4）left<0了，不好意思，失效了，返回-1步
//（5）right<0了，不好意思，失效了，返回-1步
int step = 0;
//看看左右哪个小？取小的步数返回
if (left != -1 && right != -1) step = Math.min(left, right);//对比要小的那个步数
else if (left != -1) step = left;//如果左边OK
else if (right != -1) step = right;//如果左边OK
//不用清除k了
return left == -1 && right == -1 ? -1 :step;//算我刚刚i走出去的步数
}
//改编，走几步呢：业务限制类模型
public int canReachStepLeastDP2(int[] arr, int start, int end) {
if (arr == null || arr.length == 0) return -1;
//本题是要找到0位置下标作为end
int N = arr.length;
return g(arr, end, start, 0);//最开始k=0步
}
仍然要注意，中途不要k–，不需要恢复现场，你尽管死循环，重复走吧，k找过了N-1，就失败了！！！
测试：
public static void test(){
int[] arr = {0,3,0,6,3,3,4};
int start = 6;
int end = 2;
Solution solution = new Solution();
System.out.println(solution.canReach(arr, start));
System.out.println(solution.canReachStepLeast(arr, start, end));
System.out.println(solution.canReachStepLeastDP1(arr, start, end));
System.out.println(solution.canReachStepLeastDP2(arr, start, end));
}
public static void main(String[] args) {
test();
}
为啥不会有死循环，因为k死循环就会++++++
最后挂了
上图中，你死循环，左右，左右，走走，步数多了，你就是不行，提起那结束了，所以也不需要恢复现场，你死循环也OK
面试最优解：DFS：正经地将上面g改为动态规划，写好转移方程，填dp表
我们直接造一个dp表，二维的，长宽都是N，i做行，k做列，所有的可能组合中，i=start，k=0时，就是咱们的start出发，刚刚走了0步，还需要至少多少步到达end呢？
这就是暴力递归的主函数调用的含义，因此我们需要把dp表按照暴力递归g填好，这样直接拿dp[start][0]做我们的结果。
因为i取值就0–N-1，N长度，算一个变量
还有就是k取值0–N-1，最大走N-1步，N长度，算一个变量
业务限制就整一个表，两个分支走法类似
dp表
dp[i][k]代表啥呢？当前来到i，已经走过了k步：最后至少能走多少步，到达end
每次i，k格子依赖i-arr[i],i+arr[i]，k+1，俩格子
我们最后需要dp[start][0]，start在中间某一行
所以宏观填表，应该从最后一列开始填，往左推，这样才能搞
先填好第一行，最后一行，
根据暴力递归填写
我们都没要
k超过N-1，我们也没要
把end这行填写好
剩下的所有位置，都根据暴力递归内部这些步骤来改
注意，我们说了，ik格子依赖i-[i]，k+1,和i+[i],k+1格子，所以呢
我们得把最后一列k=N-1填好，否则，没法依赖
当k=N-1，你得保证i==end，才能是k步，即dp[i][N-1]=k,否则dp[i][N-1]=-1；
另外，我们没有-1和N位置，所以，提前确定left和right=-1，如果i-[i]>=0,可以取走left，i+[i]<N，才能往右走
当然，我们填过i=end行，就不要填了
手撕代码如下：
//改编，走几步呢：业务限制类模型，精细化动态规划代码
public int canReachStepLeastDP3(int[] arr, int start, int end) {
if (arr == null || arr.length == 0) return -1;
//本题是要找到0位置下标作为end
int N = arr.length;
int[][] dp = new int[N][N];
for (int k = 0; k < N; k++) {
//（1）base case：就是i==end，返回k步，有效的
dp[end][k] = k;//i=k，
}
//貌似最后一列得填好，否则炸了
for (int i = 0; i < N; i++) {
dp[i][N - 1] = i == end ? N - 1 : -1;//恰好走了N-1步，如果此时i恰好到end就是k，否则-1，无效
}
for (int k = N - 2; k >= 0; k--) {
//咱们从最后一列开始填
for (int i = 0; i < N; i++) {
if (i != end){//end这行填过了
//尝试往左走left=i-arr[i],right=i+[i]
//（2）去递归走左边，返回从左边可以走，最少的步数
//（3）去递归走右边，返回从右边可以走，最少的步数
//必须提前判断能走，才走
int left = -1;
int right = -1;
if (i - arr[i] >= 0) left = dp[i - arr[i]][k + 1];
if (i + arr[i] < N) right = dp[i + arr[i]][k + 1];
//（4）left<0了，不好意思，失效了，返回-1步
//（5）right<0了，不好意思，失效了，返回-1步
int step = 0;
//看看左右哪个小？取小的步数返回
if (left != -1 && right != -1) Math.min(left, right);//对比要小的那个步数
else if (left != -1) step = left;//如果左边OK
else if (right != -1) step = right;//如果左边OK
dp[i][k] = left == -1 && right == -1 ? -1 :step;//算我刚刚i走出去的步数
}
}
}
return dp[start][0];//最开始k=0步
}
测试：
public static void test(){
int[] arr = {0,3,0,6,3,3,4};
int start = 6;
int end = 2;
Solution solution = new Solution();
System.out.println(solution.canReach(arr, start));
System.out.println(solution.canReachStepLeast(arr, start, end));
System.out.println(solution.canReachStepLeastDP1(arr, start, end));
System.out.println(solution.canReachStepLeastDP2(arr, start, end));
System.out.println(solution.canReachStepLeastDP3(arr, start, end));
}
public static void main(String[] args) {
test();
}
一绝屌爆了！！
这就是本题最牛逼的动态规划解法！！
绝对的强大
BFS能做，但是DFS更强大，能该处动态规划了，而且尝试非常牛逼！！
i出发，走过了k步，最少多少步能到end，这个尝试，一般还想不到，得尝试那个walk走过哪里标记，你才知道，那方法可能变量不是int，或者Boolean，这种简单的类型，
所以我们要用新的尝试，观察k最多走n-1步，必须到，因为中途不重复。
本题LeetCode倒是没有问你要：走最少的步数？它问你能去0位置吗？
我们需要提前找一个哪些位置都是0，然后用ends记起来
从start去ends列表那些位置end，只要中途cur等于end，有其一就算是true，简单改改上面的代码即可
仍然是BFS思想，尽快走，左右，反正早点到，就OK
手撕代码：
public boolean canReach(int[] arr, int start) {
if (arr == null || arr.length == 0) return false;
//本题是要找到0位置下标作为end
int N = arr.length;
List<Integer> ends = new ArrayList<>();//可能有一堆0，到一个就算
for (int i = 0; i < N; i++) {
if (arr[i] == 0) {
ends.add(i);
}
}
if (ends.size() == 0) return false;
//然后BFS找我从start去end至少需要几步？
//能遇到end就true，否则false
LinkedList<Integer> queue = new LinkedList<>();//队列BFS的
queue.add(start);
HashMap<Integer, Integer> map = new HashMap<>();//key：位置i，走了几步来的？value
map.put(start, 0);//map刚刚来到start位置，走了0步
//看看能能否遇到end
while (!queue.isEmpty()){
int cur = queue.poll();//弹出操作
for(Integer end : ends) if (cur == end) return true;//有其一到达即可
int level = map.get(cur);//找到走了多少步来到的cur？
//看看cur左右子的情况，没出现在map，不越界就可以
int left = cur - arr[cur];//往左，下标
int right = cur + arr[cur];//往右，下标
if (left >= 0 && !map.containsKey(left)){
queue.add(left);
map.put(left, level + 1);//层数必然增加，就是步数增加
}
if (right < N && !map.containsKey(right)){
queue.add(right);
map.put(right, level + 1);//层数增加，就是步数增加
}
}
//中途一直没有遇到end下标，发现挂了
return false;
}
LeetCode测试：
当然，我们上面说的DFS的暴力尝试到动态规划，也是完全可以改到这里的，非常OK
我今天就不改了，写太多了，头炸了，做饭去！
总结
提示：重要经验：
0）我发现，其实，不管是矩阵中往右，还是斜着走，去打击怪兽，还是这种数组，往左右走，走步数，到达指定地点，都是考的分支限界的业务限制类算法，无法不走这，就走那，这种业务限制类模型，就是要把变量考虑清楚，动态规划的尝试，一定是考虑变量简单，int，Boolean类型，还不要超过3个变量，越少越好，越简单越好。
1）关于跳跃游戏，有一堆类似的题目，用DFS,BFS，或者通过控制变量来决定i与cur的关系，才能知道能否到N-1位置，也才能知道需不需要增加步数
2）本题，BFS很巧妙，i可以走左边，也可以走右边，只要是二分支，我们就可以考虑看看是左边好，还是右边好，那就是BFS，考虑到重复，反正你要么往左跳，往右跳，不能走重复的地方，这很重要
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
相关文章
- [LeetCode] Palindrome Number & Valid Palindrome - 回文系列问题
- leetcode 之Partition List（16）
- Java实现 LeetCode 794 有效的井字游戏 （暴力分析）
- Java实现 LeetCode 728 自除数（暴力）
- Java实现 LeetCode 679 24 点游戏（递归）
- Java实现 LeetCode 529 扫雷游戏(DFS)
- Java实现 LeetCode 413 等差数列划分
- Java实现 LeetCode 390 消除游戏
- Java实现 LeetCode 390 消除游戏
- Java实现 LeetCode 377 组合总和 Ⅳ
- Java实现 LeetCode 299 猜数字游戏
- Java实现 LeetCode 299 猜数字游戏
- Java实现 LeetCode 292 Nim游戏
- Java实现 LeetCode 149 直线上最多的点数
- Java实现 LeetCode 118 杨辉三角
- Java实现 LeetCode 55 跳跃游戏
- Java实现 LeetCode 55 跳跃游戏
- Java实现 LeetCode 25 K个一组翻转链表
- 【LeetCode算法-53】Maximum Subarray
- LeetCode（45）： 跳跃游戏 II
- 【栈&队列】LeetCode 394. 字符串编码【中等】
- LeetCode（87）：扰乱字符串
- LeetCode（45）： 跳跃游戏 II
- LeetCode（35）：搜索插入位置
- [LeetCode] 45. Jump game II ☆☆☆☆☆(跳跃游戏 2)
- leetcode 389. Find the Difference
- leetcode 762. Prime Number of Set Bits in Binary Representation
- 【Leetcode刷题Python】234.回文链表
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】跳跃游戏II