目錄

①力扣56. 合并區(qū)間

解析代碼

②力扣435. 無重疊區(qū)間

解析代碼

③力扣452. 用最少數(shù)量的箭引爆氣球

解析代碼

④力扣397. 整數(shù)替換

解析代碼1_遞歸改記憶化搜索

解析代碼2_貪心策略

⑤力扣354. 俄羅斯套娃信封問題

解析代碼1_動態(tài)規(guī)劃（超時）

解析代碼2_重寫排序+貪心+二分

⑥力扣1262. 可被三整除的最大和

解析代碼

⑦力扣1054. 距離相等的條形碼

解析代碼

⑧力扣767. 重構(gòu)字符串

解析代碼

本篇完。

---

①力扣56. 合并區(qū)間

56. 合并區(qū)間

難度 中等

以數(shù)組?intervals?表示若干個區(qū)間的集合，其中單個區(qū)間為?intervals[i] = [starti, endi]?。請你合并所有重疊的區(qū)間，并返回?一個不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間?。

示例 1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例?2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {}
};

---

解析代碼

貪心策略：

1. 先按照區(qū)間的左端點排序：此時會發(fā)現(xiàn)能夠合并的區(qū)間都是連續(xù)的。
2. 然后從左往后，如果可以合并就按照求并集的方式合并區(qū)間，如果不可以合并就把區(qū)間丟到結(jié)果數(shù)組，再往后遍歷。

如何求并集：

由于區(qū)間已經(jīng)按照左端點排過序了，因此當(dāng)兩個區(qū)間合并的時候，合并后的區(qū)間：

• 左端點就是前一個區(qū)間的左端點。
• 右端點就是兩者右端點的最大值。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ret;int left = intervals[0][0], right = intervals[0][1];for(auto& e : intervals){if(e[0] <= right) // 可以合并{right = max(right, e[1]);}else{ret.push_back({left, right});left = e[0], right = e[1];}}ret.push_back({left, right});return ret;}
};

---

②力扣435. 無重疊區(qū)間

435. 無重疊區(qū)間

難度 中等

給定一個區(qū)間的集合?intervals?，其中?intervals[i] = [starti, endi]?。返回?需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊?。

示例 1:

輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。

提示:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4?<= starti?< endi?<= 5 * 10^4

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {}
};

---

解析代碼

貪心策略：

1. 先按照區(qū)間的左端點排序。
2. 當(dāng)兩個區(qū)間重疊的時候，為了能夠在移除某個區(qū)間后，保留更多的區(qū)間，我們應(yīng)該把區(qū)間范圍較大的區(qū)間移除。

如何移除區(qū)間范圍較大的區(qū)間：

由于已經(jīng)按照左端點排序了，因此兩個區(qū)間重疊的時候，我們應(yīng)該保留右端點較小的區(qū)間。

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int ret = 0;int left = intervals[0][0], right = intervals[0][1];for(auto& e : intervals){if(e[0] >= right) // 不重疊{left = e[0], right = e[1];}else // 重疊{++ret;right = min(right, e[1]); // 保留右端點較小的區(qū)間}}return ret - 1; // 從第一個區(qū)間開始比較就刪掉第一個區(qū)間}
};

---

③力扣452. 用最少數(shù)量的箭引爆氣球

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

難度 中等

有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數(shù)數(shù)組?points?，其中points[i] = [xstart, xend]?表示水平直徑在?xstart?和?xend之間的氣球。你不知道氣球的確切 y 坐標(biāo)。

一支弓箭可以沿著 x 軸從不同點?完全垂直?地射出。在坐標(biāo)?x?處射出一支箭，若有一個氣球的直徑的開始和結(jié)束坐標(biāo)為?xstart，xend，?且滿足 ?xstart?≤ x ≤ xend，則該氣球會被?引爆??？梢陨涑龅墓臄?shù)量?沒有限制?。 弓箭一旦被射出之后，可以無限地前進(jìn)。

給你一個數(shù)組?points?，返回引爆所有氣球所必須射出的?最小?弓箭數(shù)?。

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]。
-在x = 11處發(fā)射箭，擊破氣球[10,16]和[7,12]。

示例 2：

輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個氣球需要射出一支箭，總共需要4支箭。

示例 3：

輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：氣球可以用2支箭來爆破:
- 在x = 2處發(fā)射箭，擊破氣球[1,2]和[2,3]。
- 在x = 4處射出箭，擊破氣球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -2^31?<= xstart?< xend?<= 2^31?- 1

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {}
};

---

解析代碼

貪心策略：

