一、參考資料
無重疊區間
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
劃分字母區間
https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
合并區間
https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
二、LeetCode435. 無重疊區間
https://leetcode.cn/problems/non-overlapping-intervals/description/
給定一個區間的集合 intervals ,其中 intervals[i] = [starti, endi] 。傳回 需要移除區間的最小數量,使剩餘區間互不重疊 。
示例 1:
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]] 輸出: 1 解釋: 移除 [1,3] 後,剩下的區間沒有重疊。
示例 2:
輸入: intervals = [ [1,2], [1,2], [1,2] ] 輸出: 2 解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。
示例 3:
輸入: intervals = [ [1,2], [2,3] ] 輸出: 0 解釋: 你不需要移除任何區間,因為它們已經是無重疊的了。
提示:
1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4
詳細題解看這裡:https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html#%E6%80%9D%E8%B7%AF
我當時的思路是按照左排序做的:
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int res = 0;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
res ++;
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
}
}
return res;
}
};
三、LeetCode763.劃分字母區間
https://leetcode.cn/problems/partition-labels/description/
給你一個字元串 s 。我們要把這個字元串劃分為盡可能多的片段,同一字母最多出現在一個片段中。
注意,劃分結果需要滿足:将所有劃分結果按順序連接配接,得到的字元串仍然是 s 。
傳回一個表示每個字元串片段的長度的清單。
示例 1:
輸入:s = "ababcbacadefegdehijhklij" 輸出:[9,7,8] 解釋: 劃分結果為 "ababcbaca"、"defegde"、"hijhklij" 。 每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 這樣的劃分是錯誤的,因為劃分的片段數較少。
示例 2:
輸入:s = "eccbbbbdec" 輸出:[10]
提示:
1 <= s.length <= 500
s 僅由小寫英文字母組成
可以分為如下兩步:
- 統計每一個字元最後出現的位置
- 從頭周遊字元,并更新字元的最遠出現下标,如果找到字元最遠出現位置下标和目前下标相等了,則找到了分割點
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5yYiRWO1MGZyMGNiJTN2ImMwYDO3cjMhVjYwcTMiVGN18CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
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> res;
int left = 0, right = 0;
for (int i = 0; i < s.size(); i++) {
right = max(right, hash[s[i] - 'a']); // 找到字元出現的最遠邊界
if (i == right) {
res.push_back(right - left + 1);
left = i + 1;
}
}
return res;
}
};
四、LeetCode56. 合并區間
https://leetcode.cn/problems/merge-intervals/description/
以數組 intervals 表示若幹個區間的集合,其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間,并傳回 一個不重疊的區間數組,該數組需恰好覆寫輸入中的所有區間 。
示例 1:
輸入:intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出:[[1,6],[8,10],[15,18]] 解釋:區間 [1,3] 和 [2,6] 重疊, 将它們合并為 [1,6].
示例 2:
輸入:intervals = [[1,4],[4,5]] 輸出:[[1,5]] 解釋:區間 [1,4] 和 [4,5] 可被視為重疊區間。
提示:
1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4
需要注意,隻更新右邊界就可以!!!
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 = 1; 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;
}
};
今日總結:
附加了一道單調棧問題 但是一直沒做出來
https://leetcode.cn/problems/asteroid-collision/