当前位置: 首页 > news >正文

【前缀和】42. 接雨水

本文涉及知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9

提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

枚举

vWater[i] 记录 第i个柱子水的高度。
令 leftMax =max(height[0…i-1])
rightMax = max(height[i+1…])
如果水高于 leftMax 或 rightMax,水会流走。故水的高度为:min(leftMax,rightMax) - height[i]
结果为负,则为0。
更改leftMax为max(height[0…i]),rightMax类似。则不需要考虑负数。
时间复杂度:O(n)

代码

核心代码

class Solution {
public:int trap(vector<int>& height) {const int n = height.size();vector<int> vLeft = height;for (int i = 1; i < n; i++) {vLeft[i] = max(vLeft[i], vLeft[i - 1]);}int iRightMax = 0;int iRet = 0;for (int i = n - 1; i >= 0; i--) {iRightMax = max(iRightMax, height[i]);const int iWater = min(iRightMax, vLeft[i]);iRet += iWater - height[i];}return iRet;}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> height;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){	height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };auto res = Solution().trap(height);AssertEx(6,res);}TEST_METHOD(TestMethod1){height = { 4, 2, 0, 3, 2, 5 };auto res = Solution().trap(height);AssertEx(9, res);}};
}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

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

相关文章:

【前缀和】42. 接雨水

本文涉及知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&am…...

我的名字叫大数据

第1章 大家好,我叫大数据 1.1 我的家族传统:从我小小的祖先到壮大的我 1.1.1 最初的我:原始部落里的计数石头 大家好,我是你们人类文明的“老朋友”——大数据。你们知道吗?在我还没有变成你们手机、电脑里飞速跑动的那些数字前,我最初的模样可是一块块“计数石头”。…...

数据库漫谈-infomix

infomix数据库知名度不高&#xff0c;主要跟它的定位有关&#xff0c;它主要用于unix操作系统&#xff1a;Informix便是取自Information和Unix的结合&#xff0c;它也是第一个支持linux系统的数据库。它其实在金融、电信行业使用率非常高。98年&#xff0c;当时我在做银行领域的…...

【Qt】Qt界面美化指南:深入理解QSS样式表的应用与实践

文章目录 前言&#xff1a;1. 背景介绍2. 基本语法3. QSS 设置方式3.1. 设置全局样式3.2. 从文件加载样式表3.3. 使用 Qt Designer 编辑样式 总结&#xff1a; 前言&#xff1a; 在当今这个视觉至上的时代&#xff0c;用户界面&#xff08;UI&#xff09;的设计对于任何软件产…...

七彩云南文化旅游网站的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;游客管理&#xff0c;导游管理&#xff0c;旅游景点管理&#xff0c;酒店信息管理 前台账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;论坛&#xff0c;旅…...

7-zip安装教程

一、简介 7-Zip 是一款开源的文件压缩软件&#xff0c;由 Igor Pavlov 开发。它具有高压缩比、支持多种格式、跨平台等特点。使用 C语言编写&#xff0c;其代码在 Github 上开源。 7-Zip的官网&#xff1a; 7-Zip 7-zip官方中文网站&#xff1a; 7-Zip 官方中文网站 7-Zip 的 G…...

oracle 12c DB卸载流程

1.运行卸载程序 [rootprimary1 ~]# su - oracle [oracleprimary1 ~]$ cd $ORACLE_HOME/deinstall [oracleprimary1 deinstall]$ ./deinstall Checking for required files and bootstrapping ... Please wait ... 这里选择3 、回车、y、y、回车、ASM 这里输入y 2.删除相关目录…...

Docker学习笔记 - 创建自己的image

目录 基本概念常用命令使用docker compose启动脚本创建自己的image 使用Docker是现在最为流行的软件发布方式&#xff0c; 本系列将阐述Docker的基本概念&#xff0c;常用命令&#xff0c;启动脚本和如何生产自己的docker image。 在我们发布软件时&#xff0c;往往需要把我…...

java web爬虫

