当前位置: 首页 > 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;并提…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

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

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

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑

精益数据分析&#xff08;98/126&#xff09;&#xff1a;电商转化率优化与网站性能的底层逻辑 在电子商务领域&#xff0c;转化率与网站性能是决定商业成败的核心指标。今天&#xff0c;我们将深入解析不同类型电商平台的转化率基准&#xff0c;探讨页面加载速度对用户行为的…...