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

面试热题(接雨水问题)

       给定 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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 我们看到题的第一步&#xff0c;永远是对入参进行判断 public int trap(int[] height) {if (height null) {return 0;}...} 但是我们想想看&#xff0c;接…...

Meta AI研究团队新AI模型: Llama 2 大语言模型

Llama是Facebook Research团队开发的基础语言模型集&#xff0c;旨在提供广泛的语言理解能力。它基于转换器架构&#xff0c;参数范围从7B到65B。通过使用Llama模型&#xff0c;研究人员和开发人员可以构建更先进的自然语言处理系统。您可以在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解决方法

说明&#xff1a; 在linux下&#xff0c;./xxx.sh执行shell脚本时会提示No such file or directory。但shell明明存在&#xff0c;为什么就是会提示这个呢&#xff1f; 这种其实是因为编码方式不对&#xff0c;如你在win下编辑sh&#xff0c;然后直接复制到linux下面 实现&…...

Sklearn-使用SVC对iris数据集进行分类

Sklearn-使用SVC对iris数据集进行分类 iris数据集的加载训练svc模型输出混淆矩阵和分类报告使用Pipeline管道完成固定操作不使用Pipeline使用Pipeline 使用SVC对iris数据集进行分类预测 涉及内容包含&#xff1a; 数据集的加载,训练集和测试集的划分训练svc模型,对测试集的预测…...

项目经理必读:领导风格对项目成功的关键影响

引言 项目经理作为一个领导者的角色&#xff0c;他们需要协调各方资源&#xff0c;管理团队&#xff0c;推动项目的进行。为了完成这些任务&#xff0c;项目经理必须具备各种领导风格的灵活性&#xff0c;以应对项目中的各种变数和挑战。在这篇文章中&#xff0c;我们将讨论领…...

行业追踪,2023-08-04

自动复盘 2023-08-04 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…...

双链表(带哨兵位头节点)

目录 ​编辑 双链表的初始化&#xff1a; 双链表的打印&#xff1a; 双链表的尾插&#xff1a; 双链表的头插&#xff1a; 双链表的尾删&#xff1a; 双链表的头删&#xff1a; 双链表pos位置之前的插入&#xff1a; 双链表pos位置的删除&#xff1a; 关于顺序表和链表…...

MySQL - LOAD DATA LOCAL INFILE将数据导入表中和 INTO OUTFILE (速度快)

文章目录 一、语法介绍二、数据分隔符介绍 :换行符说明&#xff1a; 三、示例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区别详解&#xff08;Java面试&#xff09;_stringbuffer和stringbuilder的区别_辰兮要努力的博客-CSDN博客...

阶段总结(linux基础)

目录 一、初始linux系统 二、基本操作命令 三、目录结构 四、文件及目录管理命令 查看文件内容 创建文件 五、用户与组管理 六、文件权限与压缩管理 七、磁盘管理 八、系统程序与进程管理 管理机制 文件系统损坏 grub引导故障 磁盘资源耗尽 程序与进程的区别 查…...

HTTP(超文本传输协议)学习

关于HTTP补学 一、HTTP能干什么 通过下图能够直观的看出&#xff1a;“交换数据 ” 二、HTTP请求例子 一个 HTTP 方法&#xff0c;通常是由一个动词&#xff0c;像 GET、POST 等&#xff0c;或者一个名词&#xff0c;像 OPTIONS、HEAD 等&#xff0c;来定义客户端执行的动作。…...

23年7月工作笔记整理(前端)

目录 一、js相关二、业务场景学习 一、js相关 1.js中Number类型的最大值常量&#xff1a;Number.MAX_VALUE&#xff0c;最小值常量&#xff1a;Number.MIN_VALUE 2.巩固一下reduce语法&#xff1a;reduce(function(初始值或方法的返回值,当前值,当前值的索引,要累加的初始值))…...

pytorch学习——正则化技术——权重衰减

一、概念介绍 权重衰减&#xff08;Weight Decay&#xff09;是一种常用的正则化技术&#xff0c;它通过在损失函数中添加一个惩罚项来限制模型的复杂度&#xff0c;从而防止过拟合。 在训练参数化机器学习模型时&#xff0c; 权重衰减&#xff08;weight decay&#xff09;是…...

iTOP-RK3588开发板Ubuntu 系统交叉编译 Qt 工程-命令行交叉编译

使用源码 rk3588_linux/buildroot/output/rockchip_rk3588/host/bin/qmake 交叉编译 QT 工程。 最后烧写编译好的 buildroot 镜像&#xff0c;将编译好的 QT 工程可执行程序在 buildroot 系统上运行。 交叉编译 QT 工程如下所示&#xff0c;首先进入 QLed 的工程目录下。 然后…...

Java进阶——数据结构与算法之哈希表与树的入门小结(四)

文章大纲 引言一、哈希表1、哈希表概述2、哈希表的基本设计思想3、JDK中的哈希表的设计思想概述 二、树1、树的概述2、树的特点3、树的相关术语4、树的存储结构4.1、双亲表示法4.2、孩子兄弟表示法&#xff1a;4.3、孩子表示法&#xff1a;4.4、双亲孩子表示法 三、二叉树1、二…...

DataFrame中按某字段分类并且取该分类随机数量的数据

