1，跳跃游戏II
题目连接：45. 跳跃游戏 II - 力扣（LeetCode）
【题目描述】
在给定的一个nums数组中，nums[i]表示从当前i位置最多可以向后跳跃nums[i]个位置。问跳跃到最后 数组最后一个元素的最少跳跃次数？？？
【贪心】
首先，需要注意的是，题目的意思是最远跳跃nums[i]个位置，而不是必须跳跃mun[i]个位置。
以一个例子来看：nums=[2,3,1,1,4,2,6,7,1]。nums[0]=2，所以可以从0位置最多向后跳跃2个位置，所以最远可以跳跃到1，也可以选择跳跃到3。
nums=[2,3,1,1,4,2,6,7,1]。还是以这个数组为例。
第一次的起跳位置是数组下标为0的位置。经过一次跳跃之后，可以到达3或者1，此时的位置是第二次起跳位置，也就是说第二次起跳的位置是3或者1。同理，假设3为第二次起跳的位置 ，那么可以到达【1，1，4】，假设1为第二次起跳的位置，可以到达【1】。两者取并集，可以得到从第二次起跳位置起跳，可以跳跃到的区间。后面也是同理，配图：
从上图我们可以发现二次起跳的位置【3，1】和三次起跳的位置【1，1，4】这两个区间存在交集。而题目中求的是最少跳跃次数，所以可以通过二次跳跃可以到达的位置，不会选择跳跃三次。
那么如何判断跳跃到数组的最后一个元素了？对于每一个跳跃区间，我们可以使用两个变量来维护这两个区间的开始位置和结束位置【left，right】，比如 对于二次起跳的位置（上图中蓝色部分的线），对应的区间就是【1，2】。当right超出数组的长度，就表示可以跳跃到数组的结尾位置了。注意：这个【left，right】区间存储的是下标，不是元素。
维护【left,right】区间，从上图可以发现，第三次起跳的【left，right】，其中left可以通过上一次起跳的【left，right】的right+1得来。而right就需要遍历第二次起跳的【left，right】找出最远的距离。
【代码】
只需遍历数组一遍，时间复杂度为O(N)
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size();
int maxpos=0;//存储下一次起跳的最远位置，也就是下一个right
int ret=0;//记录最终结果
int left=0,right=0;
while(left<=right)
{
if(maxpos>=n-1)//已经可以跳跃到数组结尾
{
return ret;
}
//遍历当前[left,right]，更新下一次的[left,right]
for(int i=left;i<=right;i++)
{
maxpos=max(maxpos,nums[i]+i);
}
left=right+1;
right=maxpos;
ret++;//跳跃次数++
}
return ret;
}
};2，跳跃游戏I
本题与上体思路一模一样，只是返回值修改以下即可。
class Solution {
public:
bool canJump(vector<int>& nums) {
//贪心
int n=nums.size();
int left=0,right=0,ret=0;
int maxPos=0;//记录下一个最远跳到的位置
while(left<=right)
{
if(maxPos>=n-1)
return true;
//跟新maxPos
for(int i=left;i<=right;i++)
maxPos=max(maxPos,nums[i]+i);
//更新区间
left=right+1;
right=maxPos;
ret++;
}
return false;
}
};3，加油站
【题目描述】
题目简单的理解，n个加油站，每个加油站有gas[i]升汽油。刚开始汽车的油箱为空。从第i个加油站行驶到第i+1个加油站，需要消耗cost[i]升汽油。问，是否存在一个加油站，是该汽车可以环绕n个加油占一周，回到起始加油站，返回该加油站的下标。
【暴力枚举算法】
我们可以枚举每个加油站位置，看看是否可以环绕一周，回到起始位置。
从第i个加油站到达第i+1个加油站，需要消耗cost[i]升汽油，而第i个加油站可以获得gas[i]升汽油，所以汽车要想从第i个加油站行驶到第i+1个加油站，必须保证gas[i]>=cos[i]。
我们可以将gas[i]-cos[i]的值保存于一个diff数组中（这个数组不需要定义出来，只是为了好理解），如果从第i个加油站开始走，那么mixup满足gas[i]>=cos[i]，也就是diff[i]>=0。
以题目中给的示例为例：
当我们选中一个位置作为起点，从当前位置，再次枚举步数（0~n-），以为可能下标会越界，所以需要在对数组长度取模。
【暴力代码】（会超时）
时间复杂度O（N^2）
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
//枚举起点
for(int i=0;i<n;i++)
{
int rest=0;//剩余汽油
for(int step=0;step<n;step++)//枚举步数
{
int index=(step+i)%n;//求出走step后的下标
rest+=gas[index]-cost[index];
if(rest<0)
break;
}
if(rest>=0)
return i;
}
return -1;
}
};
【贪心优化】
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
//枚举起点
for(int i=0;i<n;i++)
{
int rest=0;//剩余汽油
int step=0;
for(;step<n;step++)//枚举步数
{
int index=(step+i)%n;//求出走step后的下标
rest+=gas[index]-cost[index];
if(rest<0)
break;
}
if(rest>=0)
return i;
i+=step;//循环会完成+1工作
}
return -1;
}
};