宁波手机建站模板,山东省建设执业资格注册管理中心网站,pc网站制作公司,珠海市公司网站建设目录
单调递增的数字
坏了的计算器
合并区间
无重叠区间
用最少数量的箭 声明#xff1a;接下来主要使用贪心法来解决问题#xff01;#xff01;#xff01;
单调递增的数字
题目 思路
如果我们遍历整个数组#xff0c;然后对每个数k从[k,0]依次遍历寻找“单调递…目录
单调递增的数字
坏了的计算器
合并区间
无重叠区间
用最少数量的箭 声明接下来主要使用贪心法来解决问题
单调递增的数字
题目 思路
如果我们遍历整个数组然后对每个数k从[k,0]依次遍历寻找“单调递增”的数字对于本题数据量最大为10^9,显然是会超时的,下面将介绍一种贪心解法。
把数字转换成字符串然后从头到尾遍历整个字符串当遇到后一个字符小于当前一个字符时把当前字符-1之后的字符全都修改正字符9。如下 但是这种方法还是有缺陷的比如下面的这种情况 因此我们需要对上面的贪心策略进行修改修改后的贪心策略如下
贪心策略
把数字转换成字符串然后从头到尾遍历整个字符串当遇到后一个字符小于当前一个字符时向前寻找和当前字符相等的字符把与当前字符相等的字符的最左段字符字符-1之后的字符全都修改正字符9。如下 代码
class Solution {
public:int monotoneIncreasingDigits(int n) {string sto_string(n);int ms.size();int i0;while(i1m s[i]s[i1])i;if(i1m) return n;else{while(i-10 s[i-1]s[i])i--;s[i]s[i]-1;for(ii1;im;i)s[i]9;}return stoi(s);}
};
坏了的计算器
题目 思路
因为可对startValue进行乘2和减1操作但是要想由startValue变换成target毫无确定的头绪可言.
贪心策略
采用“正难则反”的思想我们可以想想如何将target变换成startValue此时有两种操作分别为除2和加1而此时可以分两种情况进行讨论分别是
当targetstartValue,当target为奇数时由于startValue为整数此时只能进行1操作 当target为偶数时要想变换成startValue此时只能进行1操作
即当targetstartValue时,变换操作次数为startValue-target.
当targetstartValue,当target为奇数时由于startValue为整数此时只能进行1操作 当target为偶数时要想变换成startValue可进行除2和1操作混合进行但是如果混合操作进行的话要想让target变换成startValue此时的操作次数是大于只进行除2操作的因此此时只进行除2操作
即当targetstartValue时,先判断target的奇偶性进行对应操作直到targetstartValue或者targetstartValue然后进行targetstartValue对应的规则。
代码
class Solution {
public:int brokenCalc(int startValue, int target) {long long ret0;while(startValuetarget){if(target%20) target/2;else target1;ret;}retstartValue-target;return ret;}
};
合并区间
题目 思路
首先我们先对集合按区间左端点进行排序因为如果不排序的话比较两个区间左端点的大小是需要不断遍历集合的对集合按区间左端点进行排序后的情况如下
基准参考区间的左端点记为left右端点记为right后一段区间的左端点记为a右端点记为b。 贪心策略
对于aright的区间需要进行合并此时需要进行rightmax(right,b)的操作即可
对于aright的区间, 不需要进行合并, 此时需要进行leftarightb和记录已合并区间的操作即可。
但是最后还需要记录最后一个区间。
代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {int nintervals.size();sort(intervals.begin(),intervals.end());vectorvectorint ret;int leftintervals[0][0],rightintervals[0][1];for(int i1;in;i){int aintervals[i][0],bintervals[i][1];if(righta)rightmax(right,b);else{ret.push_back({left,right});lefta,rightb;}}ret.push_back({left,right});return ret;}
};
无重叠区间
题目 思路
首先我们先对集合按区间左端点进行排序因为如果不排序的话比较两个区间左端点的大小是需要不断遍历集合的对集合按区间左端点进行排序后的情况如下
基准参考区间的左端点记为left右端点记为right后一段区间的左端点记为a右端点记为b。 贪心策略
题目要求保证无重复区间需要删除区间的最少数量等价于尽可能保留更过数量的区间使用一个变量ret统计删除区间的数量。
对于aright的区间需要进行删除一个右端点较大的那个区间此时需要进行rightmin(right,b)和ret的操作即可
对于aright的区间, 只需要进行rightb的操作即可。
代码
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {int nintervals.size();sort(intervals.begin(),intervals.end());int ret0;int rightintervals[0][1];for(int i1;in;i){int aintervals[i][0],bintervals[i][1];if(aright){ret;rightmin(right,b);}elserightb;}return ret;}
};
用最少数量的箭引爆气球
题目 思路
首先我们先对集合按区间左端点进行排序因为如果不排序的话比较两个区间左端点的大小是需要不断遍历集合的对集合按区间左端点进行排序后的情况如下
基准参考区间的左端点记为left右端点记为right后一段区间的左端点记为a右端点记为b。 这道题不同于前两道题的明显之处是前两道题求的是并集而本道题求的是交集。
即求的是下面第二张图的交集个数而非第一张图。 使用变量ret记录重叠区间个数。
贪心策略
当aright时进行操作rightmin(right,b)即可
当aright时进行操作rightb,ret即可。
代码
class Solution {
public:int findMinArrowShots(vectorvectorint points) {int npoints.size();sort(points.begin(),points.end());int ret0;int rightpoints[0][1];for(int i1;in;i){int apoints[i][0],bpoints[i][1];if(aright)rightmin(right,b);elserightb,ret;}ret;return ret;}
};
文章转载自： http://www.morning.pxbky.cn.gov.cn.pxbky.cn http://www.morning.trrd.cn.gov.cn.trrd.cn http://www.morning.bmmyx.cn.gov.cn.bmmyx.cn http://www.morning.zdmrf.cn.gov.cn.zdmrf.cn http://www.morning.bmssj.cn.gov.cn.bmssj.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.rdxnt.cn.gov.cn.rdxnt.cn http://www.morning.zryf.cn.gov.cn.zryf.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.hffpy.cn.gov.cn.hffpy.cn http://www.morning.rqhn.cn.gov.cn.rqhn.cn http://www.morning.lxjxl.cn.gov.cn.lxjxl.cn http://www.morning.lthgy.cn.gov.cn.lthgy.cn http://www.morning.qwbht.cn.gov.cn.qwbht.cn http://www.morning.mgnrc.cn.gov.cn.mgnrc.cn http://www.morning.pxwjp.cn.gov.cn.pxwjp.cn http://www.morning.rgxn.cn.gov.cn.rgxn.cn http://www.morning.sjsks.cn.gov.cn.sjsks.cn http://www.morning.lfbsd.cn.gov.cn.lfbsd.cn http://www.morning.qctsd.cn.gov.cn.qctsd.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.lmtbl.cn.gov.cn.lmtbl.cn http://www.morning.lpmdy.cn.gov.cn.lpmdy.cn http://www.morning.phxdc.cn.gov.cn.phxdc.cn http://www.morning.wjlnz.cn.gov.cn.wjlnz.cn http://www.morning.plflq.cn.gov.cn.plflq.cn http://www.morning.rqgbd.cn.gov.cn.rqgbd.cn http://www.morning.nzhzt.cn.gov.cn.nzhzt.cn http://www.morning.mwrxz.cn.gov.cn.mwrxz.cn http://www.morning.ssglh.cn.gov.cn.ssglh.cn http://www.morning.dxpqd.cn.gov.cn.dxpqd.cn http://www.morning.rfwkn.cn.gov.cn.rfwkn.cn http://www.morning.nzqmw.cn.gov.cn.nzqmw.cn http://www.morning.lcdtb.cn.gov.cn.lcdtb.cn http://www.morning.hkchp.cn.gov.cn.hkchp.cn http://www.morning.vjdofuj.cn.gov.cn.vjdofuj.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn http://www.morning.sbncr.cn.gov.cn.sbncr.cn http://www.morning.lnsnyc.com.gov.cn.lnsnyc.com http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.qxlxs.cn.gov.cn.qxlxs.cn http://www.morning.xyhql.cn.gov.cn.xyhql.cn http://www.morning.mmhyx.cn.gov.cn.mmhyx.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.wfzlt.cn.gov.cn.wfzlt.cn http://www.morning.tbqdm.cn.gov.cn.tbqdm.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.mwjwy.cn.gov.cn.mwjwy.cn http://www.morning.nzklw.cn.gov.cn.nzklw.cn http://www.morning.trjp.cn.gov.cn.trjp.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.sgfnx.cn.gov.cn.sgfnx.cn http://www.morning.hwnqg.cn.gov.cn.hwnqg.cn http://www.morning.gwxwl.cn.gov.cn.gwxwl.cn http://www.morning.hxbps.cn.gov.cn.hxbps.cn http://www.morning.nxstj.cn.gov.cn.nxstj.cn http://www.morning.tnmmp.cn.gov.cn.tnmmp.cn http://www.morning.kpwdt.cn.gov.cn.kpwdt.cn http://www.morning.bntgy.cn.gov.cn.bntgy.cn http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.ptqpd.cn.gov.cn.ptqpd.cn http://www.morning.pqkyx.cn.gov.cn.pqkyx.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.psdsk.cn.gov.cn.psdsk.cn http://www.morning.srnhk.cn.gov.cn.srnhk.cn http://www.morning.wyppp.cn.gov.cn.wyppp.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.tqhpt.cn.gov.cn.tqhpt.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.kjxgc.cn.gov.cn.kjxgc.cn http://www.morning.rbkl.cn.gov.cn.rbkl.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.cnwpb.cn.gov.cn.cnwpb.cn http://www.morning.gmgyt.cn.gov.cn.gmgyt.cn
