目錄

1. 單調(diào)遞增的數(shù)字

1.1 算法原理?

1.2 算法代碼

2. 壞了的計算器

2.1 算法原理

2.2 算法代碼

3. 合并區(qū)間

3.1 算法原理

3.2 算法代碼

4. 無重疊區(qū)間

4.1 算法原理

4.2 算法代碼

5. 用最少數(shù)量的箭引爆氣球

5.1 算法原理

?5.2 算法代碼

---

1. 單調(diào)遞增的數(shù)字

738. 單調(diào)遞增的數(shù)字 - 力扣（LeetCode）

1.1 算法原理?

解法一: 暴力枚舉

依次比較每個位上的值, 觀察是否遞增, 一旦發(fā)現(xiàn)不是遞增的, 則 num--, 繼續(xù)比較.
比較時, 有以下兩種方式:

1. 將數(shù)字封裝成字符串, 依次比較每個位上的值
2. 以 "%10 , /10" 的順序, 依次比較每個位上的值

解法二: 貪心

• 即從左往右, 找到第一個遞減的位置后, 向前推, 定位到相同區(qū)域的最左端,?使其減小 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;// 從這個位置向前推, 找到相同區(qū)域的最左端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, 在這兩個操作間選出最優(yōu)的方案, 但是這樣處理是很麻煩的. 所以, 我們采用正難則反的思想, target => start, 此時只有 +1 和 /2 兩個操作:

這里, 我們需要根據(jù)?target 的數(shù)值, 進(jìn)行分類討論:

• 當(dāng) target <= start 時, 只有 +1 可以到達(dá), return start - target;

接著, 根據(jù) target 的奇偶性, 進(jìn)行分類討論:

1. target 為奇數(shù)時, 只能進(jìn)行 +1 操作(除法會使數(shù)據(jù)丟失)
2. target 為偶數(shù)時, 進(jìn)行 /2 操作(貪心: /2 操作優(yōu)于 +1 操作)

當(dāng) target 為偶數(shù)時, 此時使用了貪心策略: /2 優(yōu)于 +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;// 奇數(shù)時, 只能 +else target /= 2;// 偶數(shù)時: 貪心: / 優(yōu)于 +ret++;}return ret;}
}

---

3. 合并區(qū)間

56. 合并區(qū)間 - 力扣（LeetCode）

3.1 算法原理

• 合并區(qū)間, 本質(zhì): 求并集

解法: 排序 + 貪心

1. 排序: 根據(jù)左端點或者右端點進(jìn)行排序(本題以左端點進(jìn)行排序), 排完序后, 能夠合并的區(qū)間, 一定是相鄰的.
2. 貪心: 合并 => 求并集, 根據(jù)當(dāng)前區(qū)間右端點的值, 以及相鄰區(qū)間左端點的值,?判斷兩個區(qū)間是否能合并(有沒有重疊部分).

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 { // 不能合并 => 加入結(jié)果中l(wèi)ist.add(new int[]{left, right});left = intervals[i][0];right = intervals[i][1];}}// 此時, 最后一個區(qū)間還沒有加入結(jié)果中l(wèi)ist.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: 集合轉(zhuǎn)化為數(shù)組// 參數(shù): new int[0][] => 生成的數(shù)值不限行, 不限列, 有多少放多少return list.toArray(new int[0][]);}
}

---

4. 無重疊區(qū)間

435. 無重疊區(qū)間 - 力扣（LeetCode）

4.1 算法原理

本題的核心思想和上一題其實是一致的.
?解法: 排序 + 貪心

• 排序: 根據(jù)左端點進(jìn)行排序

排序后, 如果相鄰的兩個區(qū)間沒有重疊, 那么不需要移除; 如果有重疊, 則必須移除一個!!
(注意, 本題與上題不同, 兩端點相同時, 視為無重疊)

• 貪心: 移除區(qū)間較大的那一個, 保留區(qū)間較小的那一個(根據(jù)兩區(qū)間右端點的大小進(jìn)行判斷)

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. 移除區(qū)間for(int i = 1; i < intervals.length; i++) {int a = intervals[i][0], b = intervals[i][1];if(a < right) {// 有重疊區(qū)間, 舍棄一個// 貪心 => 保留小區(qū)間, 舍棄大區(qū)間right = Math.min(right, b);ret++;}else {// 無重疊區(qū)間, 更新 rightright = b;}}return ret;}
}

---

5. 用最少數(shù)量的箭引爆氣球

452. 用最少數(shù)量的箭引爆氣球 - 力扣（LeetCode）

5.1 算法原理

解法: 排序 + 貪心

• 排序: 對左端點進(jìn)行排序 => 互相重疊的區(qū)間是連續(xù)的
• 貪心: 使用最少數(shù)量的箭, 即找到互相重疊區(qū)間的數(shù)量(求交集)

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;// 求出互相重疊區(qū)間的數(shù)量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