目录 读取本地文件 从网站读取文件 java爬虫 总结 读取本地文件 import java.io.File; import java.io.PrintWriter; import java.util.Scanner;public class ReplaceText {public static void main() throws Exception{File file new File("basic\\test.txt"…...

MySQL开发教程和具体应用案例

一、MySQL开发教程 初识数据库 定义:数据仓库,安装在操作系统之上,用于存储和管理数据。 分类:关系型数据库(如MySQL、Oracle、SQL Server)和非关系型数据库(如Redis、MongoDB)。 SQL:结构化查询语言,用于管理和操作关系型数据库。 操作数据库 创建、修改、删除…...

QT C++ 模型视图结构 QTableView 简单例子

在Qt中&#xff0c;MVC模式被广泛使用于各种用户界面框架中&#xff0c;包括Qt的模型视图结构。Qt的模型视图结构是基于MVC模式设计的&#xff0c;其中包括了Model、View和Delegate三个部分。 QTableView是Qt模型视图结构中的一种视图&#xff0c;它用于以表格形式显示数据。 …...

2024年3月电子学会Python编程等级考试(四级)真题题库

2024年3月青少年软件编程Python等级考试&#xff08;四级&#xff09;真题试卷 题目总数&#xff1a;38 总分数&#xff1a;100 选择题 第 1 题 单选题 运行如下Python代码&#xff0c;若输入整数3&#xff0c;则最终输出的结果为&#xff1f;&#xff08; &#xff…...

深入分析 Android BroadcastReceiver (一)

文章目录 深入分析 Android BroadcastReceiver (一)1. Android BroadcastReceiver 设计说明1.1 BroadcastReceiver 的主要用途 2. BroadcastReceiver 的工作机制2.1 注册 BroadcastReceiver2.1.1 静态注册2.1.2 动态注册 3. BroadcastReceiver 的生命周期4. 实现和使用 Broadca…...

2024医美如何做抖音医美抖音号,本地团购、短视频直播双ip爆品引流,实操落地课

课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/89307619 更多资源下载&#xff1a;关注我。 课程内容&#xff1a; 01-0-序.mp4 02-01-账号定位.mp4 03-02-误区.mp4 04-03-五件套.mp4 05-04-文案怎么来.mp4 06-05-对标怎么弄.mp4 07-06-人设怎…...

Debian常用指令指南:高效管理你的Linux系统

Debian作为Linux发行版中的佼佼者&#xff0c;以其稳定性和安全性而闻名。掌握Debian的常用指令对于系统管理员和开发人员来说至关重要。本文将介绍一系列Debian系统中的常用指令&#xff0c;帮助你高效地管理和维护你的系统。喜欢的话记得一键三连哦&#xff0c;方便找到它。 …...

什么是DELINS交货指示?

DELINS 是指 Delivery Instruction&#xff08;交货指示&#xff09;报文&#xff0c;用于在供应链管理中传递交货指令和相关信息。该报文用于在供应链中的不同合作伙伴之间交换关于交货的详细信息。 DELINS 报文的主要功能 交货指示&#xff1a;传达具体的交货指令&#xff…...

基于Open3D的点云处理24-ICP匹配cuda加速

参考:docs/jupyter/t_pipelines/t_icp_registration.ipynb 完整测试用例: import open3d as o3d import open3d.core as o3cif o3d.__DEVICE_API__ == cuda:import open3d.cuda.pybind.t.pipelines.registration as treg else:...

UE_地编教程_创建地形洞材质

个人学习笔记&#xff0c;不喜勿喷。侵权立删&#xff01; 使用地形洞材质来遮罩地形上特定位置的可视性和碰撞。如要在山脉侧面创建进入洞穴的入口&#xff0c;此操作将非常有用。可使用地形材质和地形洞材质的相同材质&#xff0c;但注意&#xff1a;对比不使用不透明蒙版的…...

「C系列」C 基本语法

文章目录 一、C 基本语法1. **程序结构**2. **数据类型**3. **变量声明**4. **运算符**6. **函数**7. **指针**8. **数组**9. **结构体和联合体**10. **预处理指令**11. **内存管理** 二、C 关键字1. 整体概览2. 具体关键字数据类型关键字控制流关键字其他关键字C11新增关键字总…...

java期末细节知识整理(一)

1.java程序的执行过程&#xff1a;先编译后解释。也就是我们在idea写的文件叫做java源文件&#xff08;.java结尾的文件&#xff09;&#xff0c;经过编译器会生成字节码文件&#xff08;.class结尾的文件&#xff09;&#xff0c;再通过解释器进行实现 2.栈用来存储引用类型的…...

从模型评估、梯度难题到科学初始化:一步步解析深度学习的训练问题

偏差 & 方差要理解模型的泛化能力&#xff0c;我们首先要量化它的“泛化误差”&#xff0c;即模型在未知数据上的表现。然而&#xff0c;泛化误差并非一个单一的问题&#xff0c;它源于三种不同性质的错误&#xff1a;模型固有的近似能力不足、对训练数据的过度敏感、模型数…...

Windows Defender Remover:系统性能优化与防护机制管理指南

Windows Defender Remover&#xff1a;系统性能优化与防护机制管理指南 【免费下载链接】windows-defender-remover A tool which is uses to remove Windows Defender in Windows 8.x, Windows 10 (every version) and Windows 11. 项目地址: https://gitcode.com/gh_mirror…...

OpenClaw技能开发:为nanobot编写天气查询插件

OpenClaw技能开发&#xff1a;为nanobot编写天气查询插件 1. 为什么需要自定义技能 当我第一次接触OpenClaw时&#xff0c;最吸引我的不是它预置的那些功能&#xff0c;而是它允许开发者自由扩展能力的开放架构。作为一个经常需要查询天气的开发者&#xff0c;我发现现有的天…...

OpenClaw自动化测试:nanobot驱动浏览器执行回归用例

OpenClaw自动化测试&#xff1a;nanobot驱动浏览器执行回归用例 1. 为什么选择OpenClaw进行自动化测试 去年接手一个老项目时&#xff0c;我遇到了一个典型的前端测试困境——每次发版前需要手动执行87个回归测试用例&#xff0c;整个过程耗时近4小时。尝试过Selenium和Playw…...

轻量级C++ HTTP库:cpp-httplib极速集成指南

轻量级C HTTP库&#xff1a;cpp-httplib极速集成指南 【免费下载链接】cpp-httplib A C header-only HTTP/HTTPS server and client library 项目地址: https://gitcode.com/GitHub_Trending/cp/cpp-httplib 核心价值&#xff1a;单文件驱动的开发效率革命 cpp-httplib…...

iCalendar文件逆向解析:用Python拆解别人发你的会议邀请(附Outlook兼容性测试)

iCalendar文件逆向解析实战&#xff1a;Python拆解会议邀请的完整指南 收到会议邀请时&#xff0c;那个小小的.ics文件里藏着多少秘密&#xff1f;作为技术人员&#xff0c;我们常常需要从第三方日历文件中提取关键信息、分析重复规则&#xff0c;甚至修复跨时区协作中的时间错…...

Wan2GP:革命性开源视频生成平台,仅需6GB VRAM即可创作好莱坞级影片

Wan2GP&#xff1a;革命性开源视频生成平台&#xff0c;仅需6GB VRAM即可创作好莱坞级影片 【免费下载链接】Wan2GP Wan 2.1 for the GPU Poor 项目地址: https://gitcode.com/gh_mirrors/wa/Wan2GP Wan2GP&#xff08;GitHub加速计划&#xff09;是一款专为GPU资源有限…...

网易云音乐评论爬虫实战:破解加密接口抓取数据

一、接口分析&#xff1a;找准评论数据请求入口 在抓取网易云音乐歌曲评论时&#xff0c;我们不难发现&#xff0c;页面并不会随着翻页刷新跳转&#xff0c;评论的加载属于异步AJAX请求。这类接口有一个明显特点&#xff1a;接口地址固定不变&#xff0c;分页切换完全依靠请求载…...

流处理 vs 批处理:大数据时代的技术选择指南

流处理 vs 批处理&#xff1a;大数据时代的技术选择指南 关键词&#xff1a;流处理、批处理、大数据、实时计算、离线计算、延迟、吞吐量 摘要&#xff1a;在大数据时代&#xff0c;数据处理就像一场永不停歇的"数据马拉松"。流处理和批处理是两种最核心的技术方案&a…...

3个让Mac窗口管理效率倍增的秘密武器:AltTab深度解析

3个让Mac窗口管理效率倍增的秘密武器&#xff1a;AltTab深度解析 【免费下载链接】alt-tab-macos Windows alt-tab on macOS 项目地址: https://gitcode.com/gh_mirrors/al/alt-tab-macos 作为一名从Windows转战macOS的开发者&#xff0c;你是否也曾为窗口切换效率低下…...