社交网站开发技术岗,莱芜金点子最新消息,wordpress 亲子模板,小说网站开发的看书软件#x1f525;博客介绍#xff1a; 27dCnc
#x1f3a5;系列专栏#xff1a; 数据结构与算法 算法入门 C项目
#x1f3a5; 当前专栏: 数据结构与算法 专题 : 数据结构帮助小白快速入门算法 …
博客介绍 27dCnc
系列专栏 数据结构与算法 算法入门 C项目 当前专栏: 数据结构与算法 专题 : 数据结构帮助小白快速入门算法 ☆*: .. o(≧▽≦)o ..:*☆ ❤️感谢大家点赞收藏⭐评论✍️ 学习目标
今日学习打卡 代码随想录-贪心算法 学习时间
周一至周五晚上 7 点—晚上9点周六上午 9 点-上午 11 点周日下午 3 点-下午 6 点 学习内容
无重叠区间划分字母区间合并区间单调递增的数字 内容详细
无重叠区间
题目考点: 贪心 区间 解题思路 排序,找重叠区间,然后标记排除 我来按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的如图
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),[](const vectorinta,const vectorintb) {return a[0] b[0];});if (intervals.size() 0) return 0;int cnt 0;int end intervals[0][1];for(int i 1; i intervals.size(); i) {if (intervals[i][0] end) end intervals[i][1]; //无重叠情况else {end min(end,intervals[i][1]);cnt; //记录重叠情况}}return cnt;}
};划分字母区间
题目考点: 贪心 在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。 可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点 代码
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint ans;int left 0;int right 0;for (int i 0; i S.size(); i) {right max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) {ans.push_back(right - left 1);left i 1;}}return ans;}
};合并区间
题目考点: 区间 贪心
题解 对区级左右端点的一个端点进行排序, 然后查找重叠区间 这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。
所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。
按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是 class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint ans;sort(intervals.begin(),intervals.end(),[](const vectorinta,const vectorintb) {return a[0] b[0];});for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i-1][1]) {intervals[i][1] max(intervals[i][1], intervals[i-1][1]);intervals[i][0] intervals[i-1][0];} else {ans.push_back({intervals[i-1][0],intervals[i-1][1]});}}ans.push_back({intervals.back()[0], intervals.back()[1]});return ans;}
};单调递增的数字
题目考点: 贪心 数据 解题思路 题目要求小于等于N的最大单调递增的整数那么拿一个两位的数字来举例。
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]–然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。
这一点如果想清楚了这道题就好办了。 此时是从前向后遍历还是从后向前遍历呢
从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。
这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
确定了遍历顺序之后那么此时局部最优就可以推出全局找不出反例试试贪心。
代码
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行int flag strNum.size();for (int i strNum.size() - 1; i 0; i--) {if (strNum[i - 1] strNum[i] ) {flag i;strNum[i - 1]--;}}for (int i flag; i strNum.size(); i) {strNum[i] 9;}return stoi(strNum);}
};学习产出 技术笔记 2 遍 CSDN 技术博客 3 篇 习的 vlog 视频 1 个 重磅消息:
GTP - 4 最新版接入服务他来了 点击链接即可查看详细
GTP - 4 搭建教程
如果此文对你有帮助的话欢迎关注、点赞、⭐收藏、✍️评论支持一下博主~
