Java教程

45. 跳跃游戏 II

本文主要是介绍45. 跳跃游戏 II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 题目:45. 跳跃游戏 II
    • 给定一个非负整数数组,你最初位于数组的第一个位置。
    • 数组中的每个元素代表你在该位置可以跳跃的最大长度。
    • 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    • 假设你总是可以到达数组的最后一个位置。
    • 示例 1:
    • 输入: [2,3,1,1,4]
      输出: 2
      解释: 跳到最后一个位置的最小跳跃数是 2。
      从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
      示例 2:
    • 输入: [2,3,0,1,4]
      输出: 2
      提示:
    • 1 <= nums.length <= 1000
      0 <= nums[i] <= 10^5
  • 思路:第i-1步能走到的最远位置为arr[i-1],则arr[i-1]~arr[i]之间都是第i步可以跳到的位置,所以第i+1步最远的位置就是在这范围中 值的下标和值相加最大的距离。
  • 所以需要三个变量,第i步可以跳到的位置的左右边界,和step数。
  • 代码

    ```java
    	  package class10;
    	  
    	  // 本题测试链接 : https://leetcode.com/problems/jump-game-ii/
    	  public class Code01_JumpGame {
    	  
    	  	public static int jump(int[] arr) {
    	  		if (arr == null || arr.length == 0) {
    	  			return 0;
    	  		}
    	  		int step = 0;
    	  		int cur = 0;
    	  		int next = 0;
    	  		for (int i = 0; i < arr.length; i++) {
    	  			if (cur < i) {
    	  				step++;
    	  				cur = next;
    	  			}
    	  			next = Math.max(next, i + arr[i]);
    	  		}
    	  		return step;
    	  	}
    	  
    	  }
    	  
    ```
    
这篇关于45. 跳跃游戏 II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!