【C++贪心】2498. 青蛙过河 II

news/2024/9/19 20:13:48/ 标签: c++, 算法, leetcode, 贪心, 青蛙, 最大, 最小

本文涉及知识点

贪心 优化后不需要二分

LeetCode2498. 青蛙过河 II

给你一个下标从 0 开始的整数数组 stones ,数组中的元素 严格递增 ,表示一条河中石头的位置。青蛙一开始在第一块石头上,它想到达最后一块石头,然后回到第一块石头。同时每块石头 至多 到达 一次。
一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。
更正式的,如果青蛙从 stones[i] 跳到 stones[j] ,跳跃的长度为 |stones[i] - stones[j]| 。一条路径的 代价 是这条路径里的 最大跳跃长度 。
请你返回这只青蛙最小代价 。
示例 1:
在这里插入图片描述

输入:stones = [0,2,5,6,7]
输出:5
解释:上图展示了一条最优路径。
这条路径的代价是 5 ,是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径,我们返回 5 。
示例 2:
在这里插入图片描述

输入:stones = [0,3,9]
输出:9
解释:
青蛙可以直接跳到最后一块石头,然后跳回第一块石头。
在这条路径中,每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。
提示:
2 <= stones.length <= 105
0 <= stones[i] <= 109
stones[0] == 0
stones 中的元素严格递增。

贪心

n = stones.length
性质一:一定存在最优解,所有石头都跳。用决策包容性证明:
假定某最优解,第i块石头没有通过。去程其前面的石头是i1,后面的石头是i2。则将 i 1 → i 2 转成 i 1 → i → i 2 i1 \rightarrow i2 转成i1 \rightarrow i \rightarrow i2 i1i2转成i1ii2仍然是最优解。
性质二:一定存在最优解,除起点和终点外,去程(返程)不经过任意两个连续石头。用决策包容性证明:
不失一般性,假定去程经过: 1 → 2 → 4 返程经过 0 → 3 → 5 1 \rightarrow 2 \rightarrow 4 返程经过0 \rightarrow 3 \rightarrow 5 124返程经过035
改成 0 → 2 → 4 返程经过 1 → 3 → 5 0 \rightarrow 2 \rightarrow 4 返程经过1 \rightarrow 3 \rightarrow 5 024返程经过135也是最优解。
修改前:0能够到达3,说明0能到达2,1也能到达3。
性质三:如果石头超过3个。则一定存在最优解,第2个石头是去程。如果不是,去程和返程经过的石头互换。
同时符合上面三个的性质的最优解:
去程:0 2 4…n-1 返程 n-1 …5 3 1 0
去程枚举起点:如果 i 是 n-1 ,则不跳。 如果 i+2 < n 则跳到 i+2;否则跳到i+1。 除终点外,枚举所有偶数。
返程枚举终点:如果i 是 n-1,不会是终点。如果i+2 < n,则起点是n+2;否则起点是i+1。 除终点外,枚举所有奇数和0。
两者综合:枚举终点外所有的点。

代码

核心代码

class Solution {public:int maxJump(vector<int>& stones) {int ret = 0;for (int i = 0; i + 1 < stones.size(); i++) {ret = max(ret, stones[i + 1] - stones[i]);if (i + 2 < stones.size()) {ret = max(ret, stones[i + 2] - stones[i]);}}return ret;}};

测试

vector<int> stones;TEST_METHOD(TestMethod13){stones = { 0, 2, 5, 6, 7 };auto res = Solution().maxJump(stones);AssertEx(5, res);}TEST_METHOD(TestMethod14){stones = { 0,3,9 };auto res = Solution().maxJump(stones);AssertEx(9, res);}TEST_METHOD(TestMethod15){stones = { 1,2 };auto res = Solution().maxJump(stones);AssertEx(1, res);}};

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。


http://www.ppmy.cn/news/1513824.html

相关文章

