贪心---跳跃游戏 Posted on 2021-08-09 00:00:00 2021-08-09 00:00:00 by Author 摘要 给你一个数组，其中每个元素表示你能够从该位置到达下个位置的步数，那么从开始位置起，你能判断是否有一条合适的行走步数使其能够到达数组末尾吗？？？？ # 贪心---跳跃游戏 1. 题目描述 - 给定一个非负整数数组 `nums` ，你最初位于数组的 **第一个下标** 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。 - **提示：** - `1 <= nums.length <= 3 * 104` - `0 <= nums[i] <= 105` 2. 示例描述 - 示例一 ``` 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 ``` - 示例二 ```java 输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。 ``` 3. 解题思路 - 首先对于本题来说，看似好像很简单，但是实际认真想的话，还是有点复杂。当看到本题目的时候，我就在想思路，其中让我 卡壳的地方在于，对于某个位置而言，如果当前位置加上其能够跳的距离也就是该位置能够到达下一个位置，如果我们直接到达下一个位置的话，那么这个位置与下个位置之间的地方，有可能会出现比下个位置到达更远的地方，那么我们为何不直接跳到这两个位置之间的这个位置尼，那么出现这种情况该怎么处理尼。 - 对于这个问题我想了好久，最终我不知怎么了，就随便改了一个循环条件之后，没想到就能通过了。然后我就慢慢想这是为什么。之后我大概想明白了，在某个位置时，该位置加上其能够跳跃的距离就是当前位置能够到达的距离，如果该位置所能到达的距离，比之前位置所能到达最远距离远，说明我们可以从该位置直接到达该位置能够到达的最远距离处。正如我之前卡壳的地方，如果到达最远距离处，其两个位置之间有比该位置能够到达最远距离更远的位置的话，那么我们为何不跳到这两个位置见的这个地方尼，于是重点就在于此，此位置能够到达最远的距离肯定是大于或者等于当前的位置，所以我们在这个位置所能到达最远距离之间寻找，这之间的位置能不能到达更远的地方，如果能，那么这个更远的距离就改变，就这样一直找下去，在这过程中会出现如果到达位置提前到达终点位置，那么说明可以到达，还有一直情况就是已经到达最远距离处了，但是还没有到达终点，那么说明从开始位置无论如何也到达不了终点。 - 以上就是我自己思路，下面是具体代码逻辑已经每步的代码注释。 4. 代码示例 ```java public boolean canJump2(int[] nums) { //判断边界条件，如果数组长度小于等于1，无论如何都能到达 if(nums.length<=1){ return true; } //定义一个能否到达终点的变量 int result =0; //这里为什么循环条件是小于等于result尼 //解释将在循环里面说 for (int i=0;i<=result;i++){ //每到一个位置可以判断这个位置所能到达的最远处 //为什么和result比较尼，因为在到达此位置之前，可能之前位置所能到达最远距离会比当前位置所能到达最远距离远。 //这样就能保证每到一个位置，能够筛选出前面的位置与当前位置所能到达的最远距离了。 result = Math.max(result,nums[i]+i); //如果最远距离大于或者等于数组最后一个位置，说明可以完成跳跃。 if(result>=nums.length-1){ return true; } //否则继续循环，这里解释为什么循环条件是i<=result //因为当前位置与之前位置所能到达的最远距离肯定大于或者等于当前位置。 //第一种情况，如果等于当前的距离，并且该位置所能到达最远距离也等于当前位置，而且最远距离小于数组的最后元素的位置 //那么无论如何也到达不了终点。怎么说尼，举个例子[3,2,1,0,4]，这个数组，前三个位置元素最远距离是到达元素为0的位置 //而元素为0位置最远到达距离也是此位置，并且此位置不是数组结尾的位置，导致到达此位置时已经不能在跳跃了，也就是不能到达终点位置了。 //第二种情况，如果当前位置小于当前位置所能到达的最远距离，那么当前位置之后的元素有可能会推进最远距离，使最远距离尽可能逼近或者大于终点位置。 //使得循环条件不断满足，得到最远距离其中得元素能够到达得最远距离。 } //如果最远距离都不满足循环里面得判断条件，那么说明不能到达终点 //返回false return false; } ```
{{ item.content }}
{{ child.content }}