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

leetcode 42. 接雨水

2023.8.29

         本题可以用双指针做,求出每一列能盛的雨水,再相加即可。不过暴力法会超时,需要优化。

双指针(暴力):

class Solution {
public:int trap(vector<int>& height) {int ans = 0;for(int i=1; i<height.size()-1; i++){int max_rheight = height[i]; //记录当前柱子右边的最高柱子int max_lheight = height[i]; //记录当前柱子左边的最高柱子for(int r=i+1; r<height.size(); r++){max_rheight = max(max_rheight,height[r]);}for(int l=i-1; l>=0; l--){max_lheight = max(max_lheight,height[l]);}ans += max(0 , min(max_rheight,max_lheight)-height[i]);}return ans;}
};

双指针(优化):

        上面双指针暴力法每次遍历都需要求一次当前柱子左右两侧的最高柱子,这样有重复,自然会超时。 优化办法是设置两个数组left和right,分别存储每一个柱子的左侧最高柱子,及右侧最高柱子,这样子就不用重复遍历了。 代码如下:

class Solution {
public:int trap(vector<int>& height) {//求出当前柱子的左侧最高柱子以及右侧最高柱子,保存在两数组中。vector<int> left(height.size());vector<int> right(height.size());int max_lheight = height[0];int max_rheight = height[height.size()-1];for(int i=1; i<left.size()-1; i++){left[i] = max_lheight;max_lheight = max(max_lheight,height[i]);}for(int i=right.size()-2; i>=1; i--){right[i] = max_rheight;max_rheight = max(max_rheight,height[i]);}//遍历每一列求出最大雨水int ans = 0;for(int i=1; i<height.size()-1; i++){ans += max(0 , min(left[i],right[i])-height[i]);}return ans;}
};

相关文章:

leetcode 42. 接雨水

2023.8.29 本题可以用双指针做&#xff0c;求出每一列能盛的雨水&#xff0c;再相加即可。不过暴力法会超时&#xff0c;需要优化。 双指针&#xff08;暴力&#xff09;&#xff1a; class Solution { public:int trap(vector<int>& height) {int ans 0;for(int …...

【Lychee图床】本地电脑搭建私人图床,公网远程访问

文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站&#xff0c;可以看做是云存储的一部分&#xff0c;既可…...

【MySQL系列】-ORDER BY……HAVING详解及limit

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

浅析Keil MDK下串行Flash的下载算法设计

浅析Keil MDK下串行Flash的下载算法设计-电子发烧友网 今天给大家介绍的是 Keil MDK 工具下 i.MXRT 的串行 NOR Flash 下载算法设计。 在 i.MXRT 硬件那些事系列之《在串行 NOR Flash XIP 调试原理》一文中&#xff0c;痞子衡简单提了一下串行 NOR Flash 下载算法的概念&…...

springboot自动装配原理,手写一个starter。

文章目录 springboot自动装配原理手写starter手写starter总结&#xff1a; springboot自动装配原理 口述&#xff1a; springboot自动装配的话它其实就是只需要我们添加一个starter起步依赖&#xff0c;它就能完成这个依赖组件相关Bean的自动注入&#xff0c;其实就是自动的将…...

革命性的电子元件:RAD继电器 | 百能云芯

在现代电子和通信系统中&#xff0c;RAD继电器是一种关键的电子元件&#xff0c;它在各种应用中发挥着重要作用。RAD继电器&#xff08;Reed-relay Actuated Device&#xff09;是一种基于磁性原理的电子开关&#xff0c;其特点是极其高速、可靠、低功耗和长寿命。下面云芯将为…...

文献阅读:Deep Learning Enabled Semantic Communication Systems

目录 论文简介关于文章内容的总结引申出不理解的问题 论文简介 作者 Huiqiang Xie Zhijin Qin Geoffrey Ye Li Biing-Hwang Juang 发表期刊or会议 《IEEE TRANSACTIONS ON SIGNAL PROCESSING》 发表时间 2021.4 这篇论文由《Deep Learning based Semantic Communications: A…...

巨人互动|游戏出海游戏出海效果怎样?

游戏出海是指将原本面向国内市场的游戏产品进行调整和优化&#xff0c;以适应海外市场的需求&#xff0c;并进行推广和销售。下面小编讲讲关于游戏出海对于游戏效果的影响的一些讨论点。 1、市场扩大 通过游戏出海&#xff0c;可以将游戏产品的目标受众从国内扩展到全球范围内…...

二、GoLang输出HelloWorld、变量定义、数据类型的转换

一、输入Hello World go语言中&#xff0c;想要输出内容到控制台&#xff0c;package必须是main&#xff0c;包括方法名也必须是main&#xff0c; go语言输出的语法是 fmt 库。 package mainimport "fmt"func main() {// go语言中 输出内容 使用的库是 fmt库fmt.Pr…...

Mars3d图层树//图层管理加载时设置默认折叠的状态

问题&#xff1a;Mars3d图层树//图层管理加载时设置默认折叠的状态。 设置参考&#xff1a; 有个参数 open:false&#xff0c;写在对应的图层配置下&#xff0c;比如某个节点不展示&#xff0c;就对这个节点配置下。 如果全局&#xff0c;可以搜下这个widget内的代码&#xff…...

区块链技术|DApp与传统应用程序的关键区别

在数字时代&#xff0c;应用程序已经成为我们生活的一部分&#xff0c;无论是社交媒体、金融服务还是娱乐媒体&#xff0c;应用程序几乎无处不在。然而&#xff0c;随着区块链技术的崭露头角&#xff0c;一种新型应用程序——去中心化应用程序&#xff08;DApp&#xff09;正在…...

Python 加密解密技巧大揭秘:让你的数据安全无忧

建议食用原文链接效果更佳 Python 加密解密技巧大揭秘&#xff1a;让你的数据安全无忧 今天我们将探讨在 Python 中常见的加密解密算法&#xff0c;并通过代码案例来帮助大家更好地理解它们的实现。 在开始之前&#xff0c;请确保您已经安装了 pycryptodome 这个库。您可以使用…...

C#判断字符是否为utf16编码

unity截取显示微信昵称后&#xff0c;出现异常Error: UTF-16 to UTF-8 conversion failed because the input string is invalid&#xff0c;原因是截取字符串刚好截到了表情后面&#xff0c;解决思路是从截取到的索引向前遍历&#xff0c;找第一个不是utf16编码的字符&#xf…...

centos7上hive3.1.3安装及配置

1、安装背景&#xff1b; hive是基于hadoop的数据仓库软件&#xff0c;部署运行在linux系统之上&#xff0c;安装之前必须保证hadoop环境运行正常&#xff0c;hive本身不是分布式软件&#xff0c;它的分布式主要是借助hadoop实现&#xff0c;存储是hdfs&#xff0c;计算是mapr…...

Redis面试题(笔记)

目录 1.缓存穿透 2.缓存击穿 3.缓存雪崩 小结 4.缓存-双写一致性 5.缓存-持久性 6.缓存-数据过期策略 7.缓存-数据淘汰策略 数据淘汰策略-使用建议 数据淘汰策略总结 8.redis分布式锁 setnx redission 主从一致性 9.主从复制、主从同步 10.哨兵模式 服务状态监…...

iPhone 15 Pro展示设计:7项全新变化呈现

我们不应该再等iPhone 15 Pro在苹果9月12日的“Wonderlust”活动上发布了&#xff0c;而且可能会有很多升级。有传言称&#xff0c;iPhone 15 Pro将是自iPhone X以来最大的飞跃&#xff0c;这要归功于大量的新变化&#xff0c;从带有更薄边框的新钛框架到顶级A17仿生芯片和动作…...

【六袆 - Windows】PL/SQL instantclient安装包下载;PL/SQL双击登录配置

安装 PL/SQL 15 OMIT Oracle Instant Client Downloads for Microsoft Windows (x64) 64-bit https://www.oracle.com/database/technologies/instant-client/winx64-64-downloads.html 配置 # tnsnames.ora Network Configuration File:E:\oracle\product\10.2.0\db_1\ne…...

Springboot+mybatis-plus+dynamic-datasource 切换数据源失败问题总结

Springbootmybatis-plusdynamic-datasourceDruid 多数据源 切换数据源失败总结 文章目录 Springbootmybatis-plusdynamic-datasourceDruid 多数据源 切换数据源失败总结0.前言1. dynamic-datasource 切换数据源失败场景总结1. spring-batch整合情况下切换数据源异常解决办法&am…...

QuantLib学习笔记——InterestRate的应用

⭐️ 单利还是复利 巴菲特老爷子有句名言&#xff1a;“人生就像滚雪球&#xff0c;重要的是发现很湿的雪和很长的坡。” 很湿的雪&#xff0c;指的就是复利。很长的坡&#xff0c;指的就是时间。很湿的雪和很长的坡组合起来&#xff0c;就能滚成巨大的雪球。 哈哈&#xff0…...

记录--解决前端内存泄漏:问题概览与实用解决方案

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 内存泄漏是前端开发中的一个常见问题&#xff0c;可能导致项目变得缓慢、不稳定甚至崩溃。在本文中&#xff0c;我们将深入探讨在JavaScript、Vue和React项目中可能导致内存泄漏的情况&#xff0c;并提…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析

LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...