Python实现水果忍者(开源)

一、整体介绍&#xff1a; 1.1 前言&#xff1a; 游戏代码基于Python制作经典游戏案例-水果忍者做出一些改动&#xff0c;优化并增加了一些功能。作为自己Python阶段学习的结束作品&#xff0c;文章最后有源码链接。 1.2 Python主要知识&#xff1a; &#xff08;1&#xf…

Springboot 使用 maven-resources-plugin 打包变量替换jar没有打包进去、Jar包没有被使用

问题场景&#xff1a; 最近在使用环境分离&#xff0c;必须用到maven-resources-plugin来替换配置文件变量。遇到了一些问题。 程序写好了需要打包为packge.jar。恰好本地使用了一些jar包&#xff08;如&#xff1a;them.jar&#xff09;作为依赖。jar包路径就在项目根目录的 …

【深度学习】基于Transformers的大模型推理框架

本文旨在介绍基于transformers的decoder-only语言模型的推理框架。与开源推理框架不同的是&#xff1a; 本框架没有利用额外的开源推理仓库&#xff0c;仅基于huggingface&#xff0c;transformers&#xff0c;pytorch等原生工具进行推理&#xff0c;适合新手学习大模型推理流…

聚鼎科技:怎么做装饰画更受大众好评

在当今这个充满创意与个性表达的时代&#xff0c;装饰画不再仅仅是墙面的点缀&#xff0c;它成为了展现屋主品味与生活态度的重要载体。那么&#xff0c;究竟如何才能创作出既符合大众审美又具有独特魅力的装饰画呢? 融合流行元素与个性化设计是关键所在。一方面&#xff0c;通…

振兴杯全国青年职业技能大赛职业技能标准——物联网安装调试员

一、大赛概述 1.1 振兴杯全国青年职业技能大赛简介 振兴杯全国青年职业技能大赛是一项国家级的职业技能竞赛&#xff0c;自2005年首届大赛成功举办以来&#xff0c;已逐渐成为国内规模最大、影响力最广的青年职业技能竞赛之一。这项竞赛旨在推动青年技能人才的培养和发展&…

camx chi 开 log

下面这里是chi log: <settingsSubGroup Name"ChiOverride Settings"> <setting> <Name>Set Log levels</Name> <Help> Bitmask of log levels, bit 0 - error, …

Java面试-基础

1. 面向对象 什么是面向对象 什么是面向对象&#xff1f; 对比面向过程&#xff0c;是两种不同的处理问题的角度 面向过程更注重事情的每一个步骤及顺序&#xff0c;面向对象更注重事情有哪些参与者 &#xff08;对象&#xff09;、及各自需要做什么 封装、继承、多态 2. …

MySQL 数据库管理

在 MySQL 中&#xff0c;数据库管理是非常基础但又至关重要的技能。无论是创建新的数据库、选择当前使用的数据库&#xff0c;还是查看数据库的相关信息&#xff0c;这些操作都是日常数据库管理中不可或缺的一部分。本文将详细介绍 MySQL 数据库管理的基本操作&#xff0c;包括…

【Solidity】代币

ERC20 ERC-20 全称 “Ethereum Request for Comment 20”&#xff0c;是一种标准接口&#xff0c;用于实现代币合约。ERC20 标准定义了一组函数和事件&#xff0c;使得代币可以在不同的应用和平台之间互操作。 ERC20 标准接口定义了一组必须实现的函数和事件&#xff1a; in…

C#收集海康系读码器内容并硬触发IO报警

最近有个需求&#xff0c;需要对几台打码机读码器进行集中防重。 实现目标&#xff1a;1.对条码进行分机台收集追溯 2.发现重复进行触发IO报警 首先使用海康MVS软件对读码器进行设置&#xff0c;通讯设置为TCP服务器&#xff0c;我们软件做客户端 进行数据收集。 然后再收集到…

