435.?無重疊區(qū)間
思路：
這道題可以先求出沒有重疊的區(qū)間數(shù)目，然后與總數(shù)目做差就得到了需要去除的數(shù)目。在求沒有重疊的數(shù)目之前可以先將數(shù)組排序，按照右區(qū)間排序螃壤，這樣在遍歷的時(shí)候就可用上一個(gè)元素的右端點(diǎn)與下一個(gè)元素的左端點(diǎn)比較來判斷是否有重疊日麸。
代碼：
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.?劃分字母區(qū)間
思路：
這道題的難點(diǎn)在于如何劃分區(qū)間墩划，可以先將每個(gè)字母出現(xiàn)的最遠(yuǎn)位置記錄下來，在遍歷的過程中不斷更新最遠(yuǎn)距離，如果最遠(yuǎn)距離與正在遍歷的位置相同，則可以劃分為一個(gè)區(qū)間译秦。
代碼：
class Solution {
public:
? ? vector<int> partitionLabels(string s) {
? ? int num[27]={0};
? ? for(int i=0;i<s.size();i++)
? ? {
? ? ? ? num[s[i]-'a']=i;
? ? }
? ? vector<int> res;
? ? int left=0;
? ? int right=0;
? ? for(int i=0;i<s.size();i++)
? ? {
? ? ? ? right=max(right,num[s[i]-'a']);
? ? ? ? if(right==i)
? ? ? ? {
? ? ? ? ? ? res.push_back(right-left+1);
? ? ? ? ? ? left=right+1;
? ? ? ? }
? ? }
? ? return res;
? ? }
};
56.?合并區(qū)間
思路：
這道題的思路和第435題一致雷猪，如果邊界重疊了就繼續(xù)延長(zhǎng)右邊界射沟，直到不重疊為止。
代碼：
class Solution {
public:
? ? static bool cmp (const vector<int>& a, const vector<int>& b) {
? ? ? ? return a[0] < b[0];
? ? }
? ? vector<vector<int>> merge(vector<vector<int>>& intervals) {
? ? ? ? vector<vector<int>> res;
? ? ? ? if(intervals.size()==0)return res;
? ? ? ? sort(intervals.begin(),intervals.end(),cmp);
? ? ? ? res.push_back(intervals[0]);
? ? ? ? for(int i=0;i<intervals.size();i++)
? ? ? ? {
? ? ? ? ? ? if (res.back()[1] >= intervals[i][0]) {
? ? ? ? ? ? ? ? res.back()[1] = max(res.back()[1], intervals[i][1]);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? res.push_back(intervals[i]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
};