1. 先按照區(qū)間的左端點排序：此時會發(fā)現(xiàn)互相重疊的區(qū)間都是連續(xù)的。
2. 這樣在射箭的時候，要發(fā)揮每一支箭最大的作用，應(yīng)該把互相重疊的區(qū)間統(tǒng)一引爆。

如何求互相重疊區(qū)間：

由于我們是按照左端點排序的，因此對于兩個區(qū)間，我們求的是它們的交集：（注意合并區(qū)間用的是并集，求重疊區(qū)間求的是交集）

• 左端點為兩個區(qū)間左端點的最大值，但是左端點不會影響我們的合并結(jié)果，所以可以忽略。
• 右端點為兩個區(qū)間右端點的最小值。

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end());int ret = 1, right = points[0][1];for(auto& e : points){if(e[0] <= right) // 能合并，求交集，一起擊破{// left = max(left, e[0]); // left不影響合并結(jié)果right = min(right, e[1]);}else // 不能合并，繼續(xù)往后遍歷{++ret;// left = e[0]; // left不影響合并結(jié)果right = e[1];}}return ret; // 加上最后的區(qū)間}
};

---

④力扣397. 整數(shù)替換

397. 整數(shù)替換

難度 中等

給定一個正整數(shù)?n?，你可以做如下操作：

1. 如果?n?是偶數(shù)，則用?n / 2替換?n?。
2. 如果?n?是奇數(shù)，則可以用?n + 1或n - 1替換?n?。

返回?n?變?yōu)?1?所需的?最小替換次數(shù)?。

示例 1：

輸入：n = 8
輸出：3
解釋：8 -> 4 -> 2 -> 1

示例 2：

輸入：n = 7
輸出：4
解釋：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

輸入：n = 4
輸出：2

提示：

• 1 <= n <= 2^31 - 1

class Solution {
public:int integerReplacement(int n) {}
};

---

解析代碼1_遞歸改記憶化搜索

????????此題的貪心策略很難想出來，先看看記憶化搜索的方法（記憶化搜索在之前專題已經(jīng)學(xué)過）：用爆搜模擬也可以過，但是加上備忘錄優(yōu)化：

class Solution {unordered_map<int, int> memo;
public:int integerReplacement(int n) {// 時間O(logN) 空間O(logN)return dfs(n);}int dfs(long long n){if(n == 1)return 0;if(memo[n] != 0)return memo[n];if(n % 2 == 0){memo[n] = 1 + dfs(n / 2);return memo[n];}else{memo[n] = 1 + min(dfs(n - 1), dfs(n + 1));return memo[n];}}
};

---

解析代碼2_貪心策略

貪心策略：任何選擇都應(yīng)該讓這個數(shù)盡可能快地變成 1 。

• 對于偶數(shù)：只執(zhí)行除 2 操作。
• 對于奇數(shù)：

1. 當(dāng) n== 1 的時候，不用執(zhí)行任何操作。
2. 當(dāng) n == 3 的時候，變成 1 的最優(yōu)操作數(shù)是 2 。
3. 當(dāng) n > 1 && n % 4?== 1的時候，那么它的二進(jìn)制表示是 ......01 ，最優(yōu)的方式應(yīng)該選擇 -1 ，這樣就可以把末尾的 1 干掉，接下來執(zhí)行除法操作，能夠更快地變成1 。
4. 當(dāng) n > 3 && n % 4 == 3的時候，那么它的二進(jìn)制表示是 ......11 ，最優(yōu)的方式應(yīng)該選擇 +1 ，這樣可以把一堆連續(xù)的 1 轉(zhuǎn)換成 0 ，更快地變成 1 。

class Solution {
public:int integerReplacement(int n){// 時間O(logN) 空間O(1)int ret = 0;while(n != 1){if(n % 2 == 0){n =  n / 2;++ret;}else{ret += 2; // 下面操作都是兩步if(n == 3)break;else if(n % 4 == 1) // ......01n /= 2; // 和減1除2結(jié)果一樣else // ......01n = n / 2 + 1; // 和加1除2結(jié)果一樣，防溢出}}return ret;}
};

---

⑤力扣354. 俄羅斯套娃信封問題

354. 俄羅斯套娃信封問題

難度 困難

給你一個二維整數(shù)數(shù)組?envelopes?，其中?envelopes[i] = [wi, hi]?，表示第?i?個信封的寬度和高度。

當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進(jìn)另一個信封里，如同俄羅斯套娃一樣。

請計算?最多能有多少個?信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。

注意：不允許旋轉(zhuǎn)信封。

示例 1：

輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個數(shù)為 3, 組合為: 
[2,3] => [5,4] => [6,7]。

示例 2：

輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1

提示：

• 1 <= envelopes.length <= 10^5
• envelopes[i].length == 2
• 1 <= wi, hi <= 10^5

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {}
};

---

解析代碼1_動態(tài)規(guī)劃（超時）

????????將數(shù)組按照左端點排序之后，問題就轉(zhuǎn)化成了最長遞增子序列模型，那接下來我們就可以用解決最長遞增子序列的經(jīng)驗，來解決這個問題（會超時，但還是建議敲一下代碼）。

• 狀態(tài)表示：dp[i] 表示：以 i 位置的信封為結(jié)尾的所有套娃序列中，最長的套娃序列的長度。
• 狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] 。
• 初始化：全部初始化為 1 。
• 填表順序：從左往右。
• 返回值：整個 dp 表中的最大值。

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end());int n = envelopes.size(), ret = 1;vector<int> dp(n, 1);for(int i = 1; i < n; ++i){for(int j = 0; j < i; ++j){if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};

---

解析代碼2_重寫排序+貪心+二分

當(dāng)我們把整個信封按照下面的規(guī)則排序之后：

• 左端點不同的時候：按照左端點從小到大排序。
• 左端點相同的時候：按照右端點從大到小排序

? ? ? ? 此時問題就變成了僅考慮信封的右端點，完完全全的變成的最長遞增子序列的模型。那么我們就可以用貪心 + 二分優(yōu)化我們的算法。

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), [&](vector<int>& e1, vector<int>& e2){return e1[0] != e2[0] ? e1[0] < e2[0] : e1[1] > e2[1];});vector<int> ret;ret.push_back(envelopes[0][1]);for(auto& e : envelopes){if(e[1] > ret.back()){ret.push_back(e[1]);}else // 二分找到要放的位置（找大于等于e[1]的左端點）{int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] < e[1])left = mid + 1;elseright = mid;}ret[left] = e[1];}}return ret.size();}
};

