贪心系列专题篇三
目录
单调递增的数字
坏了的计算器
合并区间
无重叠区间
用最少数量的箭
声明:接下来主要使用贪心法来解决问题!!!
单调递增的数字
题目
思路
如果我们遍历整个数组,然后对每个数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;}
};
相关文章:
贪心系列专题篇三
目录 单调递增的数字 坏了的计算器 合并区间 无重叠区间 用最少数量的箭 声明:接下来主要使用贪心法来解决问题!!! 单调递增的数字 题目 思路 如果我们遍历整个数组,然后对每个数k从[k,0]依次遍历寻找“单调递…...
Java中两个集合取差集
Java中两个集合取差集 说明: 集合A ListA: search archive relation test 集合B ListB: search search-gejunhao archive-gejunhao archive system 需求: 现在要取存在于A但是不存在B中的元素 test 该如何实现 思路: 在Java中,如果你想要从一个集合ÿ…...
flask mysql数据迁移
flask 数据迁移 在Flask中使用数据库迁移,通常我们会结合SQLAlchemy和Alembic来管理数据库的迁移。以下是一个基本的数据迁移流程: 安装Flask-Migrate: pip install Flask-Migrate 配置Flask应用和数据库: from flask import Fla…...
Kylin系列(一)入门
Kylin系列(一)入门 目录 简介Kylin的特点安装与配置 环境要求安装步骤 基本概念 Cube维度与度量 Kylin的基本操作 数据准备Cube设计Cube构建查询与分析 最佳实践常见问题总结 简介 Apache Kylin 是一个开源的分布式分析引擎,提供 SQL 查询接口及多维分析&#x…...
pmp学习交流组队~
首先,来看看什么是PMP PMP指的是项目管理专业人士资格认证。它是由美国项目管理协会(Project Management Institute(PMI)发起的,严格评估项目管理人员知识技能是否具有高品质的资格认证考试。 pmp备考攻略本人推荐的参考资料比较多࿰…...
公司常用的监控软件有哪些?2024年六大公司监控软件良心推荐!
在现代企业管理中,监控软件不仅可以帮助提高员工生产力,还可以确保企业数据的安全和保护。小编分享六款公司监控软件,能够满足不同企业的需求,提升管理效率和信息安全。 一、值得推荐的监控软件 1. 固信软件 固信软件https://ww…...
DNS解析异常--排查验证
目录 1.脚本 2.解析结果 3.脚本详解 1.脚本 for j in {1..100}; do for i in $domain1 $domain2; do echo $i; dig $i $dns服务器1 short; sleep 1; dig $i $dns服务器2 short ; sleep 1; done; sleep 2; done; 2.解析结果 ## 域名的解析实际IP: ## $domain1 $IP1 ## $do…...
OpenCV库学习之Canny边缘检测模块
OpenCV库学习之Canny边缘检测模块 一、简介 Canny边缘检测是OpenCV库中一个非常著名的边缘检测算法模块,由John F. Canny在1986年提出。该算法通过多个步骤来确定图像中的边缘,包括噪声降低、梯度计算、非极大值抑制、双阈值检测和边缘跟踪等。Canny边缘…...
Python 教程(七):match...case 模式匹配
目录 专栏列表前言基本语法match 语句case 语句 模式匹配的类型示例具体值匹配类型匹配序列匹配星号表达式命名变量复杂匹配 模式匹配的优势总结 专栏列表 Python教程(一):环境搭建及PyCharm安装Python 教程(二)&…...
Python小项目实战:杨辉三角
题目要求 编写python程序,实现输入正整数n,输出一个n层的杨辉三角,要求打印显示的时候左右对称 比如,输入7,返回结果如图所示 解决思路 generate_pascals_triangle(n) 函数: 生成一个包含 n 层的杨辉三角。 初始化第…...
java注解与反射(非常详细, 带有很多样例)
下面是详细地讲解 Java 中的注解与反射,并提供了很多的示例来帮助理解。 Java 注解(Annotations) 1. 注解的基本概念 注解(Annotation)是 Java 5 引入的一种用于为代码元素(类、方法、字段、参数等&…...
模拟实现短信登录功能 (session 和 Redis 两种代码实例) 带前端演示
目录 整体流程 发送验证码 短信验证码登录、注册 校验登录状态 基于 session 实现登录 实现发送短信验证码功能 1. 前端发送请求 2. 后端处理请求 3. 演示 实现登录功能 1. 前端发送请求 2. 后端处理请求 校验登录状态 1. 登录拦截器 2. 注册拦截器 3. 登录完整…...
C# Parallel设置最大并发度
背景 以前用Parallel都是直接用,今天在处理pdf时发现不是很快,特别是有时居然卡死了,异常是有处理的,但没有爆出来,不知道问题在哪。 老老实实不用多线程,一个多小时觉得还是太累。 用的话,部…...
【java】力扣 反转字符串中的单词
目录 题目描述题目描述思路代码 题目描述 151.反转字符串中的单词 题目描述 思路 主要是利用快慢指针和字符串的截取 还要了解去掉首尾空格的函数是trim 那s"the sky is blue"举例 这个例子是没有首尾空格的,以防万一,我们不管有没有&#…...
科学设计程序员面试内容,破解“八股文”之弊
“八股文”在实际工作中是助力、阻力还是空谈? 作为现在各类大中小企业面试程序员时的必问内容,“八股文”似乎是很重要的存在。但“八股文”是否能在实际工作中发挥它“敲门砖”应有的作用呢?有IT人士不禁发出疑问:程序员面试考…...
蓝牙BlueZ验证使用记录
最近使用的一款AICSemi AIC8800D8芯片做的WiFiBT二合一模组,该模组WiFi使用SDIO通信,BT使用UART通信,供应商丢了一份驱动,包含了三个目录:aic8800_bsp、aic8800_fdrv和aic8800_btlpm,而蓝牙部分提供了lbh_s…...
【从0制作自己的ros导航小车:上位机篇】02、ros1多机通讯与坐标变换可视化
从0制作自己的ros导航小车 前言一、ros1多机通讯二、rviz可视化小车坐标系 前言 上节课完成了里程计数据与坐标变换发布,但是还没有测试,本节进行测试,测试之前需要知道一件事,上位机也就是开发板一般不做可视化用,因…...
JumpServer关闭admin mfa验证
背景 因为上一次启动了mfa验证,但是没有验证就关机重启,导致再开机输入密码后需要mfa绑定,但是怎么也无法绑定成功,导致无法登录。 故希望通过后台取消mfa的验证 解决方法 1. 进入docker docker exec -it jms_core /bin/bash…...
Kafka知识总结(选举机制+控制器+幂等性)
文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 选举机制 控制器(Broker)选举 控制器就是…...
2024非常全的接口测试面试题及参考答案-软件测试工程师没有碰到算我输!
一、前言 接口测试最近几年被炒的火热了,越来越多的测试同行意识到接口测试的重要性。接口测试为什么会如此重要呢? 主要是平常的功能点点点,大家水平都一样,是个人都能点,面试时候如果问你平常在公司怎么测试的&#…...
python 写一个年会抽奖的demo
使用while 进行循环,进行三轮之后,停止。random.sample() 抽样不重复查询数据 import random name_list [] for i in range(0,100): name_list .append(员工{i}) winnerNum [30,6,3] //每个中奖人数 count 0 while count < 3: choice i…...
C++ OpenCV 实现多张图片叠加 叠加文字
C OpenCV 实现多张图片叠加 叠加文字 在C中使用OpenCV叠加多张图片以及添加文字的基本步骤如下: 加载多张图片。 确定叠加位置。 使用cv::addWeighted叠加图片,可以为叠加的图片添加透明度。 使用cv::putText在图片上添加文字。 显示或保存结果图片…...
用 apifox cli 命令行运行本地接口出现TypeError:Invalid IP address: undefined
用 apifox cli 命令行运行本地接口出现TypeError:Invalid IP address: undefined,客户端运行是通过的但命令行运行会报错 修改端口也是一样报错,地址修改为127.0.0.1会报错connect ECONNREFUSED 127.0.0.1:8080 解决方法:不用localhost&…...
PyQt6简易案例代码GUI界面小工具——实现增、删、查、改(练手正合适)
目录 专栏导读1、库的介绍PyQt6的主要特点包括:使用PyQt6开发应用程序的一般步骤:库的安装 2、设计窗口设计列表视图设计输入框控件与按钮设计布局listView的简单样式增删查改函数 完整代码总结 专栏导读 🌸 欢迎来到Python办公自动化专栏—P…...
JavaScript快速入门指南
JavaScript是一种广泛应用于网页开发的脚本语言,它可以让网页实现动态效果和交互性。无论是前端开发还是全栈开发,JavaScript都是不可或缺的一部分。本文将带你快速入门JavaScript,从基础语法到实际应用,让你快速上手这门强大的语…...
Esbuild介绍
Esbuild是一个由Evan Wallace基于Go语言开发的快速、可扩展的JavaScript和CSS打包器及压缩器。它以其极快的构建速度和高效的性能在众多构建工具中脱颖而出。 一、核心特性 超快的构建速度: Esbuild相比传统的构建工具(如Webpack)在构建速度…...
UnityShaderUI编辑器扩展
前言: 当我们在制作通用Shader的时候,避免不了许多参数混杂在一起,尽管在材质面板已经使用过Header标签来区分,但是较长的Shader参数就会导致冗余,功能块不够简约明了,如图: 对于Shader制作者来…...
分布式事务——2PC 代码示例
一 2PC代码示例 在Java中实现两阶段提交(2PC, Two-Phase Commit)协议通常涉及多个组件,包括事务协调者(Transaction Coordinator)和多个资源管理器(Resource Managers,如数据库)。在…...
vue实现简易的全局加载动画效果
效果展示 思路 封装一个组件,放Img,伪类样式,固定在屏幕fixed 然后App应用这个组件,Z index拉最大,防止用户在加载动画时乱点, v-show绑定loading,该数据可以放vuex还是任一的公共状态管理变…...
Linux网络工具“瑞士军刀“集合
一、背景 平常我们在进行Linux服务器相关运维的时候,总会遇到一些网络相关的问题。我们可以借助这些小巧、功能强悍的工具帮助我们排查问题、解决问题。 下面结合之前的一些使用经验为大家介绍一下一些经典应用场景下,这个网络命令工具如何使用的。例如怎…...
Sentinel隔离、降级、授权规则详解
文章目录 Feign整合Sentinel线程隔离熔断降级授权规则自定义异常结果 上一期教程讲解了 Sentinel 的限流规则: Sentinel限流规则,这一期主要讲述 Sentinel 的 隔离、降级和授权规则 虽然限流可以尽量避免因高并发而引起的服务故障,但服务还…...
C++11 列表初始化与类型声明
目录 0.前言 1.C11介绍 2.统一的列表初始化 2.1{}初始化 2.2initializer_list 2.2.1initializer_list 的基本用法 2.2.2用于类的 initializer_list 构造函数 2.2.3与标准库容器的结合 2.2.4优势与注意事项 3.新声明 3.1auto 3.1.1基本用法 3.1.2优势 3.1.3注意事项 3.2declt…...
缓存策略自定义:Laravel应用性能优化秘籍
缓存策略自定义:Laravel应用性能优化秘籍 在现代Web应用中,缓存是一种提高应用性能和响应速度的有效手段。Laravel框架提供了强大的缓存机制,支持多种缓存驱动,如文件、数据库、Redis等。然而,在某些情况下࿰…...
python连接sqlserver,封装操作
1封装 # 导入Flask类 import pymssql import tracebackclass Mssql(object):# 连接库def base(database):connect pymssql.connect(usersa,password123456,databasef{database},charsetutf8,as_dictTrue)if connect:print("数据库连接成功!")else:print…...
原生PHP/JS自主开发的交友内核框架婚恋交友系统V10
本文来自:婚恋交友系统V10 - 源码1688 应用介绍 原生PHP/JS自主开发的交友内核框架,极高性能、无捆绑、自主权、无流水扣点、独立全开源 01脱单盲盒:脱单盲盒类似于漂流瓶,先将自己《投放》到盲盒中,另一伴有缘将您取…...
如何在Java、Python、GO程序中使用AI人脸识别API接口
AI人脸识别是一种通过面部识别或确认一个人身份的软件。它通过识别和测量图像中的面部特征来工作。面部识别可以识别图像或视频中的人脸,确定两幅图像中的人脸是否属于同一个人,或者在大量现有图像中搜索人脸。 AI人脸识别的优势是什么? 高…...
在vue使用MQTT
在vue中使用MQTT 最近有个需求,需要前端直接链接mqtt,想到后面可能多出使用,就封装成了hooks 中间遇到了一个坑,就是浏览器默认不支持mqtt协议,其借助了webSocket实现的mqtt协议, 而mqtt默认未开启webSocke…...
DNS、网关、IP、DHCP
DNS、网关、IP、DHCP:深入剖析与理解 在计算机网络的世界中,DNS、网关、IP和DHCP是四个至关重要的概念,它们共同构建了互联网的基础架构,确保了数据的准确传输和设备的有效连接。本文将深入剖析这四个概念,帮助读者更…...
vue2 vue3 props 的处理机制
在 Vue 2 中,props 是单向数据流,父组件向子组件传递的 props 默认情况下是不具有响应式特性的。这意味着当父组件的数据发生变化时,如果传递给子组件的 props 发生变化,子组件不会自动更新视图。 具体来说,在 Vue 2 …...
C++第十弹 ---- vector的介绍及使用
目录 前言vector的介绍及使用1. vector的使用1.1 vector的定义1.2 iterator的使用1.3 vector空间增长问题1.4 vector增删查改 2. vector迭代器失效问题(重点) 总结 前言 本文介绍了C中的vector数据结构及其使用方法。 更多好文, 持续关注 ~ 酷酷学!!! 正文开始 vector的介绍…...
ValueError: invalid literal for int() with base 10: ‘a‘
ValueError: invalid literal for int() with base 10: ‘a‘ 目录 ValueError: invalid literal for int() with base 10: ‘a‘ 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰ÿ…...
[C++探索]初始化列表,static成员,友元函数,内部类,匿名对象
💖💖💖欢迎来到我的博客,我是anmory💖💖💖 又和大家见面了 欢迎来到C探索系列 作为一个程序员你不能不掌握的知识 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成本搭建个人网站…...
搭建自己的金融数据源和量化分析平台(二):读取上交所股票列表
我在上交所没发现上交所有像深交所一样的一键下载股票xls文档的按钮,因此上交所的股票列表读取就会比较麻烦。总体思路是查出来所有股票的代码之后根据股票代码逐一发起HTTP请求读取公司英文名、总股本、流通股本等详细信息,这就导致上交所爬虫的网络交互…...
Kafka知识总结(分区机制+压缩机制+拦截器+副本机制)
文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 分区机制 分区策略 分区策略是决定生产者将消息发送到哪个分区的…...
WordPress原创插件:搜索引擎抓取首图seo图片
WordPress原创插件:搜索引擎抓取首图seo图片 插件设置 插件将在网站头部添加适当的meta标签,以便百度等搜索引擎抓取指定的固定图像。 插件下载 https://download.csdn.net/download/huayula/89596527...
Android Framework 之AMS
它管理了系统的四大组件:Activity、Service、ContentProvider、Broadcast。 它除了管理四大组件外,同时也负责管理和调度所有的进程 AMS相关目录结构 AMS代码主要在下面几个目录(AndroidQ上AMS相关部分功能移到了wm下): frameworks/base/core/java/andro…...
AnConda环境配置学习笔记
AnConda环境配置 个人笔记,自己学习使用。 1、软件安装 去官网或者是清华大学镜像下载 2、环境配置 Conda 查看版本:conda --version 更新所有库 conda update --all(千万不要跟新,版本不匹配) matploitlib安装cond…...
架构师的36项修炼 学习笔记
架构师的36项修炼 学习笔记 分布式缓存 缓存特点 1.技术简单 2.性能提升明显 3.应用场景多 缓存数据存储 hash表 缓存的关键指标 命中率 缓存失效方式 超时失效 LLT 实时清除 代理缓存 反向代理缓存 多层反向代理缓存 内容分发网络CDN 通读缓存 包括代理缓存…...
Python | “IndexError: tuple index out of range” 【已解决】
Python | “IndexError: tuple index out of range” 【已解决】 IndexError: tuple index out of range 深度解析与实战指南 在Python编程中,IndexError: tuple index out of range是一个常见的错误,它发生在尝试访问元组(或其他可索引的数…...
Linux上部署easySpider及基本使用
一、安装及简介 默认使用Chrome浏览器。 1、下载压缩包 官网:易采集EasySpider:无代码可视化爬虫/浏览器自动化测试软件 Linux版只适用于Ubuntu 20.04及以上版本、Deepin、Debian及其衍生版本。 (建议使用)下载网址/Github下…...