怎么在网站上做模式题库,网站开发外文文献,公司网站需要多少钱,做学校网站会下线吗题目描述#xff1a;给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示…题目描述给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。第一次尝试尝试用了递归结果超出时间限制了
class Solution {
public:bool canArrive(vectorint nums, int end){if(!end) return true;int index end-1;while(index 0){if(index nums[index] end){ //该坐标能到达if(canArrive(nums, index)) //判断能不能到达index这个坐标return true; //如果能则返回true}index--;}return false;}bool canJump(vectorint nums) {int end nums.size()-1;return canArrive(nums, end);}
}; // 73 / 172 个通过的测试用例超出时间限制第二次尝试跟官方解思路差不多但是没有想的很完善如果最大步数正好跳到了0就死路了。
class Solution {
public:bool canJump(vectorint nums) {int end nums.size() - 1;int index 0;if (nums[0] end) return true;while (nums[index] index end 1) {int step nums[index];int maxStep 0;for (int i 1; i step; i) {if (index i nums[index i] end) //能到达return true;maxStep max(maxStep, index i nums[index i]);}index maxStep; //跨最大一步}return false;}
}; // 167 / 172 个通过的测试用例 [5,9,3,2,1,0,2,3,3,1,0,0]思路
从后往前遍历以last_point为终点不断找能到达last_point的点并且替换last_point。
最后如果last_point为0则代表能到达最后一个下标代码解析
class Solution {
public:bool canJump(vectorint nums) {int end nums.size() - 1;if (nums[0] end) return true;int index end-1; //从倒数第二个开始遍历int last_point end; //最靠近目标点且能到达的点while (index0) {//if (index 0) return true;if (index nums[index] last_point) {last_point index;}index--;}if (last_point 0) return true;return false;}
};学到的总结
从后往前遍历
