今日總結

用最少數量的箭引爆氣球

題目鏈接：452. 用最少數量的箭引爆氣球 - 力扣（LeetCode）

代碼隨想錄

整體思路：

? ? ? ? 1、統一度量 ：

? ? ? ? ? ? ? ? 將所有區間按照左端點進行排序：

? ? ? ? ? ? ? ? ? ? ? ? 用到了二維的sort，在類中需要定義靜態成員函數cmp，從小到大排列

? ? ? ? 2、進行區間合并

? ? ? ? ? ? ? ? （1）如果沒有氣球，就是0箭

? ? ? ? ? ? ? ? （2）如果有氣球，至少1箭

? ? ? ? ? ? ? ? （3）按照排序從小到大遍歷，比較當前位置的左端點是否在前邊位置的范圍內（<=前邊位置的最小右端點）

? ? ? ? ? ? ? ? ? ? ? ? 如果在，就不加箭，只更新最小的右端點（前邊的最小右與當前的右 比較取最小）

? ? ? ? ? ? ? ? ? ? ? ? 如果不在，就加箭，更新右端點為當前氣球的右端點

整體代碼：

class Solution {
public:static bool cmp(const vector<int>&a,vector<int>&b){if(a[0]<b[0])return true;else return false;}int findMinArrowShots(vector<vector<int>>& points) {//進行排序：按照起始坐標排序：//在類中，兩個維度，使用sort需要自己定義靜態比較函數cmpsort(points.begin(),points.end(),cmp);//進行比較：//1、如果沒有氣球就是0支箭if(points.size()==0)return 0;//2、要是有氣球至少一支箭int sum =1;//定義右邊端點位置int res = points[0][1];//有氣球需要判斷后邊的箭的起點是不是在前邊的范圍的之內，在就不需要加箭，更新右邊的端點位置為最小 for(int i=1;i<points.size();i++){if(points[i][0]<=res){//不加箭，只更新右端點res = min(res,points[i][1]);}else{//超過了右端點，//加一支箭sum ++;//更新右端點res = points[i][1];}}return sum;}
};

無重疊區間

題目鏈接：435. 無重疊區間 - 力扣（LeetCode）

代碼隨想錄

整體思路：

? ? ? ? 1、統一度量：

? ? ? ? ? ? ? ? 將所有的區間按照第一個維度從小到大排列，如果第一個維度相同，按照第二維度小的排在前邊(第二維度大的一定是一個舍掉的區間)

? ? ? ? 2、進行區間遍歷，舍棄重疊區間

? ? ? ? ? ? ? ? 如果當前區間的左端點在上一個區間的范圍內（小于右端點，沒有等）說明這兩個區間重疊了：所以舍棄數量+1，更新右端點為小的右端點，相當于舍掉了右端點大的區間

? ? ? ? ? ? ? ? 如果當前區間的左端點不在上一個區間的范圍內，說明沒有重疊，舍棄數量不變，更新右端點為當前區間的右端點

整體代碼：

class Solution {
public://移除最小數量的區間，所以區間所占位置越小越好：//[1,3],[2,3]這種，舍掉[1,3],因為戰空間大， 可能存在[0,2]//1、對所有區間，按照第一維度進行從小到大排序，第一維度相同，排列第二維度小的在前邊（大的一定是舍棄的）//2、從左到右進行遍歷，如果當前的區間的左端點在前一個區間內，說明重疊了，比較兩者的右端點，誰的右端點小，要誰，舍棄數量+1//如果當前區間的左端點不在前一個區間內，說明沒有重疊，記錄右端點位置便于下一個區間的比較,舍棄數量不變//定義sort的靜態比較函數static bool cmp(const vector<int>&a,const vector<int>&b){if(a[0]<b[0])//比較第一維度return true;else if(a[0]<=b[0]){if(a[1]<b[1])return true;else return false;}else return false;}int eraseOverlapIntervals(vector<vector<int>>& intervals) {//排序sort(intervals.begin(),intervals.end(),cmp);//如果沒有區間if(intervals.size()==0)return 0;//如果有區間int rm =0;//如果只有一個區間，不需要舍棄//定義第一個區間的右端點 ，便于后邊進行比較int right_point = intervals[0][1];//遍歷，從第二個區間開始for(int i=1;i<intervals.size();i++){//判斷當前區間的起點是否在上一個區間中,注意如果在在一個點上是不重疊的，所以沒有等號if(intervals[i][0]<right_point){//此時說明當前區間與上一個區間有重疊，需要舍棄加1，同時更新小的右區間，相當于刪掉了右端點大的區間rm ++;right_point = min(right_point,intervals[i][1]);}//如果沒有重疊else{//不需要舍棄區間，rm不變化//更新右端點為當前區間的右端點right_point = intervals[i][1];}}return rm;}
};

劃分字母區間

題目鏈接：763. 劃分字母區間 - 力扣（LeetCode）

代碼隨想錄

整體思路：

unordered_map記錄：

? ? ? ? 1、插入元素可以使用insert、下標操作符[]賦值

? ? ? ? ? ? ? ? （1）insert插入限制：

? ? ? ? ? ? ? ? ? ? ? ? mmap.insert({1,2})如果鍵1不存在插入{1，2};但是鍵 1存在就不會重復插入了

? ? ? ? ? ? ? ? （2）[]插入

? ? ? ? ? ? ? ? ? ? ? ? mmap[1]=2,如果鍵1不存在，就插入{1,2}如果鍵1存在，就更新鍵1的value為2

? ? ? ? 2、不能先判斷是否到了長度lengthh，再進行沒有到達長度時加當前段的長度，因為會出現第一個坐標0時，本身就是一段 ，此時卻不能進行額外判斷

? ? ? ? ? ? ? ? 需要先將當前位置加入之后，再判斷當前位置是不是符合寫入要求

? ? ? ? 3、使用unordered_map進行記錄每個元素的最遠位置，之后通過判斷當前元素是不是有更遠的位置，更新最遠的位置，當到達最遠位置時進行記錄，并將距離恢復為0

整體代碼：
?

class Solution {
public://最大的困難在于同一個字母必須出現在同一個片段中，這會導致分段一定是唯一解//所以需要統計每個字母最后出現的位置，只要在這個區間中，沒有其他字母最后出現的位置大于這個字母的最后位置，就可以將這個字母的最后位置當作分段點vector<int> partitionLabels(string s) {//1、統計所有字母的最后出現位置為一個數組,使用unordered_map進行記錄iunordered_map <char,int> mmap;for(int i=0;i<s.size();i++){mmap[s[i]] = i;}//2、遍歷所有元素，記錄當前區間的最遠出現位置，判斷在這個位置范圍內是否存在更遠的位置int lengthh =0;//記錄當前的段的大小int vec=0;//記錄總的分段情況vector<int>res;if(s.size()==0)return {0};for(int i=0;i<s.size();i++){//如果當前沒有到達最遠的位置，就判斷當前需不需要更新最遠位置lengthh = max(mmap[s[i]],lengthh);//同時當前段的大小+1vec++;//判斷當前是否到了最遠位置if(i==lengthh){//到了最遠位置,記錄res.push_back(vec);vec =0;//更新距離為0，進行下一個元素}}return  res;}
};