使用VMware安装银河麒麟桌面操作系统

安装银河麒麟桌面操作系统&#xff08;Kylin Desktop OS&#xff09;在 VMware 虚拟机上是一项相对简单的任务。以下是具体步骤&#xff1a; 1. 准备工作 VMware Workstation 或 VMware Player&#xff1a;确保已在您的计算机上安装了 VMware 。银河麒麟桌面操作系统的ISO镜像…

《Redis核心技术与实战》学习笔记6——数据同步:主从库如何实现数据一致?

文章目录 主从库间如何进行第一次同步&#xff1f;主从级联模式分担全量复制时的主库压力主从库间网络断了怎么办&#xff1f;小结 大家好&#xff0c;我是大白。 如果 Redis 发生了宕机&#xff0c;我们可以使用了 AOF 和 RDB分别通过回放日志和重新读入 RDB 文件的方式恢复数…

API接口安全101:基础概念与最佳实践

文章目录 API定义协议架构风格描述语言 Webservicewsdl介绍复现 SOAPswagger介绍指纹查找利用存在目录复现 HTTPWebpack介绍复现 在当今数字化时代,API接口已成为现代软件架构中不可或缺的组成部分。它们连接着各种应用程序和服务,促进了数据交换和功能集成。然而,随着API的普及…

python创建项目环境及项目打包

目录 创建项目环境conda创建环境常用命令创建项目虚拟环境创建虚拟环境激活虚拟环境安装第三方库 pyinstaller 打包常用参数组合 嵌入式打包下载嵌入式版本的python配置环境无参调用可完善 nuitka打包 创建项目环境 conda创建环境常用命令 conda create -n py310 python3.10.…

Vue 计算属性:优雅地处理数据逻辑

在 Vue.js 中&#xff0c;计算属性&#xff08;Computed Properties&#xff09;是一种非常实用的功能&#xff0c;它允许我们根据组件的响应式依赖进行缓存和派生状态。计算属性可以让我们以声明式的方式编写复杂的逻辑&#xff0c;而不必担心性能问题。 什么是计算属性&…

畅阅读小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;分类管理&#xff0c;充值信息管理&#xff0c;扣费信息管理&#xff0c;书城管理&#xff0c;购买章节管理&#xff0c;章节信息管理&#xff0c;书架管理&#xff0c;系统管理 …

机器学习——XGBoost

目录 一、初识XGBoost 1. 介绍 2. 使用 XGBoost 的方法 &#xff08;1&#xff09;直接使用xgboost库自己的建模流程 &#xff08;2&#xff09;使用xgboost库中的sklearn的API 3. XGBoost的三大板块 4. 提升集成算法 5. 建模流程 二、模型常用参数 1. n_estimators …

C++:模板 II(非类型模板参数,特化,分离编译)

目录 非类型模板参数 模板的特化 函数模板特化 类模板特化 全特化 偏特化 引用特化 指针特化 模板分离编译 非类型模板参数 什么是非类型模板参数&#xff1f; 顾名思义&#xff0c;它的类型形参并不是一个类型&#xff0c;就是用一个常量来作为类模板或函数模板的…

等保测评避坑指南(新手必看)

等保测评&#xff0c;即信息安全等级保护测评&#xff0c;是中国网络安全法规中的一项重要内容。它要求网络运营者根据信息系统的安全保护等级&#xff0c;采取相应的管理措施和技术措施&#xff0c;以确保信息系统安全。对于初次接触等保测评的企业或个人来说&#xff0c;了解…

【HTML】用盒子模型划分网页模块

1、盒子模型 ☞ 所谓的盒子模型在HTML中就是一个盛装 元素内容的容器。 ☞ 每个盒子模型都由元素的内容、宽高、 内边距&#xff08;padding&#xff09;、边框&#xff08;border&#xff09;和外边距 &#xff08;margin&#xff09;组成。 2、< div>标签 3、border…