35. 无重叠区间

题目

解法

1. 更新区间，只保留最小区间，局部最优，推到最优

class Solution {
public:static bool cmp(vector<int> a, vector<int> b) {return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int result = 0;for (int i = 1; i < intervals.size(); i++) {if(intervals[i][0] < intervals[i-1][1]) {result++;intervals[i][1] = min(intervals[i][1], intervals[i-1][1]); // 更新区间，只保留最小区间，局部最优，推到最优}}return result;}
};

763. 划分字母区间

题目

解法

1. 先记录后分割

class Solution {
public:vector<int> partitionLabels(string s) {// 标记每个字母最后出现的位置int Hash[26] = {0};for (int i = 0; i < s.size(); i++) {Hash[s[i] - 'a'] = i;}// 进行分割int left = 0;int right = 0;vector<int> result;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;}
};

56. 合并区间

题目

解法

1. 按照第一题思路自己写的

class Solution {
public:static bool cmp(vector<int> a, vector<int> b){return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);if (intervals.size() == 1) return intervals;vector<vector<int>> result;vector<int> cur = intervals[0]; // 记录值for (int i = 1; i < intervals.size(); i++) {if(intervals[i][0] > intervals[i-1][1]) {cur[1] = intervals[i-1][1];result.push_back(cur);cur = intervals[i];}else {intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);}}cur[1] = intervals[intervals.size()-1][1];result.push_back(cur);return result;}
};

2.题解:修改重叠区间最大值

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};

感悟

【多学习，才会增加应对不确定未来的信心】算法题，没接触某类题之前一点思路也没有，接触后，面对相似问题，有了思路，并想想，有机会正确解决；