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 本题可以用双指针做,求出每一列能盛的雨水,再相加即可。不过暴力法会超时,需要优化。 双指针(暴力): 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.前言 图床作为图片集中存放的服务网站,可以看做是云存储的一部分,既可…...
【MySQL系列】-ORDER BY……HAVING详解及limit
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
浅析Keil MDK下串行Flash的下载算法设计
浅析Keil MDK下串行Flash的下载算法设计-电子发烧友网 今天给大家介绍的是 Keil MDK 工具下 i.MXRT 的串行 NOR Flash 下载算法设计。 在 i.MXRT 硬件那些事系列之《在串行 NOR Flash XIP 调试原理》一文中,痞子衡简单提了一下串行 NOR Flash 下载算法的概念&…...
springboot自动装配原理,手写一个starter。
文章目录 springboot自动装配原理手写starter手写starter总结: springboot自动装配原理 口述: springboot自动装配的话它其实就是只需要我们添加一个starter起步依赖,它就能完成这个依赖组件相关Bean的自动注入,其实就是自动的将…...
革命性的电子元件:RAD继电器 | 百能云芯
在现代电子和通信系统中,RAD继电器是一种关键的电子元件,它在各种应用中发挥着重要作用。RAD继电器(Reed-relay Actuated Device)是一种基于磁性原理的电子开关,其特点是极其高速、可靠、低功耗和长寿命。下面云芯将为…...
文献阅读: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…...
巨人互动|游戏出海游戏出海效果怎样?
游戏出海是指将原本面向国内市场的游戏产品进行调整和优化,以适应海外市场的需求,并进行推广和销售。下面小编讲讲关于游戏出海对于游戏效果的影响的一些讨论点。 1、市场扩大 通过游戏出海,可以将游戏产品的目标受众从国内扩展到全球范围内…...
二、GoLang输出HelloWorld、变量定义、数据类型的转换
一、输入Hello World go语言中,想要输出内容到控制台,package必须是main,包括方法名也必须是main, go语言输出的语法是 fmt 库。 package mainimport "fmt"func main() {// go语言中 输出内容 使用的库是 fmt库fmt.Pr…...
Mars3d图层树//图层管理加载时设置默认折叠的状态
问题:Mars3d图层树//图层管理加载时设置默认折叠的状态。 设置参考: 有个参数 open:false,写在对应的图层配置下,比如某个节点不展示,就对这个节点配置下。 如果全局,可以搜下这个widget内的代码ÿ…...
区块链技术|DApp与传统应用程序的关键区别
在数字时代,应用程序已经成为我们生活的一部分,无论是社交媒体、金融服务还是娱乐媒体,应用程序几乎无处不在。然而,随着区块链技术的崭露头角,一种新型应用程序——去中心化应用程序(DApp)正在…...
Python 加密解密技巧大揭秘:让你的数据安全无忧
建议食用原文链接效果更佳 Python 加密解密技巧大揭秘:让你的数据安全无忧 今天我们将探讨在 Python 中常见的加密解密算法,并通过代码案例来帮助大家更好地理解它们的实现。 在开始之前,请确保您已经安装了 pycryptodome 这个库。您可以使用…...
C#判断字符是否为utf16编码
unity截取显示微信昵称后,出现异常Error: UTF-16 to UTF-8 conversion failed because the input string is invalid,原因是截取字符串刚好截到了表情后面,解决思路是从截取到的索引向前遍历,找第一个不是utf16编码的字符…...
centos7上hive3.1.3安装及配置
1、安装背景; hive是基于hadoop的数据仓库软件,部署运行在linux系统之上,安装之前必须保证hadoop环境运行正常,hive本身不是分布式软件,它的分布式主要是借助hadoop实现,存储是hdfs,计算是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”活动上发布了,而且可能会有很多升级。有传言称,iPhone 15 Pro将是自iPhone X以来最大的飞跃,这要归功于大量的新变化,从带有更薄边框的新钛框架到顶级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的应用
⭐️ 单利还是复利 巴菲特老爷子有句名言:“人生就像滚雪球,重要的是发现很湿的雪和很长的坡。” 很湿的雪,指的就是复利。很长的坡,指的就是时间。很湿的雪和很长的坡组合起来,就能滚成巨大的雪球。 哈哈࿰…...
记录--解决前端内存泄漏:问题概览与实用解决方案
这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助 内存泄漏是前端开发中的一个常见问题,可能导致项目变得缓慢、不稳定甚至崩溃。在本文中,我们将深入探讨在JavaScript、Vue和React项目中可能导致内存泄漏的情况,并提…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...