---

⑥力扣1262. 可被三整除的最大和

1262. 可被三整除的最大和

難度 中等

給你一個整數(shù)數(shù)組?nums，請你找出并返回能被三整除的元素最大和。

示例 1：

輸入：nums = [3,6,5,1,8]
輸出：18
解釋：選出數(shù)字 3, 6, 1 和 8，它們的和是 18（可被 3 整除的最大和）。

示例 2：

輸入：nums = [4]
輸出：0
解釋：4 不能被 3 整除，所以無法選出數(shù)字，返回 0。

示例 3：

輸入：nums = [1,2,3,4,4]
輸出：12
解釋：選出數(shù)字 1, 3, 4 以及 4，它們的和是 12（可被 3 整除的最大和）。

提示：

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

class Solution {
public:int maxSumDivThree(vector<int>& nums) {}
};

---

解析代碼

正難則反： 可以先把所有的數(shù)累加在一起，然后根據(jù)累加和的結(jié)果，貪心地刪除一些數(shù)。

分類討論：設(shè)累加和為 sum ，用?x 標(biāo)記 %3 == 1 的數(shù)，用 y 標(biāo)記 % 3 == 2 的數(shù)。那么根據(jù) sum 的余數(shù)，可以分為下面三種情況：（求最小的值和次小的值可以直接sort，也可以在求數(shù)組和的時候記錄下來，時間就變?yōu)榱薕（N））。

• sum % 3 == 0 ，此時所有元素的和就是滿足要求的，直接返回。
• sum % 3 == 1，此時數(shù)組中要么存在一個x（x % 3 == 1），要么存在兩個y（y % 3 == 2）。因為我們要的是最大值，所以應(yīng)該選擇 x 中最小的那么數(shù)，記為 x1 ，或者是 y 中最小以及次小的兩個數(shù)，記為 y1, y2 。那么，我們應(yīng)該選擇這兩種情況下的最大值： max(sum - x1, sum - y1 - y2) 。
• sum % 3 == 2，此時數(shù)組中要么存在一個 y（y % 3 == 2），要么存在兩個 x（x % 3 == 1） 。因為我們要的是最大值，所以應(yīng)該選擇 y 中最小的那個數(shù)，記為 y1 ，或者是 x 中最小以及次小的兩個數(shù)，記為 x1, x2 。那么，我們應(yīng)該選擇這兩種情況下的最大值： max(sum - y1, sum - x1 - x2) 。

那么應(yīng)該選擇下面兩種情況下的最大值： max(sum - y1, sum - x1 - x2) ；

