跳跃游戏

Meteor 2023-10-08 17:39:53
Categories： Tags：

55. 跳跃游戏

解题思路

判断是否能跳到最后一个节点，只要保证到达倒数第二个节点时，依然有跳跃的能力。
首先要排除一种特殊情况，即当数组中第一个元素为0且数组长度大于1时，此时一定返回false。其次，令cur等于nums[0]，表示当前能跳跃的最大步数，然后从索引为1的位置开始循环，先将cur减一，表示进入当前位置消耗一个步数，然后将cur与nums[i]作比较，选出新的最大步数，最后判断最大步数是否小于等于0，若为true，则表示无法走到最后一个元素，直接返回false。循环结束表示能达到最后一个位置，返回true。

代码

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

45. 跳跃游戏 II

解题思路

由于题目保证了一定能达到最后一个元素，因此只需要考虑达到最后结尾的次数即可。无论从哪个元素开始都可以分为两种情况，第一种，能直接达到结尾，第二种，无法达到，需要找下一个元素进行接力，那么接力的元素一定是从该元素能达到的范围内能走的最远的元素。
首先排除数组长度为1的特殊情况，此时不需要跳跃。令res表示跳跃次数，i表示开始跳跃的位置，cur表示目前能跳跃的最大步数，然后当i小于nums.length-1时进行循环，若从i所在位置跳跃cur步能直接跳出去，那么退出循环。否则，需要找到从i开始到i+cur范围内能走到最远的元素索引index，nums[index]就是新的能跳跃的最大步数，index是新的起跳点，将res加1。最后由于只是判断了能到达结尾就退出循环了，没有将res加1，因此最后的返回结果是res+1.

代码

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1){
            return 0;
        }
        //每跳一次，res+1
        int res = 0;
        //i表示即将跳到的位置
        int i = 1;
        //cur表示最大能跳几步
        int cur = nums[0];
        while(i < nums.length-1){
            if(i+cur>=nums.length) break;
            int max = cur;
            int index = -1;
            for(int j = i; j < i+cur; j++){
                max--;
                if(nums[j]>max){
                    max = nums[j];
                    index = j;
                }
            }
            cur = nums[index];
            i = index+1;
            res++;
        }
        return res+1;
    }
}
划分字母区间
极简IOC