受欢迎的购物网站建设,杭州 网站建设公司,怀宁县住房与城乡建设局网站,wordpress加载插件下载一、跳跃游戏跳跃游戏类的问题#xff0c;不关心每一步怎么跳#xff0c;只需要关心最大覆盖范围这里注意i是在当前最大可覆盖范围内遍历#xff0c;如{2,1,0,1}#xff0c;就是在0~2范围内遍历#xff0c;千万不能0~numsSize-1范围内遍历#xff01;#xff01;#x…一、跳跃游戏跳跃游戏类的问题不关心每一步怎么跳只需要关心最大覆盖范围这里注意i是在当前最大可覆盖范围内遍历如{2,1,0,1}就是在0~2范围内遍历千万不能0~numsSize-1范围内遍历bool canJump(int* nums, int numsSize){//不关心每一步怎么跳只需要关心最大覆盖范围int cover0;for(int i0;icover;i){coverfmax(cover,nums[i]);if(covernumsSize-1) return true;}return false;
}二、跳跃游戏II没见过不好想建议记下来关键是当前覆盖范围和下一步覆盖范围都要考虑计算下一步覆盖范围的目的是用来更新当前覆盖范围以保证跳跃步数最少int jump(int* nums, int numsSize){//统计两个覆盖范围:当前这一步的最大覆盖和下一步最大覆盖//如果移动下标达到了当前这一步的最大覆盖最远距离了还没有到终点的话//那么就必须再走一步来增加覆盖范围直到覆盖范围覆盖了终点if(numsSize1) return 0;int curCover0,nextCover0;int result0;for(int i0;icurCover;i){nextCoverfmax(nextCover,inums[i]);if(icurCover){if(curCovernumsSize-1){result;curCovernextCover;if(nextCovernumsSize-1) break;}else break;}}return result;
}三、无重叠区间区间重叠类问题第一步排序区间判断重叠方法若当前区间的右边界大于下一个区间的左边界则表示有重叠合并实质上就是更新当前区间的右边界class Solution {
private:static bool cmp(const vectorint a,const vectorint b){return a[0]b[0];}
public:int eraseOverlapIntervals(vectorvectorint intervals) {//按照区间左边界从小到大排序//若当前区间的右边界大于下一个区间的左边界则表示有重叠//可以把移除理解成一种特殊的合并所有重叠区间合并之后右边界为最小的那个if(intervals.size()1) return 0;sort(intervals.begin(),intervals.end(),cmp);int result0;for(int i1;iintervals.size();i){if(intervals[i-1][1]intervals[i][0]){intervals[i][1]fmin(intervals[i-1][1],intervals[i][1]);result;}}return result;}
};四、用最少数量的箭引爆气球实际上这题就是在问有多少组无重叠区间和上题都在研究重叠与无重叠区间的问题注意本题的重叠区间内的所有区间的右边界和上题一样也要更新为重叠区间里最小的右边界因为找最大重叠个数的重叠区间看的是“短板”class Solution {
private:static bool cmp(const vectorint a,const vectorint b){return a[0]b[0];}
public:int findMinArrowShots(vectorvectorint points) {if(points.size()1) return 1;sort(points.begin(),points.end(),cmp);int result1;for(int i1;ipoints.size();i){if(points[i-1][1]pointss[i][0])result;elsepoints[i][1]min(points[i-1][1],points[i][1]);}return result;}
};五、划分字母区间本题实际上就是在问:求每个闭包的长度所以关键就是怎么判断闭包的起始位置这就和跳跃游戏II有点像了~class Solution {
public:vectorint partitionLabels(string s) {//开辟一个数组记录每个字母的最后出现位置int cover[27];for(int i0;is.size();i)cover[s[i]-a]i;//到达最大覆盖距离时可以理解成这个闭包的最大覆盖范围//记录该覆盖范围的长度然后向后移动一个位置int left0,right0;vectorint result;for(int i0;is.size();i){rightmax(right,cover[s[i]-a]);if(iright){result.push_back(right-left1);lefti1;}}return result;}
};六、合并区间所谓合并区间其实就是重叠区间的右边界取重叠区间内最大右边界如果下一个区间和当前重叠区间重叠则更新当前重叠区间的右边界若不重叠说明是新的闭包上一个重叠区间更新完成插入result新的重叠区间class Solution {
private:static bool cmp(const vectorint a,const vectorint b){return a[0]b[0];}
public:vectorvectorint merge(vectorvectorint intervals) {//所谓合并区间其实就是重叠区间的右边界取重叠区间内最大右边界//如果下一个区间和当前重叠区间重叠则更新当前重叠区间的右边界//若不重叠说明是新的闭包上一个重叠区间更新完成插入result新的重叠区间if(intervals.size()1) return intervals;sort(intervals.begin(),intervals.end(),cmp);vectorvectorint result;result.push_back(intervals[0]);for(int i1;iintervals.size();i){if(intervals[i-1][1]intervals[i][0])result.back()[1]max(intervals[i][1],result.back()[1]);elseresult.push_back(intervals[i]);}return result;}
};
