春 字节题（五）

leetcode 55 跳跃游戏 && leetcode 45 跳跃游戏II二分查找

55
给定一个非负整数数组nums,你最初位于数组的第一个下标，数组中的每个元素代表你在该位置可以跳跃的最大长度；
判断是否能够到达最后一个下标；

例如：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

//贪心解法
//思路：
//i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
//而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
//如果cover大于等于了终点下标，直接 return true 就可以了。
class Solution
{
public:
	bool canJump(vector& nums)
	{
		int cover = 0;//初始化一个变量用来表示可以跳跃的覆盖范围
		if (nums.size() == 1)return true;
		for (int i = 0; i <= cover; i++)//在当前可以遍历到的覆盖范围内进行遍历; i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
		{
			cover = max(i + nums[i], cover);//更新最大的覆盖范围
			if (cover >= nums.size() - 1)return true;//最终的问题转换为跳跃覆盖范围是不是可以覆盖到终点
		}
		return false;
	}
};

45
给定一个非负整数数组nums,你最初位于数组的第一个位置；
数组中的每一个元素代表你可以在该位置可以跳跃的最大长度；
你的目标是使用最少的跳跃次数达到数组的最后一个位置；

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

算法思想：
核心：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况；
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：

如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

// 版本二
class Solution {
public:
    int jump(vector& nums) {
        int curDistance = 0;    // 当前覆盖的最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};

class Solution
{
public:
	int search(vector& nums, int target)
	{
		int l = 0, r = nums.size() - 1;
		while (l <= r)
		{
			int mid = l + (r - l) / 2;
			if (nums[mid] == target)
			{
				return mid;
			}
			else if (nums[mid] < target)l = mid + 1;
			else if (nums[mid] > target)r = mid - 1;
		}
		return -1;
	}
};