本文主要是介绍代码随想录算法训练营第36期DAY38,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
DAY38
435无重叠区间
昨晚很快就想出来了,今天相当于二刷。
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[1]<b[1];
- }
- int eraseOverlapIntervals(vector<vector<int>>& intervals) {
- int res=0;
- sort(intervals.begin(),intervals.end(),mycmp);
- int end=intervals[0][1];
- for(int i=1;i<intervals.size();i++){
- if(intervals[i][0]<end){
- res++;
- continue;
- }
- end=intervals[i][1];
- }
- return res;
- }
- };
763划分字母区间
- COZE的解法:记录每个元素的最终位置,如果当前遍历到了元素的最终位置,就将长度加入到结果集中。写得很巧妙,不容易想到:很多变量的使用技巧、算法设计。之后吸收其他优质题解,先自己按着算法思路写一遍:
动手模拟一遍,就掌握该算法了:
- class Solution {
- public:
- vector<int> partitionLabels(string s) {
- vector<int> res;
- vector<int> last(26,0);
- for(int i=0;i<s.size();i++){
- last[s[i]-'a']=max(last[s[i]-'a'],i);
- }
- int j=0,anthor=0;
- for(int i=0;i<s.size();i++){
- j=max(j,last[s[i]-'a']);
- if(i==j){
- res.push_back(j-anthor+1);
- anthor=i+1;
- }
- }
- return res;
- }
- };
- 力扣优质题解,3份,加深记忆
想切割,要有首尾两个指针,确定了结尾指针,就能确定下一个切割的开始指针。
遍历字符串,如果已扫描部分的所有字符,都只出现在已扫描的范围内,即可做切割。
出自力扣博主:笨猪爆破组(https://leetcode.cn/u/xiao_ben_zhu/)
力扣数学描述:出自力扣官方题解:(https://leetcode.cn/u/leetcode-solution/)
- 代码随想录题解
需要额外学习:与区间操作类似的解法:
统计字符串中所有字符的起始和结束位置,记录这些区间,将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠。找到的边界就是答案。
过了,二刷一下:
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[0]<b[0];
- }
- vector<vector<int>> CountHash(string s){
- vector<vector<int>> hash(26,vector<int>(2,INT_MIN));
- vector<vector<int>> hashfilter;
- for(int i=0;i<s.size();i++){
- if(hash[s[i]-'a'][0]==INT_MIN) hash[s[i]-'a'][0]=i;
- hash[s[i]-'a'][1]=i;
- }
- for(int i=0;i<hash.size();i++){
- if(hash[i][0]!=INT_MIN) hashfilter.push_back(hash[i]);
- }
- return hashfilter;
- }
- vector<int> partitionLabels(string s) {
- vector<int> res;
- vector<vector<int>> tmp=CountHash(s);
- sort(tmp.begin(),tmp.end(),mycmp);
- int st=0,ed=tmp[0][1];
- for(int i=1;i<tmp.size();i++)
- {
- if(tmp[i][0]>ed){
- res.push_back(ed-st+1);
- st=tmp[i][0];
- }
- ed=max(ed,tmp[i][1]);
- }
- res.push_back(ed-st+1);
- return res;
- }
- };
56合并区间
模版题,昨天正好复习了ACWING区间合并模版:
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[0]<b[0];
- }
- vector<vector<int>> merge(vector<vector<int>>& intervals) {
- vector<vector<int>> res;
- int st=INT_MIN,ed=INT_MIN;
- sort(intervals.begin(),intervals.end(),mycmp);
- for(int i=0;i<intervals.size();i++){
- //不重叠
- if(ed<intervals[i][0]){
- if(ed!=INT_MIN) res.push_back({st,ed});
- st=intervals[i][0],ed=intervals[i][1];
- }
- //重叠
- else{
- ed=max(intervals[i][1],ed);
- }
- }
- res.push_back({st,ed});
- return res;
- }
- };
这篇关于代码随想录算法训练营第36期DAY38的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!