LeetCode 55 Jump Game & 45 Jump Game II

55 Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:

A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

一开始考虑用动态规划,当前位置i是否可以到达可以转化为,[0,...,i-1]区间的位置可以到达且该位置step大于与i的index差值,用一个boolean数组dp[]来存储之前的状态,然而写完就LTE了。。。不开心。。。因为每次判断都需要用到之前所有状态,太耗时了。

改进:用maxCover记录最大可到达距离,step记录仍然可走的步数,遍历数组更新这两个值,若step=0且没有走到数组尾部,则返回false;若遍历完成则返回true,这样只用扫描一遍且每一步都不需要再扫描之前每一步的状态。

原因是每次只用记录当前可以走到最大距离的那个状态!!!

代码:

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 0) return false;
        
        int maxCover = 0, step = 1;
        for (int i = 0; i < nums.length; i++) {
            step--;
            if (i + nums[i] > maxCover) {
                maxCover = i + nums[i];
                step = nums[i];
            }
            if (step == 0 && i < nums.length-1) return false;
        }
        return true;
    }
}

45 Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:

Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2.
(Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:You can assume that you can always reach the last index.

关键的问题1:到底什么时候总步数+1呢?
回答:假设到遍历到数组index=i的位置,在此之前jump到的位置为k;在位置k最远可以到达的范围是[k,reach],如果reach<i,说明[k-reach]之间必须再jump一次,这样才能保证i在可以reach的范围内!

关键问题2:那究竟在[k-reach]的哪个位置再次jump呢?
回答:根据贪心算法,应该挑可以reach范围最远的那个点,如果需要求jump game的最短次数的jump路径,就需要记录这个点了。

本题仅解决问题1即可。

public class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        int reach = nums[0];
        int lastreach = 0;
        int step = 0;
        
        for (int i = 1; i <= reach && i < nums.length; i++) {
            if (i > lastreach) {
                step++;
                lastreach = reach;
            }
            reach = Math.max(reach, i+nums[i]);
        }
        if (reach < nums.length-1) return 0;
        return step;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,813评论 0 23
  • 合上一页书卷,些许情愫似秋叶般纷飞、旋转、散落天空。文脉?低头看见青色的血管,不断涌动的,是传承千年所恒久不变...
    _浅安_阅读 130评论 0 3
  • 张明乾转过身冲小李说道 :“一会你听我的命令行事,一旦看到我的手势,你就立刻以最快的速度把特别羁押室的防盗门打开,...
    长白居士阅读 165评论 0 0
  • 今日任务清单:1.将进水的mac送检测,并取回2.复习C++函数、初始类3.完成今日作业 1.今日同桌不小心摔倒、...
    爱学习的栗子君阅读 100评论 0 0