【Check 78】2024-05-20 - 45. 跳跃游戏 II

[larscheng]

45. 跳跃游戏 II

[larscheng]

思路

贪心算法1：逆向搜索，复杂度O(n*n)

• 要到达最后一个位置，就找他前一个位置
• 贪心思路遍历数组找里它最远的那个可到达位置，然后继续找上上个位置，直到位置0
• O(n*n)/O(1)

贪心算法，正向搜索，复杂度O(n)

• 假设从首个位置出发，每次选择可以跳的更远的跳点
• 比如2，3，1，1，4，2，1
• 从2出发，可以跳3，1，优先选择3，因为从3可以跳的更远
• 从3出发，可以跳1，1，4，优先选择4，因为从3可以跳的更远
• O(n)/O(1)

  代码

class Solution { public int jump(int[] nums) { int lastIndex = nums.length-1; int steps=0; //从最后1个位置开始，找跳跃次数最少的上一个起跳点 while (lastIndex!=0){ //从左向右找，首个符合条件的即为跳跃次数最少的那个 for (int i = 0; i < lastIndex; i++) { if (nums[i] + i >= lastIndex) { lastIndex = i; steps++; break; } } } return steps; } }

```java
    public int jump(int[] nums) {
        int end=0;
        int maxIndex = 0;
        int steps = 0;
        for (int i = 0; i < nums.length-1; i++) {
            maxIndex = Math.max(maxIndex,nums[i]+i);
            if (i == end) {
                end = maxIndex;
                steps++;
            }
        }
        return steps;
    }

[larscheng]

思路

反向动态规划 dp[i] 表示 到达nums[i]的最小跳跃次数 i-1可以跳到i时，次数为dp[i-1]+1 i-2可以跳到i时，次数为dp[i-2]+1 ... 0可以跳到i时，次数为dp[0]+1 dp[i] = min(dp[i-1]+1,dp[i-2]+1,...dp[0]+1)

类似贪心算法，反向搜索，复杂度O(n*n)

代码

        public int jump(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = 0;
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[j] + j >= i) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[nums.length-1];
        }
    }