452. 用最少數量的箭引爆氣球

這道題目我原本的想法是只要當前的氣球半徑范圍在已有的箭頭能夠擊穿的氣球半徑內就可以實現 但是 箭射出去的地方是一個值 而不是一個范圍? 因此有相同的重疊范圍的許多氣球并一定都有相同的值，因此這種方法不可取

這題的主要局部最優就是當氣球出現重疊，一起射，所用弓箭最少。全局最優：把所有氣球射爆所用弓箭最少。然后為了讓氣球盡可能的重疊，需要對數組進行排序。

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。因此重疊區域的氣球一定要找右邊界的最小值，這樣才能確保所有氣球都能同時被射爆。

完整的代碼如下：

class Solution {
private:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1; // points 不為空至少需要一支箭for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {  // 氣球i和氣球i-1不挨著，注意這里不是>=result++; // 需要一支箭}else {  // 氣球i和氣球i-1挨著points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重疊氣球最小右邊界}}return result;}
};

435. 無重疊區間

這道題有了上道題的基礎就很容易做了 主要循環里判斷是否當前元素的左邊界是否小于上一個的右邊界，然后右邊界更新為當前元素和上一個元素最小的右邊界值即可。因為元素的范圍越小重疊的區間的概率就越小。自己的代碼如下：

class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b) {return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() <= 1) return 0;int result = 0;sort(intervals.begin(), intervals.end(), cmp);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i-1][1]) {result++;intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);}}return result;}
};

代碼隨想錄里是按右邊界排序的代碼如下：

class Solution {
public:// 按照區間右邊界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 記錄非交叉區間的個數int end = intervals[0][1]; // 記錄區間分割點for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};

763. 劃分字母區間

這道題我想復雜了，因為我想的是這個字母是否出現過，因此接下來就比較麻煩? 但是我也想過先找出每個字母的最長范圍這樣就方便許多了? 但是覺得這樣的操作比較耗時，但是下面這種還好。

        for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}

在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

• 統計每一個字符最后出現的位置
• 從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點

明白原理之后，代碼并不復雜，如下：

class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i為字符，hash[i]為字符出現的最后位置for (int i = 0; i < S.size(); i++) { // 統計每一個字符最后出現的位置hash[S[i] - 'a'] = i;}vector<int> result;int left = 0;int right = 0;for (int i = 0; i < S.size(); i++) {right = max(right, hash[S[i] - 'a']); // 找到字符出現的最遠邊界if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
};