浙江建设网官方网站,企业营销策略分析论文,做百度移动网站点击,网络营销的目的是什么题目#xff1a;
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例…题目
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。思路
不能遍历依次遍历每个数字每种跳跃能否到达终点这样的话会非常复杂。
答案思路
遍历每个数字看该数字的“覆盖范围” 能否覆盖到最后一个元素。如果可以覆盖到最后一个元素则该数组可以跳跃到最后一个元素。
代码
class Solution {
public:bool canJump(vectorint nums) {int n nums.size();// 思路遍历每个数字这个数字覆盖的范围可以到最后一个数字则返回true// 同时当前这个数字可以被之前的覆盖当前数字可到达if (n 1)return true;int range nums[0];int i;for (i 1; i n; i) {if (range i) { // 当前数字可到达int t i nums[i]; // 当前数字的覆盖范围range max(t, range); // 与之前数字的覆盖范围比较取最大值即最远覆盖范围// range i nums[i];}// 如果当前覆盖范围可以覆盖到最后一个数字则最后一个数字可到达返回true即可。if (range n - 1) {return true;}}// 遍历完之后发现没有可以覆盖到最后一个数字的下标。则返回falsereturn false;}
}; 运行结果
