力扣上的经典问题:接雨水
力扣上的经典问题:接雨水
在众多的编程题库中,力扣(LeetCode)是一个非常受欢迎的平台,拥有大量的算法和数据结构练习题。其中,接雨水(Trapping Rain Water)问题因其巧妙的思路和广泛的应用场景,成为了经典的面试题之一。在这篇博客中,我将介绍这个问题的背景,解决思路,并给出用C语言实现的解决方案。
问题描述
接雨水问题的描述如下:
给定一个表示高度的数组,数组中的每个元素表示一个柱子的高度,柱子之间的宽度为1。求出这个柱子图形在下雨之后能够接多少雨水。
举例来说,给定高度数组:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
该数组表示的图形如下图所示:
## ### ## ###############
通过图形可以看出,能够接住的雨水总量为6。
解题思路
解决这个问题的方法有很多种,常见的有以下几种:
- 暴力法:对于每一个柱子,分别计算其左右两边的最大高度,然后取其最小值减去柱子自身的高度,累加所有柱子能够接住的水量。
- 动态编程:预先计算每一个柱子的左边最高高度和右边最高高度,然后同样计算水量。
- 双指针法:使用双指针从两端向中间遍历,计算能够接住的水量。
下面我们主要介绍双指针法,这种方法时间复杂度为O(n),空间复杂度为O(1),比较高效。
C语言代码实现
#include <stdio.h>int trap(int* height, int heightSize) {if (heightSize == 0) return 0;int left = 0, right = heightSize - 1;int left_max = 0, right_max = 0;int water = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= left_max) {left_max = height[left];} else {water += left_max - height[left];}left++;} else {if (height[right] >= right_max) {right_max = height[right];} else {water += right_max - height[right];}right--;}}return water;
}int main() {int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};int size = sizeof(height) / sizeof(height[0]);int result = trap(height, size);printf("The amount of trapped rain water is: %d\n", result);return 0;
}
代码解析
-
初始化变量:
left和right分别指向数组的两端。left_max和right_max分别记录左右两边的最大高度。water用于累加接住的雨水总量。
-
双指针遍历:
- 当左指针指向的高度小于右指针指向的高度时,处理左指针指向的柱子:
- 如果当前高度大于或等于
left_max,更新left_max。 - 否则,将
left_max减去当前高度,得到当前柱子能接住的雨水量,累加到water。
- 如果当前高度大于或等于
- 当右指针指向的高度小于等于左指针指向的高度时,处理右指针指向的柱子:
- 如果当前高度大于或等于
right_max,更新right_max。 - 否则,将
right_max减去当前高度,得到当前柱子能接住的雨水量,累加到water。
- 如果当前高度大于或等于
- 当左指针指向的高度小于右指针指向的高度时,处理左指针指向的柱子:
-
输出结果:最终
water中累加的值即为总共能接住的雨水量。
总结
接雨水问题是一个经典的动态规划问题,通过不同的方法可以优化时间和空间复杂度。双指针法因其较低的时间复杂度和空间复杂度,成为了面试中常见的解法之一。希望这篇博客能够帮助大家更好地理解接雨水问题,并掌握其解决思路和方法。
希望这篇博客对你有帮助!如果你有任何问题或需要进一步的解释,请随时告诉我。
相关文章:
力扣上的经典问题:接雨水
力扣上的经典问题:接雨水 在众多的编程题库中,力扣(LeetCode)是一个非常受欢迎的平台,拥有大量的算法和数据结构练习题。其中,接雨水(Trapping Rain Water)问题因其巧妙的思路和广泛…...
双例集合(二)——双例集合的实现类之HashMap容器类
双例集合的常用实现类有HashMap和TreeMap两个,通过这两个类我们可以实现Map接口定义的容器,一般情况下使用HashMap容器类较多。 HashMap容器类是Map接口最常用的实现类,它的底层采用Hash算法来实现,这也就满足了键key不能重复的要…...
oracle-定时器(job)
--1分钟运行一次定时任务。sysdate为了定时任务即可生效。 DECLARE JOB NUMBER; BEGIN DBMS_JOB.SUBMIT(JOB,P_HJZ_HJZ_PJ_DDYTKAPB_INIT_JOB;,SYSDATE,sysdate1/24/60); COMMIT; END; / select * from user_jobs; --删除 begin DBMS_JOB.broken (462, false); DBM…...
cron.timezone
系统 date 数据库 show timezone插件 show cron.timezonealter system set cron.timezonePRC;show cron.timezone...
Hadoop+Spark大数据技术(测试)
1、九九乘法表 在下面的单元格中编写Scala程序,输出上三角形的九九乘法表,并运行。 for (i <- 1 to 9 reverse) {for (j <- 1 to i) {print(s"$j x $i ${i * j}\t")}println() } 2、单词计数 在下面的若干单元格中编写Spark程序&#…...
使用新语法连接Qt 5中重载的信号和槽
在使用Qt 5中的新信号和槽连接语法(使用成员函数指针)时,我遇到了一些问题。根据新的信号槽语法的描述,我尝试将以下代码: QObject::connect(spinBox, SIGNAL(valueChanged(int)),slider, SLOT(setValue(int)));改为&…...
梯度提升决策树(GBDT)的训练过程
以下通过案例(根据行为习惯预测年龄)帮助我们深入理解梯度提升决策树(GBDT)的训练过程 假设训练集有4个人(A、B、C、D),他们的年龄分别是14、16、24、26。其中A、B分别是高一和高三学生&#x…...
路由器的Wi-Fi性能是否限制了你的网速?这里有你想要的答案
你的无线网络速度阻碍了你吗?信不信由你,升级到超快的互联网计划可能不值得。以下是如何判断路由器的Wi-Fi速度是否阻碍了你,以及你能做些什么。 如何测试你的Wi-Fi速度 比较你的有线速度和无线速度可以表明你的路由器是否阻碍了你。虽然很多人认为“Wi-Fi”和“互联网”…...
简站WordPress是最简洁好用易上手的wordpress企业建站主题
简站WordPress主题确实是一个非常简洁、好用且易上手的企业建站主题。以下是详细分析: 简洁性:简站WordPress主题采用了扁平化设计风格,界面简洁明了,这使得它在众多WordPress主题中脱颖而出。这种设计不仅美观,还能提…...
阿里云 debian10.3 sudo apt-get updat 报错的解决方案
阿里云全新的debian10.3(buster)镜像,却无法正常执行 sudo apt-get update。主要报错信息如下: Err:6 http://mirrors.cloud.aliyuncs.com/debian buster-backports Release404 Not Found [IP: 100.100.2.148 80] Err:3 http://mirrors.cloud.aliyuncs…...
vite中使用scss技巧
一、样式混合 1.普通用法 mixin flex() {display: flex;justify-content: space-around;align-items: center; }//使用方法 .legend_box_item {width: 50%;height: 10px;include flex; }2.传递参数,参数后面的值为默认值 mixin flex($justify: flex-start, $alig…...
PyQt5/Pyside2学习记录
前言 最近导师的项目要求是PyQt,现学现用,现在写下中间的一些注意事项。 本程序分为两个界面,要求两个界面能堆叠显示,一个首页界面,一个功能界面。在功能界面中,有三个操控的控件,下拉框、文本…...
记一次通过脚本来实现自定义容器的自动重启
通过脚本来实现自定义容器的自动重启 1. 场景还原2. 自定义启动脚本3. 使用自定义脚本来作为容器启动的脚本4. 制作自定义脚本作为入口点的新镜像5. 测试新镜像启动是否走自定义启动脚本 1. 场景还原 现在我有一个自定义的Docker镜像,是基于基础镜像来构建的带有多…...
基于Django、Bootstrap的电影推荐系统,算法基于用户的协同过滤算法,有爬虫有可视化后台
背景 基于Django和Bootstrap的电影推荐系统结合了用户协同过滤算法,通过爬虫技术获取电影数据,并在可视化后台展示推荐结果。该系统旨在提供个性化的电影推荐服务,帮助用户发现符合其喜好的电影。 用户协同过滤算法是一种常用的推荐算法&am…...
mysql、mariadb 登录主机的含义,如何修改登录主机,如何删除登录主机
MariaDB版本: 10.3.39 登录主机的含义: 参考 1 阿风说事:说世间百态、聊奇闻趣事,分享个人观点和独到见解 2 mysql授权localhost&%区别及一直授权错误解决办法(安装openstack有感) 3 ERROR 1396 (HY000): Operat…...
c++ 设计模式 的课本范例
(1) 框架设计模式 model mode : 算法的框架不变,算法的细节可以改变。主要依赖多态。 class Player { protected:int life;int magic;int attack;virtual void effect_self() {}virtual void effect_enemy() {}virtual bool can_…...
QT中绘制点阵
1.QGraphicsScene,QGraphicsView,QGraphicsItem机制 #include <QApplication> #include <QGraphicsView> #include <QGraphicsScene> #include <QGraphicsEllipseItem>int main(int argc, char *argv[]) {QApplication app(arg…...
机器人里程计(Odometry)
机器人里程计(Odometry)是机器人定位和导航中的一个关键概念,它涉及到利用传感器数据来估计机器人在环境中的位置和姿态。里程计的基本原理是根据机器人自身动作的反馈来计算其相对于初始位置的位移。这通常包括机器人从一个已知位置开始&…...
后端实现预览pdf,mp4,图片
PDF预览 /*** pdf预览* param response*/RequestMapping(value "/preview")public void showPdf(HttpServletResponse response) {try {//String filePath this.getClass().getClassLoader().getResource("../../static/pdf/readme.pdf").getPath();Stri…...
【C++】数据类型、函数、头文件、断点调试、输入输出、条件与分支、VS项目设置
四、基本概念 这部分和C语言重复的部分就简写速过,因为我之前写过一个C语言的系列,非常详细。C和C这些都是一样的,所以这里不再一遍遍重复码字了。感兴趣的同学可以翻看我之前的C语言系列文章。 1、数据类型 编程的本质就是操作数据。 操…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
验证redis数据结构
一、功能验证 1.验证redis的数据结构(如字符串、列表、哈希、集合、有序集合等)是否按照预期工作。 2、常见的数据结构验证方法: ①字符串(string) 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...
