算法奇妙屋(四十二)-贪心算法学习之路 9

文章目录一. 力扣 [991. 坏了的计算器](https://leetcode.cn/problems/broken-calculator/description/)1. 题目解析2. 算法原理3. 代码二. 力扣 [56. 合并区间](https://leetcode.cn/problems/merge-intervals/description/)1. 题目解析2. 算法原理3. 代码三. 力扣 [435. 无重叠区间](https://leetcode.cn/problems/non-overlapping-intervals/description/)1. 题目解析2. 算法原理3. 代码四. 力扣 [452. 用最少数量的箭引爆气球](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/)1. 题目解析2. 算法原理3. 代码一. 力扣991. 坏了的计算器1. 题目解析题目还是很清晰易懂的, 只进行两种操作, 从起点数 s 变成 最终值 t, 最少需要几步操作2. 算法原理正面算很难, 但可以根据例子, 总结正面推导的特性, 可以用反面来直接排除一种情况3. 代码classSolution{publicintbrokenCalc(intstartValue,inttarget){intret0;while(targetstartValue){if(target%21){target;ret;}else{target/2;ret;}}returnretstartValue-target;}}二. 力扣56. 合并区间1. 题目解析题目简单易懂, 就是让求并集2. 算法原理3. 代码classSolution{publicint[][]merge(int[][]intervals){intmintervals.length,n2;Arrays.sort(intervals,(a,b)-a[0]-b[0]);Listint[]retnewArrayList();for(inti0;im;){intleftintervals[i][0];intrightintervals[i][1];intji1;for(;jm;j){intsintervals[j][0];inteintervals[j][1];if(rights){rightMath.max(right,e);}else{break;}}ret.add(newint[]{left,right});ij;}returnret.toArray(newint[0][]);// 不限行, 不限列, 有多少元素全变成数组}}三. 力扣435. 无重叠区间1. 题目解析需要移除区间的最少数量, 就是让求最多的不重叠子区间数量, 用求交集的方法2. 算法原理与上道题很相似, 不同点在于一个让求重叠区间, 这道题是不重叠区间, 并且这里right和e相等时, 不算做重叠3. 代码classSolution{publicinteraseOverlapIntervals(int[][]intervals){Arrays.sort(intervals,(a,b)-a[0]-b[0]);intmintervals.length,ret0;for(inti0;im;){intrightintervals[i][1];intji1;for(;jm;j){intsintervals[j][0];inteintervals[j][1];if(rights){rightMath.min(right,e);ret;}else{break;}}ij;}returnret;}}四. 力扣452. 用最少数量的箭引爆气球1. 题目解析这里要注意, points里面x的值是出于最大值和最小值之间的, 如果直接相减会溢出2. 算法原理这道题画出图翻译成人话之后, 和上道题 无重叠区间 一样, 都是求交集, 只不过这里right e时, 也算作相交3. 代码classSolution{publicintfindMinArrowShots(int[][]points){Arrays.sort(points,(a,b)-{// 这里要注意, points里面x的值是出于最大值和最小值之间的, 如果直接相减会溢出returna[0]b[0]?1:-1;});intmpoints.length,ret0;for(inti0;im;){longrightpoints[i][1];intji1;for(;jm;j){longspoints[j][0];longepoints[j][1];if(rights){rightMath.min(right,e);}else{break;}}ret;ij;}returnret;}}