【数据结构和算法】找到最高海拔
其他系列文章导航
Java基础合集
数据结构与算法合集设计模式合集
多线程合集
分布式合集
ES合集
文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 前缀和的解题模板
2.1.1 最长递增子序列长度
2.1.2 寻找数组中第 k 大的元素
2.1.3 最长公共子序列长度
2.1.4 寻找数组中第 k 小的元素
2.2 方法一:前缀和(差分数组)
三、代码
3.2 方法一:前缀和(差分数组)
四、复杂度分析
4.2 方法一:前缀和(差分数组)
前言
这是力扣的 1732 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。
这是一道非常经典的前缀和问题,虽然看似简单,但它却能让你深入理解前缀和的特点。
一、题目描述
有一个自行车手打算进行一场公路骑行,这条路线总共由 n + 1
个不同海拔的点组成。自行车手从海拔为 0
的点 0
开始骑行。
给你一个长度为 n
的整数数组 gain
,其中 gain[i]
是点 i
和点 i + 1
的 净海拔高度差(0 <= i < n
)。请你返回 最高点的海拔 。
示例 1:
输入:gain = [-5,1,5,0,-7] 输出:1 解释:海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
示例 2:
输入:gain = [-4,-3,-2,-1,4,3,2] 输出:0 解释:海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。
提示:
n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100
二、题解
2.1 前缀和的解题模板
前缀和算法是一种在处理数组或链表问题时常用的技巧,它可以有效地减少重复计算,提高算法的效率。下面是一些常见的使用前缀和算法的题目以及解题思路:
2.1.1 最长递增子序列长度
题目描述:给定一个无序数组,求最长递增子序列的长度。
解题思路:可以使用前缀和和单调栈来解决这个问题。首先,遍历数组,计算出前缀和。然后,使用单调栈记录当前递增子序列的起始位置。遍历数组时,如果当前元素大于前缀和,说明可以扩展当前递增子序列,将当前位置入栈。如果当前元素小于等于前缀和,说明当前递增子序列已经结束,弹出栈顶元素。最后,栈中剩余的元素即为最长递增子序列的起始位置,计算长度即可。
2.1.2 寻找数组中第 k 大的元素
题目描述:给定一个无序数组和一个整数k,找到数组中第k大的元素。
解题思路:可以使用前缀和和快速选择算法来解决这个问题。首先,计算出数组的前缀和。然后,使用快速选择算法在数组中找到第k小的元素。具体实现中,每次选择一个枢轴元素,将数组分成两部分,小于枢轴的元素和大于枢轴的元素。如果枢轴左边的元素个数小于k,则在左边的子数组中继续查找;如果枢轴左边的元素个数大于等于k,则在右边的子数组中继续查找。最后,当找到第k小的元素时,返回该元素即可。
2.1.3 最长公共子序列长度
题目描述:给定两个字符串,求最长公共子序列的长度。
解题思路:可以使用动态规划算法来解决这个问题。如果字符串长度分别为m和n,则可以定义一个二维数组dp[m+1][n+1],其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。根据动态规划的思想,状态转移方程为dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。如果s1[i-1]等于s2[j-1],则dp[i][j] = dp[i-1][j-1] + 1;否则dp[i][j]取其他两种情况中的较大值。最终结果为dp[m][n]。
2.1.4 寻找数组中第 k 小的元素
题目描述:给定一个无序数组和一个整数k,找到数组中第k小的元素。
解题思路:可以使用前缀和和快速选择算法来解决这个问题。具体实现与寻找第k大元素类似,只不过最后返回的是第k小的元素而非第k大的元素。
2.2 方法一:前缀和(差分数组)
解这个问题需要注意以下几点:
- 理解题意:首先,要明确题目的要求,理解自行车手的骑行路线和海拔变化的关系。根据题目描述,自行车手从海拔为0的点开始骑行,通过一系列的海拔变化,最终要找到最高点的海拔。
- 分析海拔变化:根据给定的gain数组,可以分析出自行车手的海拔变化。gain[i]表示点i和点i+1之间的净海拔高度差。通过累加这些高度差,可以计算出经过每个点后的总海拔变化。
- 确定最高点的海拔:在计算出总的海拔变化后,需要找到最高点的海拔。这可以通过比较累加海拔和初始海拔的大小来实现。最高点的海拔即为累加海拔和初始海拔中的较大值。
- 注意数组边界条件:在处理gain数组时,需要注意数组的边界条件。例如,gain[0]表示起点和终点之间的海拔高度差,而gain[n-1]表示倒数第二个点和终点之间的海拔高度差。
- 代码实现:最后,根据上述分析,可以使用Python等编程语言实现相应的算法。在实现过程中,需要注意代码的简洁性和可读性,同时也要注意处理可能的异常情况。
思路与算法:
我们假设每个点的海拔为 hi ,由于 gain[i] 表示第 i 个点和第 i+1 个点的海拔差,因此
gain[i] = h(i+1) − hi,那么:
可以发现,每个点的海拔都可以通过前缀和的方式计算出来。因此,我们只需要遍历一遍数组,求出前缀和的最大值,即为最高点的海拔。
实际上题目中的 gain 数组是一个差分数组,对差分数组求前缀和即可得到原海拔数组。然后求出原海拔数组的最大值即可。
三、代码
3.2 方法一:前缀和(差分数组)
Java版本:
class Solution {public int largestAltitude(int[] gain) {int high = 0, max = 0;for (int h : gain) {high += h;max = Math.max(max, high);}return max;}
}
C++版本:
class Solution {
public:int largestAltitude(std::vector<int>& gain) {int high = 0, max = 0;for (int h : gain) {high += h;max = std::max(max, high);}return max;}
};
Python版本:
class Solution:def largestAltitude(self, gain: List[int]) -> int:high = 0max_altitude = 0for h in gain:high += hmax_altitude = max(max_altitude, high)return max_altitude
Go版本:
func largestAltitude(gain []int) int {high, max := 0, 0for _, h := range gain {high += hif high > max {max = high}}return max
}func main() {gain := []int{-5, 1, 5, 0, -7}result := largestAltitude(gain)fmt.Println(result)
}
四、复杂度分析
4.2 方法一:前缀和(差分数组)
- 时间复杂度: O(n),其中 n 为数组 gain 的长度。
- 空间复杂度: O(1)。
相关文章:
【数据结构和算法】找到最高海拔
其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 前缀和的解题模板 2.1.1 最长递增子序列长度 2.1.2 寻找数组中第 k 大的元素 2.1.3 最长公共子序列…...
redis相关问题
1、概述: 1. 非关系型数据库 2. 是分布式缓存数据库 3. 使用 key -value结构存储 2、作用: 用作缓存降低数据库压力,提高性能;可以用作消息队列(削峰、解耦、异步调用) 3、基础语法: 基础命令…...
第41节: Vue3 watch函数
在UniApp中使用Vue3框架时,你可以使用watch函数来观察和响应Vue实例上的数据变化。以下是一个示例,演示了如何在UniApp中使用Vue3框架使用watch函数: <template> <view> <input v-model"message" type"text…...
Centos7:升级gcc、g++到版本5.2.0
背景 Centos7.9版本默认的g版本是4.8.5,在实践golang项目中,用到C14,编译时会报错:gcc: error: unrecognized command line option ‘-stdc14’ 因此,gcc需要升级到更高版本,我这里使用源码编译形式升级到g…...
Pytohn data mode plt
文章目录 文件的读写创建.csv类型的文件,并读取文件创建.xlsx文件 使用Python做图生成数据集切片取值操作修改张量中指定位置的数据 知识点torch.arange(x)torch.tensor(2)Atorch.randn(36).reshape(6,6)shapenumel()reshape(x,y,z)torch.zeros(3,3,4)torch.ones(2,…...
内网离线搭建之----kafka集群
1.系统版本 虚拟机192.168.9.184 虚拟机192.168.9.185 虚拟机192.168.9.186系统 centos7 7.6.1810 2.依赖下载 ps:置顶资源里已经下载好了,直接用!!!!!!!!…...
5.1 显示窗口的内容(一)
一,如何显示窗口的内容? 显示器用于在物理硬件(如计算机显示器或触摸屏显示器)上显示窗口的内容。 屏幕API提供的功能允许我们创建同时写入多个窗口和显示的应用程序。屏幕支持多个显示器,但创建和管理使用多个显示器…...
基于包围盒算法的三维点云数据压缩和曲面重建matlab仿真
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1 包围盒构建 4.2 点云压缩 4.3 曲面重建 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 ...........................................…...
关于Python里xlwings库对Excel表格的操作(十八)
这篇小笔记主要记录如何【设置单元格数据的对齐方式】。前面的小笔记已整理成目录,可点链接去目录寻找所需更方便。 【目录部分内容如下】【点击此处可进入目录】 (1)如何安装导入xlwings库; (2)如何在Wps下…...
VScode远程连接服务器,Pycharm专业版下载及远程连接(深度学习远程篇)
Visual Code、PyCharm专业版,本地和远程交互。 远程连接需要用到SSH协议的技术,常用的代码编辑器vscode 和 pycharm都有此类功能。社区版的pycharm是免费的,但是社区版不支持ssh连接服务器,只有专业版才可以,需要破解…...
Vue2和Vue3组件间通信方式汇总(3)------$bus
组件间通信方式是前端必不可少的知识点,前端开发经常会遇到组件间通信的情况,而且也是前端开发面试常问的知识点之一。接下来开始组件间通信方式第三弹------$bus,并讲讲分别在Vue2、Vue3中的表现。 Vue2Vue3组件间通信方式汇总(1)…...
PyTorch加载数据以及Tensorboard的使用
一、PyTorch加载数据初认识 Dataset:提供一种方式去获取数据及其label 如何获取每一个数据及其label 总共有多少的数据 Dataloader:为后面的网络提供不同的数据形式 数据集 在编译器中导入Dataset from torch.utils.data import Dataset 可以在jupyter中查看Dataset官方文档&…...
TensorFlow是什么
TensorFlow是什么 Tensorflow是一个Google开发的第二代机器学习系统,克服了第一代系统DistBelief仅能开发神经网络算法、难以配置、依赖Google内部硬件等局限性,应用更加广泛,并且提高了灵活性和可移植性,速度和扩展性也有了大幅…...
docker-compose 安装Sonar并集成gitlab
文章目录 1. 前置条件2. 编写docker-compose-sonar.yml文件3. 集成 gitlab4. Sonar Login with GitLab 1. 前置条件 安装docker-compose 安装docker 创建容器运行的特有网络 创建挂载目录 2. 编写docker-compose-sonar.yml文件 version: "3" services:sonar-postgre…...
支付平台在选择服务器租用时要注意什么?
如果要建设一个支付平台的话要进行服务器租用,一旦涉及到钱的方面就必须要顾虑到多方面,这样才能保证安全性,今天小编就给大家讲一讲要注意什么呢? 1、带宽:带宽是业务稳定性的直接因素,只有带宽充足,这样…...
IDEA2018升级2023,lombok插件不兼容导致get/set方法无法使用
1、问题 最近了解到一款叫CodeGeeX 的智能编程助手,想要试用一下,但是IDEA2018版本太低了,没有CodeGeeX插件,于是打算将IDEA升级到2023.2.5版本,具体升级过程略过,升级完成后,启动项目…...
企业微信服务商代开发模式获取授权企业的客户信息
服务商代开发素材: 服务商可信ip 企业微信认证 测试时不用再次创建一个企业微信,可以用当前的企业微信作为授权企业使用一、创建代开发应用模板 1,代开发模板回调URL配置 参考 注意:保存代开发应用模板时的corpId是服务商的企业…...
库存管理方法有哪些
库存管理是工作中一个离不开的话题,不管是仓管还是业务员都或多或少接触过库存管理方面的工作,例如:进货、销售、库存盘点等等这些都属于库存管理的范筹,那么库存管理方法有哪些?用哪种方法管理库存比较好,…...
数字化车间推动制造业生产创新
一、数字化车间应用场景 1:资源智能化管理 数字化车间通过搭建智能化的设备监测系统,实时采集和监控设备的运行状态和生产数据,对设备进行实时管理和维护,降低故障率和维修成本。同时,通过对生产过程中的数据采集和分…...
Linux的安装及管理程序
一、如何在linux安装卸载软件 1. 编译安装 灵活性较高 难度较大 可以安装较新的版本 2. rpm安装(redhat) linux 包安装 查软件信息:是否安装,文件列表 rpm 软件名 3. yum yum是RPM升级版本,解决rpm的弊端 安装软件 首…...
c语言-表达式求值
目录 前言一、隐式类型转换1.1 整型提升 二、算术转换三、操作符的属性四、问题表达式总结 前言 表达式求值的顺序一部分由操作符的优先级和结合性决定。 有些表达式的操作数在求值的过程中可能需要转换为其他类型 一、隐式类型转换 隐式类型转换是在编译器自动进行的类型转换…...
小型洗衣机哪个牌子质量好?口碑最好的四款小型洗衣机推荐
随着科技的快速发展,现在的人们越来越注重自己的卫生问题,不仅在吃上面会注重卫生问题,在用的上面也会更加严格要求,而衣服做为我们最贴身的东西,我们对它的要求也会更加高,所以最近这几年较火爆的无疑是内…...
springCould中的Ribbon-从小白开始【5】
目录 1.什么是Ribbo❤️❤️❤️ 2.eureka自带Ribbon ❤️❤️❤️ 3. RestTemplate❤️❤️❤️ 4.IRule❤️❤️❤️ 5.负载均衡算法❤️❤️❤️ 1.什么是Ribbo 1.Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端,负载均衡的工具。2.主要功能是提供客户端的软件…...
持续集成交付CICD:Jira 发布流水线
目录 一、实验 1.环境 2.GitLab 查看项目 3.Jira 远程触发 Jenkins 实现合并 GitLab 分支 4.K8S master节点操作 5.Jira 发布流水线 一、实验 1.环境 (1)主机 表1 主机 主机架构版本IP备注master1K8S master节点1.20.6192.168.204.180 jenkins…...
JuiceSSH结合内网穿透实现公网远程访问本地Linux虚拟机
文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …...
使用 pytest.ini 文件控制输出 log 日志
一、前置说明 pytest.ini 文件中可以配置参数来控制 pytest 的运行行为,其存放路径要求与 conftest.py 一样。 项目根目录project_root/ ├── pytest.ini ├── tests/ │ └── test_demo.py以test开头的测试子目录project_root/ ├── tests/ │ ├── pytest.in…...
【Spring】SpringBoot 配置文件
文章目录 什么是配置文件SpringBoot配置文件配置文件快速入手配置文件的格式properties 配置文件说明properties 基本语法读取配置文件信息properties 配置格式缺点 yml 配置文件说明yml 基本语法使用 yml 连接数据库 yml 使用进阶yml 配置不同数据类型配置对象配置集合配置Map…...
Koordinator 支持 K8s 与 YARN 混部,小红书在离线混部实践分享
作者:索增增(小红书)、宋泽辉(小红书)、张佐玮(阿里云) 背景介绍 Koordinator 是一个开源项目,基于阿里巴巴在容器调度领域多年累积的经验孵化诞生,目前已经支持了 K8s…...
网游逆向分析与插件开发-游戏反调试功能的实现-项目需求与需求拆解
上一个专栏结束位置:网游逆向分析与插件开发-代码保护壳的优化-修改随机基址为固定基址-CSDN博客 上一个专栏是做了一个壳有了一定的保护,但是保护还是不够,最大的保护是根上把问题解决了,就是我不允许你对我进行调试,…...
阶段七-GitEE
Git:版本控制软件 Git的优点 1.1 协同修改 多人并行不悖的修改服务器端的同一个文件。 1.2 数据备份 不仅保存目录和文件的当前状态,还能够保存每一个提交过的历史状态。 1.3 版本管理 在保存每一个版本的文件信息的时候要做到不保存重复数据&…...
Redis小记(1)
目录 1.Redis和Mysql的区别 2.Redis常用命令 1.Redis和Mysql的区别 a:mysql和redis的存储方式不同 mysql是关系型数据库,用表来进行存储数据。 redis是通过键值对来存储数据,key使用string来标识,value可以是各种不同的数据结构。 b:mys…...
Flutter windows 环境配置
Flutter windows 环境配置 从零开始,演示flutter环境配置到启动项目,同时支持 vscode 和 android studio 目录 Flutter windows 环境配置一、环境配置1. Flutter SDK2. Android Studio3. JDK4. 拓展安装5. Visual Studio 2022二、项目创建和启动1. vsco…...
odoo17核心概念view5——ir_ui_view.py
这是view系列的第5篇文章,介绍一下view对应的后端文件ir_ui_view.py,它是base模块下的一个文件 位置:odoo\addons\base\models\ir_ui_view.py 该文件一共定义了三个模型 1.1 ir.ui.view.custom 查询数据库这个表是空的,从名字看…...
截断整型提升算数转换
文章目录 🚀前言🚀截断🚀整型提升✈️整型提升是怎样的 🚀算术转换 🚀前言 大家好啊!这里阿辉补一下前面操作符遗漏的地方——截断、整型提升和算数转换 看这一篇要先会前面阿辉讲的数据的存储否则可能看不…...
阿里云 ECS Docker、Docker Compose安装
https://help.aliyun.com/document_detail/51853.html https://docs.docker.com/compose/install/ Centos https://blog.csdn.net/Alen_xiaoxin/article/details/104850553 systemctl enable dockerdocker-compose安装 https://blog.csdn.net/qq465084127/article/details/…...
LeetCode——1276. 不浪费原料的汉堡制作方案
通过万岁!!! 题目,给你两个数tomatoSlices和cheeseSlices,然后每制作一个巨无霸汉堡则消耗4个tomatoSlices和1和cheeseSlices,每制作一个小皇堡则需要消耗2个tomatoSlices和1和cheeseSlices。问给你这两个…...
隆道吴树贵:生成式人工智能在招标采购中的应用
12月22日,由中国招标投标协会主办的招标采购数字发展大会在北京召开,北京隆道网络科技有限公司总裁吴树贵受邀出席大会,并在“招标采购数字化交易创新成果”专题会议上发言,探讨生成式人工智能如何在招标采购业务中落地应用。 本次…...
docker搭建kali及安装oneforall
前期docker的安装这里就不用多说了,直接看后面的代码 安装oneforall 1.安装git和pip3 sudo apt update sudo apt install git python3-pip -y2.克隆项目 git clone https://gitee.com/shmilylty/OneForAll.git3.安装相关依赖 cd OneForAll/ sudo apt install pyt…...
【MySQL】数据库之事务
目录 一、什么是事务 二、事务的ACID是什么? 三、有哪些典型的不一致性问题? 第一种:脏读 第二种:不可重复读 第三种:幻读 第四种:丢失更新 四、隔离级别有哪些? (1…...
AGV|RGV小车RFID传感器CNS-RFID-01/1S的RS232通讯联机方法
CNS-RFID-01/1S广泛应用于AGV小车,搬运机器人,无人叉车等领域,用于定位,驻车等应用,可通过多种通讯方式进行读写操作,支持上位机控制,支持伺服电机,PLC等控制设备联机,本…...
【Python可视化系列】一文教会你绘制美观的热力图(理论+源码)
一、问题 前文相关回顾: 【Python可视化系列】一文彻底教会你绘制美观的折线图(理论源码) 【Python可视化系列】一文教会你绘制美观的柱状图(理论源码) 【Python可视化系列】一文教会你绘制美观的直方图(理…...
百度Apollo五步入门自动驾驶:Dreamview与离线数据包分析(文末赠送apollo周边)
🎬 鸽芷咕:个人主页 🔥 个人专栏:《linux深造日志》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! ⛳️ 粉丝福利活动 ✅参与方式:通过连接报名观看课程,即可免费获取精美周边 ⛳️活动链接…...
为什么IPv6 可以作为低功耗蓝牙的物联网体系结构?
蓝牙40规范引人了低功耗蓝牙(Bluetooth Low Energy,BLE)技术。低牙是一种低能低延成本的无线通信技术。 与传统蓝牙相比,低功耗蓝牙同样使用24GHz频段,但其将信道重新划分为 40个,包含37 个数据信道和3个广播信道(传统蓝牙共使用 79 个信道)低功蓝牙的协…...
GPT每预测一个token就要调用一次模型
问题:下图调用了多少次模型? 不久以前我以为是调用一次 通过看代码是输出多少个token就调用多少次,如图所示: 我理解为分类模型 预测下一个token可以理解为分类模型,类别是vocab的所有token,每一次调用都…...
运维工程师的出路到底在哪里?
1.35岁被称为运维半衰期,主要是因为运维工作的技术栈和工作方式在不断更新和演进。随着新技术的出现和发展,老旧的技术逐渐被淘汰,运维工作也需要不断学习和适应新技术,否则就容易被市场淘汰。 2.要顺利过渡半衰期,运…...
2312clang,基于访问者的前端动作
原文 基于RecursiveASTVisitor的ASTFrontendActions. 创建用RecursiveASTVisitor查找特定名字的CXXRecordDeclAST节点的FrontendAction. 创建FrontendAction 编写基于clang的工具(如Clang插件或基于LibTooling的独立工具)时,常见入口是允许在编译过程中执行用户特定操作的F…...
怎么搭建实时渲染云传输服务器
实时渲染云传输技术方案,在数字孪生、虚拟仿真领域使用越来越多,可能很多想使用该技术方案项目还不知道具体该怎么搭建云传输服务器,具体怎么使用实时云渲染平台系统。点量云小芹将对这两个问题做集中分享。 一、实时渲染服务器怎么搭建&…...
如何在生产环境正确使用Redis
一、在生产环境使用Redis 如果在生产环境使用Redis,需要遵守一定的使用规范,以保障服务稳定、高效。。 1.1、明确Redis集群的服务定位 1、仅适用于缓存场景:Redis定位于高性能缓存服务,强调快速读写和低延迟的特性,…...
LeetCode-环形链表问题
1.环形链表(141) 题目描述: 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统…...
C# 读取Word表格到DataSet
目录 功能需求 Office 数据源的一些映射关系 范例运行环境 配置Office DCOM 关键代码 组件库引入 核心代码 杀掉进程 总结 功能需求 在应用项目里,多数情况下我们会遇到导入 Excel 文件数据到数据库的功能需求,但某些情况下,也存…...