[Leetcode]44.跳跃游戏Ⅰ&&45.跳跃游戏Ⅱ

跳跃游戏链接

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

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

示例 2:

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

思路:

如果只是判断能否跳到终点,我们只要在遍历数组的过程中,更新每个点能跳到最远的范围就行了,

如果最后这个范围大于等于终点,就是可以跳到。

class Solution {
private:
inline int max(const int a,const int b){return a>b?a:b;} public:
bool canJump(vector<int>& nums) {
int count=;
for(int i=;i<nums.size()&&i<=count;i++){
count=max(count,i+nums[i]);
}
if(count<nums.size()-)return false;
return true;
}
};

跳跃游戏Ⅱ
现在来看跳跃问题一的衍生:

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
  从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

第一种方法: 动态规划(超时)

定义状态dp[i]:到达位置i的最小步数

初始化dp: 0x3f3f3f3f,即一个极大值。

状态转移方程:对每个位置i为起点可以到达的位置j,都有dp[j]=min(dp[i]+1,dp[j]);

最后想要的结果:dp[n-1]

时间复杂度:O(n^2)

class Solution {
private: inline int min(const int a,const int b){return a>b?b:a;}
public:
int jump(vector<int>& nums) {
int n=nums.size();
int dp[n];
memset(dp,0x3f,sizeof(dp));
/*初始化成最大值*/
dp[]=;
for(int i=;i<n-;i++){
for(int j=i+;j<n&&j<=i+nums[i];j++)
dp[j]=min(dp[i]+,dp[j]);
}
return dp[n-];
}
};

第二种方法:贪心算法

我们可以把整个数组分成很多个区域,

把样例[2,3,1,1,4]拿来做例子:

[2,3,1,1,4] 可以分成如左边三个区域,第i个区域代表从起点可以通过i-1步到达这些区域。

如何求上述分成上述区域呢?如下递归定义:

第1个区域就是起始位置一个。

第n个区域为(第n-1个区域最远的位置, 第n-1个区域为起点所到达的最远位置]

如何求这些区域呢,实际上可以遍历的过程中动态的求。

我们需要每次遍历的时候更新这些区域,实际上我们就用了两个变量currentReach和newReach区分区域,

前者记录现在区域的最远位置,newReach代表从这个区域能到达的最远位置。有上面我们可以知道下一个区域的范围为(currentReach,newReach]

因为我们只考虑最后一个点在第ans个区域而答案就是ans-1。遍历的过程中如果下标大于currentReach,说明进入了一个新的区域,区域就要更新。

newReach要不断更新的原因是,在到达currentReach前,我们并不知道从现在区域到达的最远位置,必须不断更新寻找。

代码如下:

 class Solution {
inline int max(const int a,const int b){return a>b?a:b;}
public:
int jump(vector<int>& nums) {
int newReach=;//记录从现在区域出发能到达的最远位置
int ans=;//记录次数
int currentReach=;//记录现在区域的最远位置
int n=nums.size();
for(int i=;i<n;i++){
if(i>currentReach){//超过现在区域的最远位置,说明进入了一个新区域,ans++
ans++;
currentReach=newReach;//更新现在区域的最远位置
}
newReach=max(newReach,i+nums[i]);//每次都更新从此区域出发的最远到达位置
}
return ans;
}
};
上一篇:LeetCode:跳跃游戏【55】


下一篇:LeetCode 45跳跃游戏&46全排列