前言
这里记录一下陈菜菜的刷题记录,主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕,一年车企软件开发经验
代码能力:有待提高
常用语言:C++
系列文章目录
第36天 :第八章 贪心算法 part05
`
文章目录
- 前言
- 系列文章目录
- 第36天 :第八章 贪心算法 part05
- 一、今日任务
- 二、详细布置
- 56. 合并区间
- 提示:
- 样例1:
- 思路
- 实战
- 738.单调递增的数字
- 提示:
- 样例1:
- 思路
- 实战
- 总结
一、今日任务
● 56. 合并区间
● 738.单调递增的数字
● 总结
二、详细布置
56. 合并区间
题目链接:力扣56
文章讲解:代码随想录
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
样例1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
思路
这题和昨天重叠区间很像。
实战
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) {
if(intervals.size()<=1)
return intervals;
//vector<int> vec;
vector<vector<int>> result;
int cnt=1;
int left=intervals[0][0];
int end=intervals[0][1];
sort(intervals.begin(),intervals.end(),cmp);
result.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
if(result.back()[1]>=intervals[i][0]){
result.back()[1]=max(result.back()[1],intervals[i][1]);
}
else{
//vec.push_back(left);
//vec.push_back(end);
result.push_back(intervals[i]);
}
}
return result;
}
};
738.单调递增的数字
题目链接:力扣738题链接
文章讲解:图文讲解
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增
提示:
0 <= n <= 109
样例1:
输入: n = 10
输出: 9
思路
这题简单题。
实战
class Solution {
public:
bool increase(int a){
string s=to_string(a);
vector<int> num;
vector<int> n;
for(int i=0;i<s.size();i++){
num.push_back(s[i]-'0');
n.push_back(s[i]-'0');
}
sort(num.begin(),num.end());
for(int i=0;i<s.size();i++){
if(num[i]!=n[i])
return false;
}
return true;
}
int monotoneIncreasingDigits(int n) {
for(int i=n;i>=0;i--){
if(increase(i)){
return i;
break;
}
}
return n;
}
};
总结
今天主要学习了贪心的一系列操作,今天的题目稍简单一点啦,提前打卡,最近要期中考试了,加油,坚持碎片化时间刷题。
加油,坚持打卡的第36天。