当前位置: 首页 > news >正文

贪心系列专题篇三

目录

单调递增的数字

坏了的计算器

合并区间

无重叠区间

用最少数量的箭


声明:接下来主要使用贪心法来解决问题!!!

单调递增的数字

题目

思路

如果我们遍历整个数组,然后对每个数k从[k,0]依次遍历寻找“单调递增”的数字,对于本题数据量最大为10^9,显然是会超时的,下面将介绍一种贪心解法。

把数字转换成字符串,然后从头到尾遍历整个字符串,当遇到后一个字符小于当前一个字符时,把当前字符-1,之后的字符全都修改正字符'9'。如下:

但是这种方法还是有缺陷的,比如下面的这种情况,

因此,我们需要对上面的贪心策略进行修改,修改后的贪心策略如下:

贪心策略

把数字转换成字符串,然后从头到尾遍历整个字符串,当遇到后一个字符小于当前一个字符时,向前寻找和当前字符相等的字符,把与当前字符相等的字符的最左段字符字符-1,之后的字符全都修改正字符'9'。如下:

代码

class Solution {
public:int monotoneIncreasingDigits(int n) {string s=to_string(n);int m=s.size();int i=0;while(i+1<m && s[i]<=s[i+1])i++;if(i+1==m) return n;else{while(i-1>=0 && s[i-1]==s[i])i--;s[i]=s[i]-1;for(i=i+1;i<m;i++)s[i]='9';}return stoi(s);}
};
坏了的计算器

题目

思路

因为可对startValue进行乘2和减1操作,但是要想由startValue变换成target,毫无确定的头绪可言.

贪心策略

采用“正难则反”的思想,我们可以想想如何将target变换成startValue,此时有两种操作,分别为除2和加1,而此时可以分两种情况进行讨论,分别是:

当target<startValue,当target为奇数时,由于startValue为整数,此时只能进行+1操作;

                            当target为偶数时,要想变换成startValue,此时只能进行+1操作,

即当target<startValue时,变换操作次数为startValue-target.

当target>startValue,当target为奇数时,由于startValue为整数,此时只能进行+1操作;

                            当target为偶数时,要想变换成startValue,可进行除2和+1操作混合进行,但是如果混合操作进行的话,要想让target变换成startValue,此时的操作次数是大于只进行除2操作的,因此此时只进行除2操作,

即当target>startValue时,先判断target的奇偶性,进行对应操作,直到target=startValue,或者target<startValue,然后进行target<startValue对应的规则。

代码

class Solution {
public:int brokenCalc(int startValue, int target) {long long ret=0;while(startValue<target){if(target%2==0) target/=2;else target+=1;ret++;}ret+=startValue-target;return ret;}
};
合并区间

题目

思路

首先我们先对集合按区间左端点进行排序,因为如果不排序的话,比较两个区间左端点的大小是需要不断遍历集合的,对集合按区间左端点进行排序后的情况如下:

基准参考区间的左端点记为left,右端点记为right,后一段区间的左端点记为a,右端点记为b。

贪心策略

对于a<=right的区间,需要进行合并,此时需要进行right=max(right,b)的操作即可;

对于a>right的区间, 不需要进行合并, 此时需要进行left=a,right=b和记录已合并区间的操作即可。

但是最后还需要记录最后一个区间。

代码

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {int n=intervals.size();sort(intervals.begin(),intervals.end());vector<vector<int>> ret;int left=intervals[0][0],right=intervals[0][1];for(int i=1;i<n;i++){int a=intervals[i][0],b=intervals[i][1];if(right>=a)right=max(right,b);else{ret.push_back({left,right});left=a,right=b;}}ret.push_back({left,right});return ret;}
};
无重叠区间

题目

思路

首先我们先对集合按区间左端点进行排序,因为如果不排序的话,比较两个区间左端点的大小是需要不断遍历集合的,对集合按区间左端点进行排序后的情况如下:

基准参考区间的左端点记为left,右端点记为right,后一段区间的左端点记为a,右端点记为b。

贪心策略

题目要求保证无重复区间需要删除区间的最少数量,等价于尽可能保留更过数量的区间,使用一个变量ret统计删除区间的数量。

对于a<=right的区间,需要进行删除一个右端点较大的那个区间,此时需要进行right=min(right,b)和ret++的操作即可;

对于a>right的区间, 只需要进行right=b的操作即可。

代码

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int n=intervals.size();sort(intervals.begin(),intervals.end());int ret=0;int right=intervals[0][1];for(int i=1;i<n;i++){int a=intervals[i][0],b=intervals[i][1];if(a<right){ret++;right=min(right,b);}elseright=b;}return ret;}
};
用最少数量的箭引爆气球

题目

思路

首先我们先对集合按区间左端点进行排序,因为如果不排序的话,比较两个区间左端点的大小是需要不断遍历集合的,对集合按区间左端点进行排序后的情况如下:

基准参考区间的左端点记为left,右端点记为right,后一段区间的左端点记为a,右端点记为b。

这道题不同于前两道题的明显之处是前两道题求的是并集,而本道题求的是交集。

即求的是下面第二张图的交集个数,而非第一张图。

使用变量ret记录重叠区间个数。

贪心策略

当a<=right时,进行操作right=min(right,b)即可;

当a>right时,进行操作right=b,ret++即可。

代码

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {int n=points.size();sort(points.begin(),points.end());int ret=0;int right=points[0][1];for(int i=1;i<n;i++){int a=points[i][0],b=points[i][1];if(a<=right)right=min(right,b);elseright=b,ret++;}ret++;return ret;}
};

http://www.lryc.cn/news/409741.html

相关文章:

  • Java中两个集合取差集
  • flask mysql数据迁移
  • Kylin系列(一)入门
  • pmp学习交流组队~
  • 公司常用的监控软件有哪些?2024年六大公司监控软件良心推荐!
  • DNS解析异常--排查验证
  • OpenCV库学习之Canny边缘检测模块
  • Python 教程(七):match...case 模式匹配
  • Python小项目实战:杨辉三角
  • java注解与反射(非常详细, 带有很多样例)
  • 模拟实现短信登录功能 (session 和 Redis 两种代码实例) 带前端演示
  • C# Parallel设置最大并发度
  • 【java】力扣 反转字符串中的单词
  • 科学设计程序员面试内容,破解“八股文”之弊
  • 蓝牙BlueZ验证使用记录
  • 【从0制作自己的ros导航小车:上位机篇】02、ros1多机通讯与坐标变换可视化
  • JumpServer关闭admin mfa验证
  • Kafka知识总结(选举机制+控制器+幂等性)
  • 2024非常全的接口测试面试题及参考答案-软件测试工程师没有碰到算我输!
  • python 写一个年会抽奖的demo
  • C++ OpenCV 实现多张图片叠加 叠加文字
  • 用 apifox cli 命令行运行本地接口出现TypeError:Invalid IP address: undefined
  • PyQt6简易案例代码GUI界面小工具——实现增、删、查、改(练手正合适)
  • JavaScript快速入门指南
  • Esbuild介绍
  • UnityShaderUI编辑器扩展
  • 分布式事务——2PC 代码示例
  • vue实现简易的全局加载动画效果
  • Linux网络工具“瑞士军刀“集合
  • Sentinel隔离、降级、授权规则详解