贪心(一步步进阶)

贪心算法

定义

贪心算法是在对问题求解时 总是做出在当前看来时最好的选择(局部最优来达到全局最优)
贪心算法并不是对所有问题都可以得到整体的最优解 关键是贪心策略的选择 选择的贪心邪恶略必须具有无后效性就是说某个状态以前的过程不会影响以后的状态 只于当前状态有关

解题第一般步骤

1. 建立数学模型来描述问题
2. 把求解的问题分成若干子问题
3. 对每一子问题求解 得到子问题的局部最优解
4. 把子问题的最优解合并为原来问题的一个解

贪心题目

LeetCode 435 无重复区间

LeetCode435

classSolution{public:interaseOverlapIntervals(vector<vector<int>>&intervals){//按照结尾时间的大小排序//如果a[0]==b[0]也不用考虑顺序问题//因为我们只用判断能不能一次更新一下end就行了//不必在意两个区间的开始时间相同时的情况了sort(intervals.begin(),intervals.end(),[](autoa,autob){returna[1]<b[1];});//到这里已经排好序了 按照结束时间排序intnum=1;//一次能有几个区间intend=intervals[0][1];//当前的结尾时刻for(intj=1;j<intervals.size();++j){if(end<=intervals[j][0]){//如果可以更新结尾时刻end=intervals[j][1];//更新结尾num++;//数量++}}//总区间个数-一次的区间个数=需要删除的区间个数returnintervals.size()-num;//返回要删除的区间个数}};

LeetCode 452 用最少数量的箭引爆气球

LeetCode 452

classSolution{public:intfindMinArrowShots(vector<vector<int>>&points){//先让数组按照气球结束区间排序sort(points.begin(),points.end(),[](autoa,autob){returna[1]<b[1];});intnum=1;//当前的结果 就时弓箭的个数intcurr=points[0][1];//目前的结尾for(inti=1;i<points.size();++i){if(curr<points[i][0]){//如果以当前结尾的弓箭不能射到这个i位置的气球num++;curr=points[i][1];}//如果以当前结尾的弓箭能射到这个i位置的气球 就直接j++ 就行了 就是下一次循环}returnnum;}};