算法奇妙屋(四十二)-贪心算法学习之路 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){intret=0;while(target>startValue){if(target%2==1){target++;ret++;}else{target/=2;ret++;}}returnret+startValue-target;}}二. 力扣56. 合并区间
1. 题目解析
题目简单易懂, 就是让求并集
2. 算法原理
3. 代码
classSolution{publicint[][]merge(int[][]intervals){intm=intervals.length,n=2;Arrays.sort(intervals,(a,b)->a[0]-b[0]);List<int[]>ret=newArrayList<>();for(inti=0;i<m;){intleft=intervals[i][0];intright=intervals[i][1];intj=i+1;for(;j<m;j++){ints=intervals[j][0];inte=intervals[j][1];if(right>=s){right=Math.max(right,e);}else{break;}}ret.add(newint[]{left,right});i=j;}returnret.toArray(newint[0][]);// 不限行, 不限列, 有多少元素全变成数组}}三. 力扣435. 无重叠区间
1. 题目解析
需要移除区间的最少数量, 就是让求最多的不重叠子区间数量, 用求交集的方法
2. 算法原理
与上道题很相似, 不同点在于一个让求重叠区间, 这道题是不重叠区间, 并且这里right和e相等时, 不算做重叠
3. 代码
classSolution{publicinteraseOverlapIntervals(int[][]intervals){Arrays.sort(intervals,(a,b)->a[0]-b[0]);intm=intervals.length,ret=0;for(inti=0;i<m;){intright=intervals[i][1];intj=i+1;for(;j<m;j++){ints=intervals[j][0];inte=intervals[j][1];if(right>s){right=Math.min(right,e);ret++;}else{break;}}i=j;}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;});intm=points.length,ret=0;for(inti=0;i<m;){longright=points[i][1];intj=i+1;for(;j<m;j++){longs=points[j][0];longe=points[j][1];if(right>=s){right=Math.min(right,e);}else{break;}}ret++;i=j;}returnret;}}