【贪心算法】(第十篇)
目录
加油站(medium)
题目解析
讲解算法原理
编写代码
单调递增的数字(medium)
题目解析
讲解算法原理
编写代码
加油站(medium)
题目解析
1.题目链接:. - 力扣(LeetCode)
2.题目描述
在⼀条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油
cost[i] 升。你从其中的⼀个加油站出发,开始时油箱为空。
给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路⾏驶⼀周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则保证它是唯⼀的。
⽰例1:
输⼊:gas=[1,2,3,4,5],cost=[3,4,5,1,2]
输出:3
解释:
从3号加油站(索引为3处)出发,可获得4升汽油。此时油箱有=0+4=4升汽油开往4号加油站,此时油箱有4-1+5=8升汽油
开往0号加油站,此时油箱有8-2+1=7升汽油
开往1号加油站,此时油箱有7-3+2=6升汽油
开往2号加油站,此时油箱有6-4+3=5升汽油
开往3号加油站,你需要消耗5升汽油,正好⾜够你返回到3号加油站。因此,3可为起始索引。
⽰例2:
输⼊:gas=[2,3,4],cost=[3,4,3]
输出:-1
解释:
你不能从0号或1号加油站出发,因为没有⾜够的汽油可以让你⾏驶到下⼀个加油站。我们从2号加油站出发,可以获得4升汽油。此时油箱有=0+4=4升汽油
开往0号加油站,此时油箱有4-3+2=3升汽油
开往1号加油站,此时油箱有3-3+3=3升汽油
你⽆法返回2号加油站,因为返程需要消耗4升汽油,但是你的油箱只有3升汽油。因此,⽆论怎样,你都不可能绕环路⾏驶⼀周。
提⽰:
◦ gas.length == n
◦ cost.length == n
◦ 1 <= n <= 10(5)
◦ 0 <= gas[i], cost[i] <= 10(4)
讲解算法原理
解法(暴⼒解法->贪⼼):
暴⼒解法:
a. 依次枚举所有的起点;
b. 从起点开始,模拟⼀遍加油的流程
贪⼼优化:
我们发现,当从 i 位置出发,⾛了 step 步之后,如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点,都不可能环绕⼀圈。
因此我们枚举的下⼀个起点,应该是 i + step + 1 。
编写代码
c++算法代码:
class Solution
{
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; i++) // 依次枚举所有的起点{int rest = 0; // 标记⼀下净收益int step = 0;for( ; step < n; step++) // 枚举向后⾛的步数{int index = (i + step) % n; // 求出⾛ step 步之后的下标rest = rest + gas[index] - cost[index];if(rest < 0) break;}if(rest >= 0) return i;i = i + step; // 优化}return -1;}
};
java算法代码:
class Solution
{public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;for(int i = 0; i < n; i++) // 依次枚举所有的起点 {int rest = 0; // 统计净收益int step = 0;for( ; step < n; step++) // 枚举向后⾛的步数 {int index = (i + step) % n; // ⾛ step 步之后的下标 rest = rest + gas[index] - cost[index];if(rest < 0){break;}}if(rest >= 0){return i;}i = i + step; // 优化}return -1;}
}
单调递增的数字(medium)
题目解析
1.题目链接:. - 力扣(LeetCode)
2.题目描述
当且仅当每个相邻位数上的数字x和y满⾜x<=y时,我们称这个整数是单调递增的。给定⼀个整数n,返回⼩于或等于n的最⼤数字,且数字呈单调递增。
• ⽰例1:
输⼊:n=10
输出:9
• ⽰例2:
输⼊:n=1234
输出:1234
• ⽰例3:
输⼊:n=332
输出:299
• 提⽰:
0<=n<=10^9
讲解算法原理
解法(贪⼼):
a. 为了⽅便处理数中的每⼀位数字,可以先讲整数转换成字符串;b. 从左往右扫描,找到第⼀个递减的位置;
c. 从这个位置向前推,推到相同区域的最左端;d. 该点的值 -1 ,后⾯的所有数统⼀变成 9 。
编写代码
c++算法代码:
class Solution
{
public:int monotoneIncreasingDigits(int n) {string s = to_string(n); // 把数字转化成字符串 int i = 0, m = s.size();// 找第⼀个递减的位置while(i + 1 < m && s[i] <= s[i + 1]) i++;if(i + 1 == m) return n; // 判断⼀下特殊情况 // 回推while(i - 1 >= 0 && s[i] == s[i - 1]) i--;s[i]--;for(int j = i + 1; j < m; j++) s[j] = '9';return stoi(s);}
};
java算法代码:
class Solution
{public int monotoneIncreasingDigits(int n) {// 把数字转化成字符串char[] s = Integer.toString(n).toCharArray();int i = 0, m = s.length;// 找第⼀个递减的位置while(i + 1 < m && s[i] <= s[i + 1]) i++;if(i == m - 1) return n; // 特判⼀下特殊情况// 回退while(i - 1 >= 0 && s[i] == s[i - 1]) i--;s[i]--;for(int j = i + 1; j < m; j++) s[j] = '9';return Integer.parseInt(new String(s));}
}
相关文章:
【贪心算法】(第十篇)
目录 加油站(medium) 题目解析 讲解算法原理 编写代码 单调递增的数字(medium) 题目解析 讲解算法原理 编写代码 加油站(medium) 题目解析 1.题目链接:. - 力扣(LeetCode&a…...
029.爬虫专用浏览器-抓取跨域#document下的内容
一、iframe下的#document是什么 #document 是一个特殊的 HTML 元素,表示 <iframe> 元素内部的文档对象。当你在 HTML 页面中嵌入一个 <iframe> 元素时,浏览器会创建一个新的文档对象来表示 <iframe> 内部的内容。这 个文档对象就是 #…...

SIP 业务举例之 Call Hold(呼叫保持)
目录 1. Call Hold(呼叫保持)简介 2. 信令流程 呼叫保持 呼叫恢复开始 恢复通话完成 3. 本例 Call Hold 建立了几个 Dialog? 博主wx:yuanlai45_csdn 博主qq:2777137742 想要 深入学习 5GC IMS 等通信知识(加入 51学通信),或者想要 cpp 方向修改简历,模拟面试,学习…...

eks节点的网络策略配置机制解析
参考链接 vpc-cni网络策略最佳实践,https://aws.github.io/aws-eks-best-practices/security/docs/network/#additional-resourcesvpc cni网络策略faq,https://github.com/aws/amazon-vpc-cni-k8s/blob/0703d03dec8afb8f83a7ff0c9d5eb5cc3363026e/docs/…...
【C】用c写贪吃蛇
1.输入正确的账号密码及其用户名,登录成功进入贪吃蛇游戏界面, 2.随机生成蛇头★、食物▲的位置(x,y),并使用□打印地图 3.使用w s a d按键,完成蛇头的上下左右移动 4.蛇头碰撞到食物后,吃下食物变成蛇身的一部分●…...

qt QLineEdit详解
一、概述 QLineEdit 是 Qt 框架中用于创建单行文本输入框的类。它非常适合用于接收用户输入,例如用户名、密码或其他简单的文本信息。它提供了许多有用的编辑功能,支持多种输入模式和文本限制,并支持撤销、重做、剪切、粘贴以及拖放等功能。…...
DevEco Studio的使用 习题答案<HarmonyOS第一课>
一、判断题 1. 如果代码中涉及到一些网络、数据库、传感器等功能的开发,均可使用预览器进行预览。 正确(True)错误(False) 错误(False)回答正确 2. module.json5文件中的deviceTypes字段中,配置了phone,tablet,2in1等多种设备类型,才能进行多设备预览。 正确(True)…...

鸿蒙网络编程系列36-固定包头可变包体解决TCP粘包问题
1. TCP数据传输粘包简介 在本系列的第6篇文章《鸿蒙网络编程系列6-TCP数据粘包表现及原因分析》中,我们演示了TCP数据粘包的表现,如图所示: 随后解释了粘包背后的可能原因,并给出了解决TCP传输粘包问题的两种思路,第一…...

【华为路由】OSPF多区域配置
网络拓扑 设备接口地址 设备 端口 IP地址 RTA Loopback 0 1.1.1.1/32 G0/0/0 10.1.1.1/24 RTB Loopback 0 2.2.2.2/32 G0/0/0 10.1.1.2/24 G0/0/1 10.1.2.1/24 RTC Loopback 0 3.3.3.3/32 G0/0/0 10.1.2.2/24 G0/0/1 10.1.3.1/24 RTD Loopback 0 4.4.4…...

【C++初阶】一文讲通C++内存管理
文章目录 1. C/C内存分布2. C语言中动态内存管理方式3. C内存管理方式3. 1 new/delete操作内置类型3. 2 new和delete操作自定义类型 4. new与delete的原理4. 1 operator new与operator delete函数4. 2 内置类型4. 3 自定义类型 5. 定位new表达式(placement-new)6. malloc/free和…...
Vue学习笔记(九、简易计算器)
在这个案例中,我们使用v-model分别双向绑定了n1、n2操作数,op操作选项和result计算结果,同时用绑定了等号按钮事件。 由于是双向绑定,当input和select通过外部输入内容时,vm内部的数值也会改变,所以calcula…...

Maven 不同环境灵活构建
需求: 使用 Maven根据不同的构建环境(如开发、测试、生产)来定义不同的配置,实现灵活的构建管理。 需要Demo项目的可以参考:我的demo项目 一、项目分层 一般的初创项目不会有特别多的配置文件,所以使用 spring.profile…...

第三十篇:TCP连接断开过程,从底层说明白,TCP系列五
上一篇《第二十九篇:图解TCP三次握手,看过不会忘,从底层说清楚,TCP系列四》说了TCP的三次握手,接下来我将讲解TCP四次挥手。 既然有连接就有断开,谈到这里,有的同学可能会想,不就是…...
代码随想录算法训练营第七天| 哈希表理论基础 454.四数相加II 383.赎金信 15.三数之和 18.四数之和
454. 四数相加 II 题目 给定四个包含整数的数组 A, B, C, D,计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。 解题思路 先计算数组 A 和 B 的所有组合和,并存入哈希表 map 中,键为组合和,值为该和出现的次数…...
搜维尔科技:Manus新品发布Metagloves Pro专业版,专为高精度需求的客户打造,尤其是人形机器人产业与人机工效研究使用
manus新品发布Metagloves Pro专业版,专为高精度需求的客户打造,尤其是人形机器人产业与人机工效研究使用 搜维尔科技:manus新品发布Metagloves Pro专业版,专为高精度需求的客户打造,尤其是人形机器人产业与人机工效研究…...

Spring Boot实现的动态化酒店住宿管理系统
1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理酒店客房管理系统的相关信息成为必然。开发…...

数字IC后端实现Innovus |给各种IP子模块添加port buffer和antenna diode万能脚本
我们之前分享过在hierarchical flow后端实现中为了确保顶层flatten时timing signoff和physical signoff看到的情况和模块级看到的情况一致,我们会在模块io port添加io port buffer(主要是timing,antenna一致性)。实际上在芯片级我…...
反向代理服务器---NGINX
1.NGINX NGINX(发音为“engine-x”)是一个开源的高性能HTTP服务器和反向代理服务器。它被广泛用于互联网应用程序的加速、负载均衡和高可用性的配置。NGINX具有低内存消耗、高并发能力和卓越的性能,能够处理大量并发连接和高流量的网络流量。…...
unity3d————场景管理类SceneManager
常用API SceneManager.LoadScene(string sceneName) 加载名为 sceneName 的场景。SceneManager.LoadScene(int sceneBuildIndex) 根据场景在Build设置中的索引加载场景。SceneManager.GetActiveScene() 获取当前活动的场景。SceneManager.GetSceneByName(string name) 根据名称…...

鹅厂面试官:Transformer 为何需要位置编码?
最近这一两周看到不少互联网公司都已经开始秋招发放Offer。 不同以往的是,当前职场环境已不再是那个双向奔赴时代了。求职者在变多,HC 在变少,岗位要求还更高了。 最近,我们又陆续整理了很多大厂的面试题,帮助一些球…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...