各网站封面尺寸,做养生类项目的网站,网站外链建设方法,网络推广公司怎么接单题目
给定一个非负整数数组#xff0c;你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1#xff1a; 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步#xff0c;从位置 0 到达 位置 1…题目
给定一个非负整数数组你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例2 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 所以你永远不可能到达最后一个位置。 思考
这个题目需要注意每个元素代表你在该位置可以跳跃的最大长度而不是长度。也就是说如果是3那么你可以走0123步。 其次观察题目不能到达最后一格的原因是某一格元素为0且之前没有足够步数跨越这个0 来分析一下示例2[3,2,1,0,4]连续的0个数为1 我们先遍历找到元素0下标为3。此刻从它前面的一个元素开始往前遍历 下标为2的元素为1步数为1步数 - 连续0的第一个下标 - 当前下标 - 1 1 - 3-2 -11 连续的0个数,所以不行 下标为1的元素为2步数为2步数 - 连续0的第一个下标 - 当前下标 - 1 2 - 3-1 -11 连续的0个数,所以不行 下标为0的元素为3步数为3步数 - 连续0的第一个下标 - 当前下标 - 1 3 - 3-0 -11 连续的0个数,所以不行
所以我们可以归纳出一个明显的特征步数 - 连续0的第一个下标 - 当前下标 - 1 连续的0个数 只有满足这个特征才算是可以到达最后一个位置。 代码实现的时候还需要考虑特殊情况以及细节 1、长度为1直接为true 2、遍历从 i1开始i nums.size()-1,结束 3、获取连续0的个数
int succesive_zero 0;
if(nums[i] 0)
{succesive_zero 1;for(int j i;j nums.size()-2;j){if(nums[j] 0 nums[j1] 0) succesive_zero;else break;}
}4、如果找到了可以可以跨越连续0的步数那么将i指针移动到跳跃的格子。并且如果在连续0之前没有找到足够大的步数跳跃则说明不能到达最后一个格子但是找到了还需要遍历之后的情况直到整个数组都被遍历了且没有出现不能跳过的情况我们才能返回true。
int flag 0;
for(int j i-1;j 0;j--)
{if((nums[j]-(i-j-1)) succesive_zero){iisuccesive_zero;flag1;break;}
}
if(flag 0) return false;AC代码
class Solution {
public:bool canJump(vectorint nums) {if(nums.size() 1) return true;if(nums[0] 0) return false;for(int i1;i nums.size()-1;i){//如果当前为0记录连续0的个数int succesive_zero 0;if(nums[i] 0){succesive_zero 1;for(int j i;j nums.size()-2;j){if(nums[j] 0 nums[j1] 0) succesive_zero;else break;}//cout succesive_zerosuccesive_zero endl;//判断i之前有没有步数在走到i后还有剩余的步数跳过这个0说明暂时可以否则不行int flag 0;for(int j i-1;j 0;j--){if((nums[j]-(i-j-1)) succesive_zero){iisuccesive_zero;flag1;break;}}if(flag 0) return false;}}return true;}
};参考贪心思路思路更加直观代码逻辑更加简单
参考代码随想录的思路https://mp.weixin.qq.com/s/606_N9j8ACKCODoCbV1lSA 跳几步无所谓关键在于可跳的范围 每次取最大的跳跃步数这个就是跳跃的覆盖范围。 问题转化为跳跃覆盖范围究竟可不可以覆盖到终点。 每次移动取最大跳跃步数(得到最大覆盖范围)每移动一个单位就更新最大覆盖范围。
**局部最优解**每次取最大跳跃步数 **整体最优解**最后得到整体最大覆盖范围看是否能到终点。 编程细节 1、i只能在cover范围内移动每移动一个元素cover得到该元素数值补充覆盖范围让i继续移动下去。 2、cover每次只取max(钙元素数值补充后的范围cover本身范围) 3、如果cover 终点下标直接return true AC代码
class Solution {
public:bool canJump(vectorint nums) {//初始化覆盖范围int cover 0;if(nums.size() 1) return true;//从0开始的覆盖范围迭代for(int i 0; i cover;i){cover max(inums[i],cover);if(cover nums.size() - 1) return true; }return false;}
};有一说一这个思路确实妙也很符合贪心的逻辑。
