贪心算法专题（四）

目录

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--, 继续比较.
比较时, 有以下两种方式:

1. 将数字封装成字符串, 依次比较每个位上的值
2. 以 "%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 的奇偶性, 进行分类讨论:

1. target 为奇数时, 只能进行 +1 操作(除法会使数据丢失)
2. 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 算法原理

• 合并区间, 本质: 求并集

解法: 排序 + 贪心

1. 排序: 根据左端点或者右端点进行排序(本题以左端点进行排序), 排完序后, 能够合并的区间, 一定是相邻的.
2. 贪心: 合并 => 求并集, 根据当前区间右端点的值, 以及相邻区间左端点的值, 判断两个区间是否能合并(有没有重叠部分).

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