本文主要是介绍算法刷题记录 Day31，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法刷题记录 Day31
Date: 2024.03.27
lc 56. 合并区间
class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b){if(a[0] != b[0])return a[0] < b[0];elsereturn a[1] > b[1];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> res;// 1.遍历过程中，若遇到start小于上一个的end，则合并。start不变，end变为两者的最大值。int start = intervals[0][0];int end = intervals[0][1];for(int i=1; i<intervals.size(); i++){if(intervals[i][0] <= end){end = max(intervals[i][1], end);}else{res.push_back(vector<int>{start, end});start = intervals[i][0];end = intervals[i][1];}}res.push_back(vector<int>{start, end}); // 补上最后一个区间return res;}
};
- 划分字母区间
class Solution {
public:vector<int> partitionLabels(string s) {vector<int> res;int n = s.size();vector<int> dict(26, -1); //保存s中各字符出现的最后索引.不存在则为-1.for(int i=0; i<n; i++){dict[s[i] - 'a'] = i;}// 根据每个字符的最后出现索引，判断所需的长度int start = 0;int end = 0;int before_end = 0;while(end < s.size()){int max_next_end = INT_MIN;for(int i=before_end; i<=end; i++){max_next_end = max(max_next_end, dict[s[i] - 'a']);}if(end == max_next_end){ //一轮迭代后end不变，则该长度符合要求res.push_back(end-start+1);start = end+1;end = start;before_end = start;}else{before_end = end;end = max_next_end;}}return res;}
};
- 无重叠区间
class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b){if(a[0] != b[0])return a[0] < b[0];else{return a[1] < b[1];}}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);// int cur_start = intervals[0][0];int cur_end = intervals[0][1];int cut_nums = 0;for(int i=1; i<intervals.size(); i++){if(intervals[i][0] < cur_end){if(intervals[i][1] < cur_end){ //如果是真子集，则舍去大的，保留小的cur_end = intervals[i][1];}cut_nums++;}else{cur_end = intervals[i][1];}}return cut_nums;}
};
这篇关于算法刷题记录 Day31的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