最近有个需求&#xff0c;把某个df中的数据&#xff0c;按照特定字段分类&#xff0c;并且每个分类只取随机数量数据&#xff0c;这个随机数量需要有范围限制。写出来记录下。 def randomCutData(self, df, startNum):grouped df.groupby(classify_label)df_sampled pd.Data…...

【c++】rand()随机函数的应用(一)——rand()函数详解和实例

c语言中可以用rand()函数生成随机数&#xff0c;今天来探讨一下rand()函数的基本用法和实际应用。 本系列文章共分两讲&#xff0c;今天主要介绍一下伪随机数生成的原理&#xff0c;以及在伪随机数生成的基础上&#xff0c;生成随机数的技巧&#xff0c;下一讲主要介绍无重复随…...

iOS——Block回调

先跟着我实现最简单的 Block 回调传参的使用&#xff0c;如果你能举一反三&#xff0c;基本上可以满足了 OC 中的开发需求。已经实现的同学可以跳到下一节。 首先解释一下我们例子要实现什么功能&#xff08;其实是烂大街又最形象的例子&#xff09;&#xff1a; 有两个视图控…...

Steam游戏DLC完整解锁指南:3步掌握SmokeAPI终极技巧

Steam游戏DLC完整解锁指南&#xff1a;3步掌握SmokeAPI终极技巧 【免费下载链接】SmokeAPI Legit DLC Unlocker for Steamworks 项目地址: https://gitcode.com/gh_mirrors/smo/SmokeAPI 你是否曾看着心爱的游戏DLC列表&#xff0c;却因预算有限而望而却步&#xff1f;或…...

3个关键步骤:如何用XXMI启动器统一管理多款热门游戏模组

3个关键步骤&#xff1a;如何用XXMI启动器统一管理多款热门游戏模组 【免费下载链接】XXMI-Launcher Modding platform for GI, HSR, WW and ZZZ 项目地址: https://gitcode.com/gh_mirrors/xx/XXMI-Launcher 你是否曾经为不同游戏的模组管理感到头疼&#xff1f;每个游…...

EldenRingSaveCopier:终极艾尔登法环存档迁移指南,告别进度丢失烦恼

EldenRingSaveCopier&#xff1a;终极艾尔登法环存档迁移指南&#xff0c;告别进度丢失烦恼 【免费下载链接】EldenRingSaveCopier 项目地址: https://gitcode.com/gh_mirrors/el/EldenRingSaveCopier 你是否曾因更换电脑或重装系统而担心辛苦打拼的艾尔登法环游戏进度…...

TranslucentTB完全指南:免费实现Windows任务栏透明化与个性化定制

TranslucentTB完全指南&#xff1a;免费实现Windows任务栏透明化与个性化定制 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB Translucen…...

动手学深度学习——数据集

1. 前言在前面的内容中&#xff0c;我们已经学习了&#xff1a;什么是物体检测什么是边界框边界框如何表示目标的位置但是&#xff0c;仅仅理解这些概念还不够。 如果想真正训练一个物体检测模型&#xff0c;我们还必须解决一个核心问题&#xff1a;训练数据从哪里来&#xff1…...

Sunshine终极指南:5个步骤搭建你的免费游戏串流服务器

Sunshine终极指南&#xff1a;5个步骤搭建你的免费游戏串流服务器 【免费下载链接】Sunshine Self-hosted game stream host for Moonlight. 项目地址: https://gitcode.com/GitHub_Trending/su/Sunshine 想要在客厅电视、平板电脑甚至手机上流畅玩PC大作吗&#xff1f;…...

我让 Claude 和 Codex 同时审计 个模块,它们只在 个上达成共识凹

整体排查思路 我们的目标是验证以下三个环节是否正常&#xff1a; 登录成功时&#xff1a;服务器是否正确生成了Session并返回了包含正确 JSESSIONID的Cookie给浏览器。 浏览器端&#xff1a;浏览器是否成功接收并存储了该Cookie。 后续请求&#xff1a;浏览器在执行查询等操作…...

TikTok爆火C语言创意:电脑无硬件发无线电,靠谱吗?

一、刷爆TikTok的技术神操作&#xff0c;无硬件也能发无线电&#xff1f; 2026年3月17日&#xff0c;有一条C语言创意短视频&#xff0c;它刷爆了TikTok&#xff0c;在单日的时候&#xff0c;斩获了10万以上的播放量&#xff0c;以及5万以上的点赞量。并且它登顶了当日C语言创…...

Python 快速上手 Telegram Bot:从零到一的实战指南

1. 为什么选择Python开发Telegram Bot&#xff1f; Telegram Bot就像是你安插在Telegram里的一个24小时待命的智能助手。它能自动回复消息、处理订单、推送新闻&#xff0c;甚至陪你玩文字游戏。而Python凭借其简洁的语法和丰富的库生态&#xff0c;成为了开发Telegram Bot的首…...

AI让Verilog入门不再劝退,但芯片工程师真的轻松了吗?

还记得第一次写Verilog的感觉吗&#xff1f;明明只是想让一个LED灯闪烁&#xff0c;却要先声明一堆wire、reg&#xff0c;搞清楚阻塞赋值和非阻塞赋值的区别&#xff0c;再纠结always块里该用还是<。现在的情况完全不同了。新入行的工程师可以直接对AI说&#xff1a;"帮…...