class Solution {
public:int maxSumDivThree(vector<int>& nums) {const int INF = 0x3f3f3f3f;int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;for(auto& x : nums){sum += x;if(x % 3 == 1) // 找出x % 3 == 1中x最小的和次小的{if(x < x1)x2 = x1, x1 = x;else if(x < x2) x2 = x;}else if(x % 3 == 2) // 找出x % 3 == 2中x最小的和次小的{if(x < y1)y2 = y1, y1 = x;else if(x < y2)y2 = x;}}if(sum % 3 == 1)sum = max(sum - x1, sum - y1 - y2);else if(sum % 3 == 2)sum = max(sum - y1, sum - x1 - x2);return sum;}
};

---

⑦力扣1054. 距離相等的條形碼

1054. 距離相等的條形碼

難度 中等

在一個倉庫里，有一排條形碼，其中第?i?個條形碼為?barcodes[i]。

請你重新排列這些條形碼，使其中任意兩個相鄰的條形碼不能相等。 你可以返回任何滿足該要求的答案，此題保證存在答案。

示例 1：

輸入：barcodes = [1,1,1,2,2,2]
輸出：[2,1,2,1,2,1]

示例 2：

輸入：barcodes = [1,1,1,1,2,2,3,3]
輸出：[1,3,1,3,2,1,2,1]

提示：

• 1 <= barcodes.length <= 10000
• 1 <= barcodes[i] <= 10000

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {}
};

---

解析代碼

貪心策略：

• 每次處理一批相同的數(shù)字，往 n 個空里面擺放。
• 每次擺放的時候，隔一個格子擺放一個數(shù)。
• 先處理出現(xiàn)次數(shù)最多的那個數(shù)，剩下的數(shù)可任意。此題保證存在答案->出現(xiàn)次數(shù)最多的那個數(shù)不會超過（n + 1）/ 2，下一個數(shù)想相鄰的話只能“填一圈”（不可能）。

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {unordered_map<int, int> hash; // 數(shù)和其出現(xiàn)的次數(shù)int mostVal = 0, maxCount = 0;for(auto& e : barcodes) // 統(tǒng)計每個數(shù)出現(xiàn)的頻次{++hash[e];if(maxCount < hash[e]){maxCount = hash[e];mostVal = e;}}int n = barcodes.size(), index = 0;vector<int> ret(n);for(int i = 0; i < maxCount; ++i) // 先處理出現(xiàn)次數(shù)最多的數(shù){ret[index] = mostVal;index += 2;}hash.erase(mostVal);for(auto& [a, b] : hash) // 處理剩下的數(shù){for(int i = 0; i < b; ++i){if(index >= n)index = 1;ret[index] = a;index += 2;}}return ret;}
};

---

⑧力扣767. 重構(gòu)字符串

767. 重構(gòu)字符串

難度 中等

給定一個字符串?s?，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。

返回?s?的任意可能的重新排列。若不可行，返回空字符串?""?。

示例?1:

輸入: s = "aab"
輸出: "aba"

示例 2:

輸入: s = "aaab"
輸出: ""

提示:

• 1 <= s.length <= 500
• s?只包含小寫字母

class Solution {
public:string reorganizeString(string s) {}
};

---

解析代碼

和力扣1054. 距離相等的條形碼基本一致。

貪心策略：

• 每次處理一批相同的字母，往 n 個空里面擺放。
• 每次擺放的時候，隔一個格子擺放一個字母。
• 先處理出現(xiàn)次數(shù)最多的那個字母，剩下的字母可任意。如果出現(xiàn)次數(shù)最多的那個字母不超過（n + 1）/ 2，則有解，下一個字母想相鄰的話只能“填一圈”（不可能）。

class Solution {
public:string reorganizeString(string s) {int hash[26] = {0};char mostVal = s[0];int maxCount = 0;for(auto& e : s) // 統(tǒng)計每個數(shù)出現(xiàn)的頻次{++hash[e - 'a'];if(maxCount < hash[e - 'a']){maxCount = hash[e - 'a'];mostVal = e;}}int n = s.size(), index = 0;if(maxCount > (n + 1) / 2)return "";string ret(n, ' ');for(int i = 0; i < maxCount; ++i) // 先處理出現(xiàn)次數(shù)最多的數(shù){ret[index] = mostVal;index += 2;}hash[mostVal - 'a'] = 0;for(int i = 0; i < 26; ++i) // 處理剩下的數(shù){for(int j = 0; j < hash[i]; ++j){if(index >= n)index = 1;ret[index] = i + 'a';index += 2;}}return ret;}
};

---

本篇完。

????????此專欄暫時就不更新了，常見的算法的學(xué)了一遍了，先完結(jié)撒花，后面再更新高階數(shù)據(jù)結(jié)構(gòu)圖等內(nèi)容，然后更新力扣的每日一題或者更新一些?？偷念}。