LeetCode42.接雨水

这道题呢可以按列来累加,就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度,我想到了这里然后就想第i列的水其实就是第i-1列和i+1列中最小的高度减去第i列的高度,但是其实并不是,比如示例中的第5列,他的告诉是0左右两边是1,但水是2,然后看题解了。
第i列的水其实与第i-1列和i+1列的水并没有关系,而是和第i列左边所有柱子中最高的和第i列右边所有柱子中最高的有关
当第i列左右两边的最高柱子中较矮的比第i列要高,那么第i列能装的水就是较矮的高度-第i列的高度。如果左右两边最高的柱子都比第i列的柱子矮的话,那么第i列能装的水就是0。所以算出每一列能装的水然后全部加起来就是能接到的雨水,以下的代码:
class Solution {public int trap(int[] height) {int n = height.length;int ans = 0;for(int i =1;i<n-1;i++){int leftMaxHeight =0;for(int j =i-1;j>=0;j--){if(height[j] > leftMaxHeight)leftMaxHeight=height[j];}int rightMaxHeight =0;for(int k =i+1;k<n;k++){if(height[k] > rightMaxHeight)rightMaxHeight=height[k];}int min = Math.min(rightMaxHeight, leftMaxHeight);ans+= min > height[i] ? min-height[i] : 0;}return ans;}
}
这个算法每次都要找出某一列左边的最高的柱子和右边的最高柱子,就多了一层循环,算法还可以优化,创建一个left_max数组和right_max数组,left_max[i]表示第i列左边的最高的柱子,right_max[i]同理。用动态规划的方法来填充这两个数组。
left_max[i] = Math,max(left_max[i-1] ,height[i-1]);就是说第i列左边最高的柱子是第i-1列左边的最高柱子第i-1列的高度的最大值,right_max[i]同理。以下是代码:
public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}
相关文章:
LeetCode42.接雨水
这道题呢可以按列来累加,就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度,我想到了这里然后就想第i列的水其实就是第i-1列和i1列中最小的高度减去第i列的高度,但是其实并不是,比如示例中的第5…...
优化时间流:区间调度问题的探索与解决
在浩如烟海的信息时代,时间的有效管理成为了一门不可或缺的艺术。无论是生活中的琐事,还是工作中的任务,时间都在无声地流逝,挑战着我们的智慧。正如时间在日常生活中具有的宝贵价值一样,在计算机科学领域,…...
【Python】强化学习:原理与Python实战
搞懂大模型的智能基因,RLHF系统设计关键问答 RLHF(Reinforcement Learning with Human Feedback,人类反馈强化学习)虽是热门概念,并非包治百病的万用仙丹。本问答探讨RLHF的适用范围、优缺点和可能遇到的问题ÿ…...
设计模式——合成复用原则
文章目录 合成复用原则设计原则核心思想合成案例聚合案例继承案例优缺点 合成复用原则 原则是尽量使用合成/聚合的方式,而不是使用继承 设计原则核心思想 找出应用中可能需要变化之处,把它们独立出来,不要和那些不需要变化的代码混在一起。…...
基于OpenCV实战(基础知识一)
目录 简介 1.计算机眼中的图像 2.图片的读取、显示与保存 3.视频的读取与显示 简介 OpenCV是一个流行的开源计算机视觉库,由英特尔公司发起发展。它提供了超过2500个优化算法和许多工具包,可用于灰度、彩色、深度、基于特征和运动跟踪等的图像处理和…...
如何高效的接入第三方接口
作为程序员的我们,经常会接到领导的安排,接入某某的接口,方面我们如何如何, 例如:领导在1号时给作为员工的你说,最近系统需要增加一个新的支付方式,一会和对方技术组建一个群,有什么问题,可以直接在群里说,最近还说,尽快接入,客户等着用,让你在5号前,完成接入工…...
docker pip下载依赖超时或失败问题解决
Docker容器使用pip安装Python库时超时,可能是由于多种原因。以下是一些建议和解决方法: 使用国内镜像源: 如果你位于中国,可以尝试更换到国内的镜像源。例如,可以使用阿里云、腾讯云、清华大学提供的镜像。 你可以在Dockerfile中添…...
python并发编程
一、程序提速的方法 二、python对并发编程的支持 多线程:threading,利用CPU和IO可以同时执行的原理,让CPU不会干巴巴等待IO完成;多进程:multiprocess,利用多核CPU的能力,真正的并行执行任务&am…...
【面试题】:前端怎么实现权限设计及遇到的bug
一.权限的概念 前端权限分为页面权限、按钮权限、API权限。 二.页面权限的实现过程 ①用户登录进去调用获取用户信息接口,后端会给我们返回一个权限标识符 ②在获取到数据之后,我们就要判断用户能访问到哪些页面,我们可以在vuex中permission模块中的action…...
Vue 2 插槽
可以先阅读组件基础-简单了解通过插槽分发内容。 一、插槽定义 插槽将子组件标签间的内容分发到子组件模板的<slot>标签位置。 如果没有<slot>标签,那么该内容将被丢弃。 二、编译作用域 内容在哪个作用域编译,就可以访问哪个作用域的数据…...
Spring 容器启动耗时统计
为了了解 Spring 为什么会启动那么久,于是看了看怎么统计一下加载 Bean 的耗时。 极简版 几行代码搞定。 import org.springframework.beans.BeansException; import org.springframework.beans.factory.config.BeanPostProcessor;import java.util.HashMap; imp…...
1. 优化算法学习
参考文献 1609:An overview of gradient descent optimization algorithms 从 SGD 到 Adam —— 深度学习优化算法概览(一) - 知乎 机器学习札记 - 知乎...
再获荣誉丨通付盾WAAP解决方案获“金鼎奖”优秀金融科技解决方案
今年四月,2023中国国际金融展在首钢会展中心成功落下帷幕。中国国际金融展作为金融开放创新成果的展示、交流、传播平台,历经多年发展,已成为展示中国金融发展成就、宣传金融改革成果、促进金融产业创新和推动金融信息化发展的有效平台。 “金鼎奖”评选…...
【腾讯云 TDSQL-C Serverless 产品测评】“橡皮筋“一样的数据库『MySQL高压篇』
【腾讯云 TDSQL-C Serverless 产品测评】"橡皮筋"一样的数据库 活动介绍服务一览何为TDSQL ?Serverless 似曾相识? 降本增效,不再口号?动手环节 --- "压力"山大实验前瞻稍作简介资源扩缩范围(CCU&…...
python http文件上传
server端代码 import os import cgi from http.server import SimpleHTTPRequestHandler, HTTPServer# 服务器地址和端口 host = 0.0.0.0 port = 8080# 处理文件上传的请求 class FileUploadHandler(SimpleHTTPRequestHandler):def do_POST(self):# 解析多部分表单数据form = …...
Android学习之路(9) Intent
Intent 是一个消息传递对象,您可以用来从其他应用组件请求操作。尽管 Intent 可以通过多种方式促进组件之间的通信,但其基本用例主要包括以下三个: 启动 Activity Activity 表示应用中的一个屏幕。通过将 Intent 传递给 startActivity()&…...
vue项目配置git提交规范
vue项目配置git提交规范 一、背景介绍二、husky、lint-staged、commitlint/cli1.husky2.lint-staged3.commitlint/cli 三、具体使用1.安装依赖2.运行初始化脚本3.在package.json中配置lint-staged4.根目录新增 commitlint.config.js 4.提交测试1.提示信息格式错误时2.eslint校验…...
影响交叉导轨运行速度的因素有哪些?
交叉导轨具有精度高,速度快,承载能力大、结构简单等特点,被广泛应用在固晶机、点胶设备、自动化设备、OA机器及其周边机器、测定器、印刷基板开孔机,精密机器,光学测试仪、光学工作台、操纵机构、X 射缐装置等的滑座部…...
List转Map
一、list转map Map<Long, User> maps userList.stream().collect(Collectors.toMap(User::getId,Function.identity())); 看来还是使用JDK 1.8方便一些。 二、另外,转换成map的时候,可能出现key一样的情况,如果不指定一个覆盖规则&…...
ES:一次分片设计问题导致的故障
### 现象: 1. 单节点CPU持续高 2.写入骤降 3.线程池队列积压,但没有reject 4.使用方没有记录日志 ### 排查 1.ES监控 只能看到相应的结果指标,无法反应出原因。 2.ES日志:大量日志打印相关异常(routate等调用栈&a…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
