Day25 OK，今日份的打卡！第二十五天
- 以下是今日份的總結
- 用最少數量的箭引爆氣球
- 無重疊區間
- 劃分字母區間
以下是今日份的總結
- 用最少數量的箭引爆氣球
- 無重疊區間
- 劃分字母區間
今天的題目難度不低，而且非常的有意思，盡量還是寫一些簡潔代碼 ^?_?^
用最少數量的箭引爆氣球
思路：
局部最優：當氣球出現重疊，一起射，所用弓箭最少。
全局最優：把所有氣球射爆所用弓箭最少。
值得注意的是
為了讓氣球盡可能的重疊，需要對數組進行排序。
如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。
static bool cmp(vector<int>& a, vector<int>& b) {if (a[0] == b[0])return a[1] < b[1];return a[0] < b[0];}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;}
無重疊區間
思路：
按照右邊界排序，從左向右記錄非交叉區間的個數。最后用區間總數減去非交叉區間的個數就是需要移除的區間個數了
值得注意的是
static bool cmp(vector<int>& a, 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;}
劃分字母區間
思路：
統計每一個字符最后出現的位置
從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點
值得注意的是
找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了
vector<int> partitionLabels(string s) {int pos[26] = {0};for (int i = 0; i < s.size(); i++) { // 統計每一個字符最后出現的位置pos[s[i] - 'a'] = i;}vector<int> result;int left = 0;int right = 0;for (int i = 0; i < s.size(); i++) {right = max(right, pos[s[i] - 'a']); // 找到字符出現的最遠邊界if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
寫在最后
----OK，今日份的博客就寫到這里，這一期的貪心算法好難想，明天繼續加油！！！
—還沒看下期的題，但是我的棧還有一節沒寫；
–追上時間進度了嗎？如追，從欠兩天變成欠一天！！（笑
-被討厭就是自由的證明。
