面试算法题之跳跃游戏，“You Jump, I Jump”
面试算法题之跳跃游戏，“You Jump, I Jump”
跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
解题思路
我们从末尾倒着看，例如： [3,2,2,0,4]。
初始需要跳跃的步数为cnt=0，而最后一个元素4是我们需要到达的终点，可以不用考虑，从0开始。
- 元素
0等于cnt，无法跨越过去，于是需要跳跃的步数加1，此时cnt=1。继续下一个元素2。 - 元素
2大于cnt，可以跨越元素0，于是cnt赋值 0 后重新计数。 - 遍历完所有元素后，判断需要跨越的步数是否等于 0，等于 0 则表示可以跨越到最后的元素；否则不能跨越到最后的元素。
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int cnt = 0; // 需要跳跃的步数
for(int i=n-2;i>=0;i--) {
if(cnt >= nums[i])
cnt++;
else
cnt = 0;
}
return cnt == 0;
}
};思考
- 为什么要从 n-2 开始从尾到头遍历？
答案在解题思路中哦。
跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
贪心思路
我们初始化边界end为 0，从头到尾开始遍历，每次记录下当前能跳跃到的最大位置，当遍历到边界下标时，将边界位置更新为最大位置maxPos，并且增加一次跳跃。
最后一个元素是肯定可以达到的，我们记录的边界其实是肯定大于等于最后一个元素位置的，否则就不符合题意了。如果遍历到最后一位，则可能会多计算一次跳跃（在刚好跳跃到最后一个元素位置时）。
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int maxPos = 0; // 记录最远的距离
int end = 0; // 记录边界位置
int cnt = 0; // 记录跳跃的次数
for(int i=0;i<n-1;i++) {
if(maxPos >= i) {
maxPos = max(maxPos, i+nums[i]);
if(i == end) {
end = maxPos;
cnt++;
}
}
}
return cnt;
}
};思考
- 为什么不需要遍历最后一个元素？
答案在解题思路中哦，也可以自己实验一下。
跳跃游戏 III
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
广度优先搜索
我们可以从start开始，将其加入到队列中，每次取队列头部元素，看能跳跃到的所有位置，如果能跳跃的位置中任意一个是0，那么就返回true。如果跳跃的位置在数组范围内，就需要将其加入队列，并标识为已访问。如果遍历完后仍没有找到为0的，则返回false。
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int top = 0, n = arr.size();
queue<int> q;
vector<bool> vis(n);
q.push(start);
while(!q.empty()) {
top = q.front();
q.pop();
if(arr[top] == 0)
return true;
int a = top - arr[top];
int b = top + arr[top];
if(a >= 0 && a < n && !vis[a]) {
q.push(a);
vis[a] = true;
}
if(b >= 0 && b < n && !vis[b]) {
q.push(b);
vis[b] = true;
}
}
return false;
}
};