贪心算法-跳跃游戏——a

ゝ一纸荒年。 2021-12-04 05:07 264阅读 0赞

## 1、题目描述 ##

*  给定一个非负整数数组，你最初位于数组的第一个位置。
 *  数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *  判断是否能够到达最后一个位置。

## 2、问题分析 ##

给定一个数组，数组中每个位置的数字代表当前位置i能够向前跳跃num\[i\]的距离，然后判断最后能够从第一个位置跳到最后一个位置。这道题的难点就在于每次跳多远的距离算合适呢？如果从i的位置能跳num\[i\]距离最远能到达j的位置，那么这中间的任何一个位置我们都能跳到，但我们具体是跳到i--j之间的哪个位置才是真正合适的位置？利用贪心的思想我们的目的是判断最后能否跳到最后一个位置，其实就是只要能保证在i--j之间跳到一个能够在下一次跳的更远的距离，那么这个位置就是最合适的位置。

实例1：

输入: [2,3,1,1,4]
    输出: true
    解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

实例2：

输入: [3,2,1,0,4]
    输出: false
    解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

## 3、算法思想 ##

1、首先根据num\[\]数组求出index\[i\]=i+num\[i\];

2、设置一个变量jump表示当前的位置，设置一个变量max\_index表示当前指针经过的index\[\]数组中所能达到的最远距离

3、jump变量逐步往后循环，当到达index\[\]最后的时候或者是变量max\_index的值小于jump的值的时候停止循环，jump能走到数组的最后表示能够到达最后，如果是因为变量max\_index的值小于jump的值造成的循环终止，那么就表示不能达到最后。

## 4、解题代码 ##

1 package com.baozi.test;
     2 
     3 /**
     4  * @author BaoZi
     5  * @create 2019-05-14-20:03
     6  */
     7 public class Solution5 {
     8     public static void main(String[] args) {
     9         int[] nums= new int[]{2,0,1,1,0,1,2,10};
    10         boolean result = Solution5.canJump(nums);
    11         System.out.println(result);
    12     }
    13 
    14     public static boolean canJump(int[] nums) {
    15         int[] index = new int[nums.length];
    16         int jump = 0;
    17         int max_index = index[0];
    18         for (int i = 0; i < nums.length; i++) {
    19             index[i] = i + nums[i];
    20         }
    21         while (jump < nums.length && jump <= max_index) {
    22             if (max_index < index[jump]) {
    23                 max_index = index[jump];
    24             }
    25             jump++;
    26         }
    27         if (jump == index.length) {
    28             return true;
    29         }
    30         return false;
    31     }
    32 }

转载于:https://www.cnblogs.com/BaoZiY/p/10861416.html