贪心算法专题（四）
目录
1. 单调递增的数字
1.1 算法原理
1.2 算法代码
2. 坏了的计算器
2.1 算法原理
2.2 算法代码
3. 合并区间
3.1 算法原理
3.2 算法代码
4. 无重叠区间
4.1 算法原理
4.2 算法代码
5. 用最少数量的箭引爆气球
5.1 算法原理
5.2 算法代码
1. 单调递增的数字
738. 单调递增的数字 - 力扣（LeetCode）
1.1 算法原理
解法一: 暴力枚举
依次比较每个位上的值, 观察是否递增, 一旦发现不是递增的, 则 num--, 继续比较.
比较时, 有以下两种方式:
- 将数字封装成字符串, 依次比较每个位上的值
- 以 "%10 , /10" 的顺序, 依次比较每个位上的值
解法二: 贪心
- 即从左往右, 找到第一个递减的位置后, 向前推, 定位到相同区域的最左端, 使其减小 1, 后面的位置全部置为 '9'
1.2 算法代码
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] ch = s.toCharArray();int len = ch.length, i = 0;// 找到第一个递减的位置while(i + 1 < len && ch[i + 1] >= ch[i]) i++;// 特殊情况 => 本来就是递增的if(i == len - 1) return n;// 从这个位置向前推, 找到相同区域的最左端while(i - 1 >= 0 && ch[i - 1] == ch[i]) i--;ch[i]--;for(int j = i + 1; j < len; j++) ch[j] = '9';//while(s.charAt(0) == '0') s = s.substring(1, s.length());// parseInt 方法自动屏蔽掉最左端的 0return Integer.parseInt(new String(ch));}/*** 暴力枚举 => 通过字符串比较* @param n* @return*/public int monotoneIncreasingDigits1(int n) {String s = String.valueOf(n);char[] ch = s.toCharArray();int len = ch.length;for(int i = 0; i < len; i++) {if(i + 1 < len && ch[i] > ch[i + 1]) {int num = Integer.parseInt(s) - 1;s = String.valueOf(num);ch = s.toCharArray();len = ch.length;i = -1;}}return Integer.parseInt(s);}
}2. 坏了的计算器
991. 坏了的计算器 - 力扣（LeetCode）
2.1 算法原理
如果要将 start => target, 需要考虑什么时候 -1, 什么时候 *2, 在这两个操作间选出最优的方案, 但是这样处理是很麻烦的. 所以, 我们采用正难则反的思想, target => start, 此时只有 +1 和 /2 两个操作:
这里, 我们需要根据 target 的数值, 进行分类讨论:
- 当 target <= start 时, 只有 +1 可以到达, return start - target;
接着, 根据 target 的奇偶性, 进行分类讨论:
- target 为奇数时, 只能进行 +1 操作(除法会使数据丢失)
- target 为偶数时, 进行 /2 操作(贪心: /2 操作优于 +1 操作)
当 target 为偶数时, 此时使用了贪心策略: /2 优于 +1, 证明如下:
2.2 算法代码
class Solution {public int brokenCalc(int startValue, int target) {// 正难则反: target => startValue, /2 或者 +1int ret = 0;while(target != startValue) {if(target <= startValue) return ret + startValue - target;if(target % 2 != 0) target += 1;// 奇数时, 只能 +else target /= 2;// 偶数时: 贪心: / 优于 +ret++;}return ret;}
}3. 合并区间
56. 合并区间 - 力扣（LeetCode）
3.1 算法原理
- 合并区间, 本质: 求并集
解法: 排序 + 贪心
- 排序: 根据左端点或者右端点进行排序(本题以左端点进行排序), 排完序后, 能够合并的区间, 一定是相邻的.
- 贪心: 合并 => 求并集, 根据当前区间右端点的值, 以及相邻区间左端点的值, 判断两个区间是否能合并(有没有重叠部分).
3.2 算法代码
class Solution {public int[][] merge(int[][] intervals) {List<int[]> list = new ArrayList<>();// 1. 排序(左端点)Arrays.sort(intervals, (a, b) -> a[0] - b[0]);int left = intervals[0][0], right = intervals[0][1], n = intervals.length;for (int i = 1; i < n; i++) {if (intervals[i][0] <= right) { // 有重叠部分 => 可以合并, 求并集right = Math.max(right, intervals[i][1]);} else { // 不能合并 => 加入结果中list.add(new int[]{left, right});left = intervals[i][0];right = intervals[i][1];}}// 此时, 最后一个区间还没有加入结果中list.add(new int[]{left, right});// int[][] ret = new int[list.size()][2];// for(int i = 0; i < list.size(); i++) {// int j = 0;// for(int x : list.get(i)) ret[i][j++] = x;// }// toArray: 集合转化为数组// 参数: new int[0][] => 生成的数值不限行, 不限列, 有多少放多少return list.toArray(new int[0][]);}
}4. 无重叠区间
435. 无重叠区间 - 力扣（LeetCode）
4.1 算法原理
本题的核心思想和上一题其实是一致的.
解法: 排序 + 贪心
- 排序: 根据左端点进行排序
排序后, 如果相邻的两个区间没有重叠, 那么不需要移除; 如果有重叠, 则必须移除一个!!
(注意, 本题与上题不同, 两端点相同时, 视为无重叠)
- 贪心: 移除区间较大的那一个, 保留区间较小的那一个(根据两区间右端点的大小进行判断)
4.2 算法代码
class Solution {public int eraseOverlapIntervals(int[][] intervals) {// 1. 排序(左端点)Arrays.sort(intervals, (a, b) -> a[0] - b[0]);int ret = 0, right = intervals[0][1];// 2. 移除区间for(int i = 1; i < intervals.length; i++) {int a = intervals[i][0], b = intervals[i][1];if(a < right) {// 有重叠区间, 舍弃一个// 贪心 => 保留小区间, 舍弃大区间right = Math.min(right, b);ret++;}else {// 无重叠区间, 更新 rightright = b;}}return ret;}
}5. 用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
5.1 算法原理
解法: 排序 + 贪心
- 排序: 对左端点进行排序 => 互相重叠的区间是连续的
- 贪心: 使用最少数量的箭, 即找到互相重叠区间的数量(求交集)
5.2 算法代码
class Solution {public int findMinArrowShots(int[][] points) {// 排序(左端点)Arrays.sort(points, (a, b) -> a[0] > b[0] ? 1 : -1);int ret = 0, right = points[0][1];int n = points.length;// 求出互相重叠区间的数量for(int i = 1; i < n; i++) {int a = points[i][0], b = points[i][1];if(a <= right) {// 有重叠right = Math.min(right, b);}else {// 无重叠ret++;right = b;}}return ret + 1;}
}END