今天主要是要用貪心算法來解決重置區間的問題。
1.leetcode 452.用最少數量的箭引爆氣球
題目鏈接
class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0) return 0;sort(points.begin(),points.end(),cmp);//這里不加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],points[i-1][1]);//更新重置氣球的最小右邊界}}return result;}
};溫馨提示:
注意題目中說的是：滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。那么說明兩個氣球挨在一起不重疊也可以一起射爆，
所以代碼中?if (points[i][0] > points[i - 1][1])?不能是>=
思路總結:
局部最優：當氣球出現重疊，一起射，所用弓箭最少。全局最優：把所有氣球射爆所用弓箭最少。
這道題目貪心的思路很簡單也很直接，就是重復的一起射了，但本題我認為是有難度的。
就算思路都想好了，模擬射氣球的過程，很多同學真的要去模擬了，實時把氣球從數組中移走，這么寫的話就復雜了。
而且尋找重復的氣球，尋找重疊氣球最小右邊界，其實都有代碼技巧。
貪心題目有時候就是這樣，看起來很簡單，思路很直接，但是一寫代碼就感覺賊復雜無從下手。
這里其實是需要代碼功底的，那代碼功底怎么練？
多看多寫多總結！
2.leetcode 435.無重疊區間
題目鏈接
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;//記錄有多少符合條件的,再用總長度減去符合條件的就是需要去除的}
};思路總結:
相信很多同學看到這道題目都冥冥之中感覺要排序，但是究竟是按照右邊界排序，還是按照左邊界排序呢？
其實都可以。主要就是為了讓區間盡可能的重疊。
我來按照右邊界排序，從左向右記錄非交叉區間的個數。最后用區間總數減去非交叉區間的個數就是需要移除的區間個數了。
此時問題就是要求非交叉區間的最大個數。
大家此時會發現如此復雜的一個問題，代碼實現卻這么簡單！
3.leetcode 763.劃分字母區間
題目鏈接
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;}
};思路總結:
一想到分割字符串就想到了回溯，但本題其實不用回溯去暴力搜索。
題目要求同一字母最多出現在一個片段中，那么如何把同一個字母的都圈在同一個區間里呢？
如果沒有接觸過這種題目的話，還挺有難度的。
在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現過所有字母，最遠也就到這個邊界了。
可以分為如下兩步：
統計每一個字符最后出現的位置
從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點
這道題目leetcode標記為貪心算法，說實話，我沒有感受到貪心，找不出局部最優推出全局最優的過程。就是用最遠出現距離模擬了圈字符的行為。
但這道題目的思路是很巧妙的，所以有必要介紹給大家做一做，感受一下。
