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

我们看到题的第一步,永远是对入参进行判断
public int trap(int[] height) {if (height == null) {return 0;}...}
但是我们想想看,接雨水是不是和往桶里倒水的问题很像,倒入水的体积往往是由桶两边较低的那个高度决定的,这个问题亦是如此



由我们分析可知当数组的长度小于3的时候,是不可能接到雨水的,所以我们在判断入参条件的时候就可以这样写
public int trap(int[] height) {if (height == null || height.length < 3) {return 0;}...}
刚才我们已经分析过了,一个位置的存储量只和最短的那一边有关系,边越长,我们固定位置上的存储量就越多,所以我们可以遍历每个位置,分别计算出各个位置上的存储量,再最后求和就完美的解决了本题
int count = 0;for (int i = 1; i < height.length; i++) {//找左边的最高值int lMax = 0;for (int j = 0; j < i; j++) {lMax = Math.max(lMax, height[j]);}//找到右边的最高值int rMax = 0;for (int j = i + 1; j < height.length; j++) {rMax = Math.max(rMax, height[j]);}}
好了,这样我们相对位置上的两边最高的边已经求出来了,只不过现在还存一个问题,如果,当前位置的高度如果大于较小的那边高度的话,是否还可有存储水量呢?

所以当前位置的高度如果大于两边最长的相对较小的边的高度,则不能进行存储水量,所以我们再对我们的代码进行完善
int count = 0;for (int i = 1; i < height.length; i++) {//找左边的最高值int lMax = 0;for (int j = 0; j < i; j++) {lMax = Math.max(lMax, height[j]);}//找到右边的最高值int rMax = 0;for (int j = i + 1; j < height.length; j++) {rMax = Math.max(rMax, height[j]);}if (Math.min(lMax, rMax) - height[i] > 0) {count += Math.min(lMax, rMax) - height[i];}}
这就完成了我们所谓hard题的接雨水问题了,这个题面试中还是经常问的,希望大家透析原理,面试无压力,下面给大家奉上整个代码,供大家参考借鉴
public int trap(int[] height) {if (height == null || height.length < 3) {return 0;}int count = 0;for (int i = 1; i < height.length; i++) {//找左边的最高值int lMax = 0;for (int j = 0; j < i; j++) {lMax = Math.max(lMax, height[j]);}//找到右边的最高值int rMax = 0;for (int j = i + 1; j < height.length; j++) {rMax = Math.max(rMax, height[j]);}if (Math.min(lMax, rMax) - height[i] > 0) {count += Math.min(lMax, rMax) - height[i];}}return count;}
相关文章:
面试热题(接雨水问题)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 我们看到题的第一步,永远是对入参进行判断 public int trap(int[] height) {if (height null) {return 0;}...} 但是我们想想看,接…...
Meta AI研究团队新AI模型: Llama 2 大语言模型
Llama是Facebook Research团队开发的基础语言模型集,旨在提供广泛的语言理解能力。它基于转换器架构,参数范围从7B到65B。通过使用Llama模型,研究人员和开发人员可以构建更先进的自然语言处理系统。您可以在GitHub上找到相关的代码和资源&…...
CSS水平垂直居中
1.利用定位 margin:auto 2.flex布局 3.grid布局 一、利用positionmargin:auto <style>.outer {position: relative; /*父亲相对定位*/width: 200px;height: 200px;background-color: red;}.inner {position: absolute; /*儿子绝对定位*/top: 0;bottom: 0;left: 0;ri…...
Yolov8-pose关键点检测:模型部署篇 | yolov8-pose.onnx python推理
💡💡💡本文解决什么问题:Yolov8-pose关键点训练得到的模型转换成onnx格式在python下完成推理 Yolov8-Pose关键点检测专栏介绍:https://blog.csdn.net/m0_63774211/category_12398833.html ✨✨✨手把手教你从数据标记到生成适合Yolov8-pose的yolo数据集; 🚀🚀�…...
Linux中提示No such file or directory解决方法
说明: 在linux下,./xxx.sh执行shell脚本时会提示No such file or directory。但shell明明存在,为什么就是会提示这个呢? 这种其实是因为编码方式不对,如你在win下编辑sh,然后直接复制到linux下面 实现&…...
Sklearn-使用SVC对iris数据集进行分类
Sklearn-使用SVC对iris数据集进行分类 iris数据集的加载训练svc模型输出混淆矩阵和分类报告使用Pipeline管道完成固定操作不使用Pipeline使用Pipeline 使用SVC对iris数据集进行分类预测 涉及内容包含: 数据集的加载,训练集和测试集的划分训练svc模型,对测试集的预测…...
项目经理必读:领导风格对项目成功的关键影响
引言 项目经理作为一个领导者的角色,他们需要协调各方资源,管理团队,推动项目的进行。为了完成这些任务,项目经理必须具备各种领导风格的灵活性,以应对项目中的各种变数和挑战。在这篇文章中,我们将讨论领…...
行业追踪,2023-08-04
自动复盘 2023-08-04 凡所有相,皆是虚妄。若见诸相非相,即见如来。 k 线图是最好的老师,每天持续发布板块的rps排名,追踪板块,板块来开仓,板块去清仓,丢弃自以为是的想法,板块去留让…...
双链表(带哨兵位头节点)
目录 编辑 双链表的初始化: 双链表的打印: 双链表的尾插: 双链表的头插: 双链表的尾删: 双链表的头删: 双链表pos位置之前的插入: 双链表pos位置的删除: 关于顺序表和链表…...
MySQL - LOAD DATA LOCAL INFILE将数据导入表中和 INTO OUTFILE (速度快)
文章目录 一、语法介绍二、数据分隔符介绍 :换行符说明: 三、示例LOAD DATA LOCAL INFILEINTO OUTFILE 总结 一、语法介绍 LOAD DATA[LOW_PRIORITY | CONCURRENT] [LOCAL]INFILE file_name[REPLACE | IGNORE]INTO TABLE tbl_name[PARTITION (partition_name [, par…...
String ,StringBulider ,StringBuffer
面试指北149 知乎 StringBuffer和StringBuilder区别详解(Java面试)_stringbuffer和stringbuilder的区别_辰兮要努力的博客-CSDN博客...
阶段总结(linux基础)
目录 一、初始linux系统 二、基本操作命令 三、目录结构 四、文件及目录管理命令 查看文件内容 创建文件 五、用户与组管理 六、文件权限与压缩管理 七、磁盘管理 八、系统程序与进程管理 管理机制 文件系统损坏 grub引导故障 磁盘资源耗尽 程序与进程的区别 查…...
HTTP(超文本传输协议)学习
关于HTTP补学 一、HTTP能干什么 通过下图能够直观的看出:“交换数据 ” 二、HTTP请求例子 一个 HTTP 方法,通常是由一个动词,像 GET、POST 等,或者一个名词,像 OPTIONS、HEAD 等,来定义客户端执行的动作。…...
23年7月工作笔记整理(前端)
目录 一、js相关二、业务场景学习 一、js相关 1.js中Number类型的最大值常量:Number.MAX_VALUE,最小值常量:Number.MIN_VALUE 2.巩固一下reduce语法:reduce(function(初始值或方法的返回值,当前值,当前值的索引,要累加的初始值))…...
pytorch学习——正则化技术——权重衰减
一、概念介绍 权重衰减(Weight Decay)是一种常用的正则化技术,它通过在损失函数中添加一个惩罚项来限制模型的复杂度,从而防止过拟合。 在训练参数化机器学习模型时, 权重衰减(weight decay)是…...
iTOP-RK3588开发板Ubuntu 系统交叉编译 Qt 工程-命令行交叉编译
使用源码 rk3588_linux/buildroot/output/rockchip_rk3588/host/bin/qmake 交叉编译 QT 工程。 最后烧写编译好的 buildroot 镜像,将编译好的 QT 工程可执行程序在 buildroot 系统上运行。 交叉编译 QT 工程如下所示,首先进入 QLed 的工程目录下。 然后…...
Java进阶——数据结构与算法之哈希表与树的入门小结(四)
文章大纲 引言一、哈希表1、哈希表概述2、哈希表的基本设计思想3、JDK中的哈希表的设计思想概述 二、树1、树的概述2、树的特点3、树的相关术语4、树的存储结构4.1、双亲表示法4.2、孩子兄弟表示法:4.3、孩子表示法:4.4、双亲孩子表示法 三、二叉树1、二…...
DataFrame中按某字段分类并且取该分类随机数量的数据
最近有个需求,把某个df中的数据,按照特定字段分类,并且每个分类只取随机数量数据,这个随机数量需要有范围限制。写出来记录下。 def randomCutData(self, df, startNum):grouped df.groupby(classify_label)df_sampled pd.Data…...
【c++】rand()随机函数的应用(一)——rand()函数详解和实例
c语言中可以用rand()函数生成随机数,今天来探讨一下rand()函数的基本用法和实际应用。 本系列文章共分两讲,今天主要介绍一下伪随机数生成的原理,以及在伪随机数生成的基础上,生成随机数的技巧,下一讲主要介绍无重复随…...
iOS——Block回调
先跟着我实现最简单的 Block 回调传参的使用,如果你能举一反三,基本上可以满足了 OC 中的开发需求。已经实现的同学可以跳到下一节。 首先解释一下我们例子要实现什么功能(其实是烂大街又最形象的例子): 有两个视图控…...
Nunchaku-flux-1-dev环境部署详解:Anaconda虚拟环境与依赖管理
Nunchaku-flux-1-dev环境部署详解:Anaconda虚拟环境与依赖管理 想试试最近挺火的Nunchaku-flux-1-dev模型,结果第一步就被环境依赖给卡住了?这太正常了。不同模型、不同版本的库之间打架,是每个搞AI开发的人都绕不开的坎。今天咱…...
【仅限首批参会者披露】SITS2026圆桌闭门纪要:5家头部AI企业未公开的工程化SOP与3个反直觉降本技巧
第一章:SITS2026圆桌:大模型工程化的挑战与机遇 2026奇点智能技术大会(https://ml-summit.org) 大模型工程化已从实验室原型阶段迈入规模化生产部署的关键转折点。在SITS2026圆桌讨论中,来自Meta、阿里云、Hugging Face及多家AI基建初创公司…...
从零开始学习GDScript编程:在浏览器中免费掌握Godot游戏开发语言
从零开始学习GDScript编程:在浏览器中免费掌握Godot游戏开发语言 【免费下载链接】learn-gdscript Learn Godots GDScript programming language from zero, right in your browser, for free. 项目地址: https://gitcode.com/gh_mirrors/le/learn-gdscript …...
显示器“刷新率”的实战选择指南
1. 刷新率的基础认知:从翻书动画到电竞屏 第一次接触"刷新率"这个概念时,我正对着两台显示器纠结不已。左边是标注着60Hz的普通办公屏,右边是144Hz的电竞显示器,价格相差三倍。销售员反复强调"高刷屏更流畅"&…...
如何为ThinkPad T480安装macOS:OpenCore完整配置指南
如何为ThinkPad T480安装macOS:OpenCore完整配置指南 【免费下载链接】t480-oc 💻 Lenovo ThinkPad T480 / T580 / X280 Hackintosh (macOS Monterey 12.x - Sequoia 15.x) - OpenCore 项目地址: https://gitcode.com/gh_mirrors/t4/t480-oc 还在…...
婚恋平台用户画像优化:GPEN提升头像吸引力与真实性
婚恋平台用户画像优化:GPEN提升头像吸引力与真实性 1. 项目背景与核心价值 在婚恋社交平台中,用户头像的质量直接影响第一印象和匹配成功率。模糊、低质或失真的头像往往导致用户信任度下降和互动率降低。传统的美颜工具虽然能调整肤色和轮廓ÿ…...
Apex压枪宏终极指南:如何快速提升射击精度与稳定性
Apex压枪宏终极指南:如何快速提升射击精度与稳定性 【免费下载链接】Apex-NoRecoil-2021 Scripts to reduce recoil for Apex Legends. (auto weapon detection, support multiple resolutions) 项目地址: https://gitcode.com/gh_mirrors/ap/Apex-NoRecoil-2021 …...
FRCRN常见错误代码排查手册:从403 Forbidden到CUDA错误
FRCRN常见错误代码排查手册:从403 Forbidden到CUDA错误 部署和使用FRCRN进行语音降噪时,遇到各种报错是常有的事。这些错误信息往往让人一头雾水,从网络权限的“403 Forbidden”到让人头疼的CUDA问题,每一个都可能让你卡上半天。…...
Steam Achievement Manager完整指南:轻松管理你的Steam游戏成就
Steam Achievement Manager完整指南:轻松管理你的Steam游戏成就 【免费下载链接】SteamAchievementManager A manager for game achievements in Steam. 项目地址: https://gitcode.com/gh_mirrors/st/SteamAchievementManager 你是否曾经因为游戏BUG导致成就…...
从一次“翻车”的漏洞复现说起:记CVE-2018-7490中那个找不到的/tmp/flag
从一次“翻车”的漏洞复现说起:CVE-2018-7490排查实录 那天下午,我像往常一样打开Vulfocus靶场,准备复现uWSGI目录穿越漏洞(CVE-2018-7490)。这个漏洞在安全圈已经讨论多年,原理清晰明了——通过构造特殊的…...
