谷歌(Google)历年编程真题——接雨水
谷歌历年面试真题——数组和字符串系列真题练习。
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
思路一:双指针
这个问题可以使用双指针的方法来解决。具体步骤如下:
- 初始化左右指针
left
和right
,分别指向数组的第一个和最后一个元素。 - 初始化两个变量
left_max
和right_max
,分别表示左侧柱子的最大高度和右侧柱子的最大高度,初始值都为0。 - 使用循环遍历数组,当
left
指针小于等于right
指针时,执行以下步骤:- 如果
height[left] < height[right]
,表示左侧柱子较低,则计算当前位置的雨水量,并更新左侧最大高度left_max
。 - 否则,表示右侧柱子较低,则计算当前位置的雨水量,并更新右侧最大高度
right_max
。 - 在计算雨水量时,当前位置能够接的雨水量等于当前最小高度(
left_max
和right_max
中的较小值)与当前柱子高度之差。
- 如果
- 返回计算得到的总雨水量。
下面是相应的Python代码实现:
def trap(height):if not height:return 0left, right = 0, len(height) - 1left_max, right_max = 0, 0ans = 0while left <= right:if height[left] < height[right]:if height[left] >= left_max:left_max = height[left]else:ans += left_max - height[left]left += 1else:if height[right] >= right_max:right_max = height[right]else:ans += right_max - height[right]right -= 1return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出:6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2)) # 输出:9
这个函数使用双指针的方法,通过一次遍历就可以计算出雨水的总量。
思路二:栈
除了双指针的方法外,还可以使用栈来解决这个问题。具体步骤如下:
- 初始化一个栈
stack
和一个变量ans
,ans
用于记录接到的雨水量,初始值为0。 - 遍历数组
height
中的每一个柱子,依次执行以下操作:- 如果栈为空,或当前柱子高度小于等于栈顶柱子高度,则将当前柱子下标入栈。
- 否则,说明当前柱子可能会形成一个水池,将栈中元素逐个弹出,直到遇到柱子高度大于当前柱子高度的位置。每次弹出时,都计算当前柱子和栈顶柱子之间的距离,并根据距离和高度差计算雨水量,然后累加到
ans
中。 - 最后将当前柱子下标入栈。
- 遍历完成后,返回
ans
即为最终的雨水量。
下面是相应的 Python 代码实现:
def trap(height):stack = []ans = 0for i in range(len(height)):while stack and height[i] > height[stack[-1]]:top = stack.pop()if not stack:breakdistance = i - stack[-1] - 1bounded_height = min(height[i], height[stack[-1]]) - height[top]ans += distance * bounded_heightstack.append(i)return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出:6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2)) # 输出:9
这个函数使用栈的方法,通过一次遍历就可以计算出雨水的总量。
思路三:动态规划
除了双指针和栈的方法外,还可以使用动态规划来解决这个问题。具体步骤如下:
- 初始化两个数组
left_max
和right_max
,分别用于存储每个柱子左侧和右侧的最大高度。left_max[i]
表示第i
个柱子左侧(包括自身)的最大高度。right_max[i]
表示第i
个柱子右侧(包括自身)的最大高度。
- 遍历数组
height
,从左向右更新left_max
,从右向左更新right_max
。 - 遍历数组
height
,对于每个柱子,计算该位置上可以接到的雨水量,即min(left_max[i], right_max[i]) - height[i]
。 - 累加所有位置上的雨水量,即为最终的雨水总量。
下面是相应的 Python 代码实现:
def trap(height):n = len(height)if n == 0:return 0left_max = [0] * nright_max = [0] * n# 初始化 left_maxleft_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i - 1], height[i])# 初始化 right_maxright_max[n - 1] = height[n - 1]for i in range(n - 2, -1, -1):right_max[i] = max(right_max[i + 1], height[i])# 计算雨水量ans = 0for i in range(n):ans += min(left_max[i], right_max[i]) - height[i]return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出:6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2)) # 输出:9
这个函数使用动态规划的方法,通过三次遍历就可以计算出雨水的总量。
相关文章:

谷歌(Google)历年编程真题——接雨水
谷歌历年面试真题——数组和字符串系列真题练习。 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:…...

golang 归并回源策略
前言 下面是我根据业务需求画了一个架构图,没有特别之处,很普通,都是我们常见的中间件,都是一些幂等性GET 请求。有一个地方很有意思,从service 分别有10000 qps 请求到Redis,并且它们的key 是一样的。这样…...

【漏洞复现】可视化融合指挥调度平台 dispatch接口处存在任意文件上传漏洞
免责声明:文章来源互联网收集整理,请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失,均由使用者本人负责,所产生的一切不良后果与文章作者无关。该…...
最讨厌这种字符串问题了!!
题目:洛谷P1957口算练习题 题目大意描述: 第一行输入一个整数表示接下来要进行多少次运算,接下来每行输入一个字母c和两个数字x,y(输入的字母为a/b/c,分别表示要进行,-,*运算)或者就输入两个数…...

B-名牌赌王(本人遇到的题,做个笔记)
题解: #include <iostream> #include <queue> //需要用小根堆的优先队列 #include <unordered_map> //用无序映射 using namespace std; bool pai() {int n, m;cin >> n >> m; priority_queue<int, vector<int>, gr…...

博客评论回复03
接着之前写的,之前返回的数据集按道理来说渲染出来还是丑丑的,因此这次我看着抖音的评论样子,自己瞎写了一通,不过也算是模仿出来了虽然肯定没有抖音写的好。 类似与前面几章写的表结构 首先看看抖音评论区是怎么样的?…...

【【萌新的学习之Numpy数组的使用】】
萌新的学习之Numpy数组的使用 先记录一下之前的关于函数的设计 通过创造类的形式 复习完毕之后介绍numpy数组的使用 #整数型数组遇到除法 (即便是除以整数) 不同维度的数组之间 从外形上的本质区别 一维数组用1层中括号 二维数组用2层中括号 三维数…...

RabbitMQ3.13.x之七_RabbitMQ消息队列模型
RabbitMQ3.13.x之七_RabbitMQ消息队列模型 文章目录 RabbitMQ3.13.x之七_RabbitMQ消息队列模型1. RabbitMQ消息队列模型1. 简单队列2. Work Queues(工作队列)3. Publish/Subscribe(发布/订阅)4. Routing(路由)5. Topics(主题)6. RPC(远程过程调用)7. Publisher Confirms(发布者…...

Android JNI 调用第三方SO
最近一个项目使用了Go 编译了一个so库,但是这个so里面还需要使用第三方so库pdfium, 首先在Android工程把2个so库都放好 在jni中只能使用dlopen方式,其他的使用函数指针的方式来调用,和windows dll类似,不然虽然编译过了但是会崩溃…...

Vid2seq
Vid2Seq 应该是目前为止,个人最中意得一篇能够实际解决对一段视频进行粗略理解得paper了。个人认为它能够真正能解决视频理解是因为它是对一个模型整体做了训练,而不仅仅是通过visual encoders(e.g BLIP/CLIP/…)和 其它multi modal 的encoder直接过了个projection,做一个…...
Opencv人机交互界面设置
Opencv人机交互界面设置 以下是一些常见的OpenCV人机交互界面设置: 窗口交互 显示窗口:可以使用cv2.imshow()函数在屏幕上显示图像。例如,要显示名为“image”的图像,可以使用以下代码: import cv2img cv2.imread…...

蓝桥杯算法心得——字典树考试(贡献度+前缀和)
大家好,我是晴天学长,贡献度的题,找到技巧非常重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数…...

Linux下Qt生成程序崩溃文件
文章目录 1.背景2.Qt编译生成程序2.1.profile模式的本质 3.执行程序,得到core文件4.代码定位4.1.直接使用gdb4.2.使用QtCreator 5.总结6.题外话6.1.profile模式和debug模式的区别 1.背景 在使用Qt时,假如在windows,当软件崩溃时,…...
Go语言中测试和性能
1. 测试:软件开发最重要的方面 测试软件程序可能是软件开发人员能够做的最重要的事情。通过测试代码的功能,开发人员能够在很大程度上确定程序是有效的。另外,每次修改代码后,开发人员都可运行测试,确认没有引入Bug和衰退。通过测试软件,还能够让软件工程师确认程序按期望…...

回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测
回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测 目录 回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab基于CPO-GPR基于冠豪猪算法优化高斯…...

python 日期字符串转换为指定格式的日期
在Python编程中,日期处理是一个常见的任务。我们经常需要将日期字符串转换为Python的日期对象,以便进行日期的计算、比较或其他操作。同时,为了满足不同的需求,我们还需要将日期对象转换为指定格式的日期字符串。本文将详细介绍如…...

day03-Docker
1.初识 Docker 1.1.什么是 Docker 1.1.1.应用部署的环境问题 大型项目组件较多,运行环境也较为复杂,部署时会碰到一些问题: 依赖关系复杂,容易出现兼容性问题开发、测试、生产环境有差异 例如一个项目中,部署时需要依…...

C语言函数实现冒泡排序
前言 今天我们来看看怎么使用函数的方式实现冒泡排序吧,我们以一个数组为例arr[] {9,8,7,6,5,4,3,2,1,0},我们将这个数组通过冒泡排序的方式让他变为升序吧。 代码实现 #include<stdio.h> void bubble_sort(int arr[], int sz) {int i 0;for (i 0;i < s…...

区间概率预测python|QR-CNN-BiLSTM+KDE分位数-卷积-双向长短期记忆神经网络-时间序列区间概率预测+核密度估计
区间预测python|QR-CNN-BiLSTMKDE分位数-卷积-双向长短期记忆神经网络-核密度估计-回归时间序列区间预测 模型输出展示: (图中是只设置了20次迭代的预测结果,宽度较宽,可自行修改迭代参数,获取更窄的预测区间) 注&am…...
Java 分支结构 - if…else/switch
顺序结构只能顺序执行,不能进行判断和选择,因此需要分支结构。 Java有两种分支结构: if语句switch语句 if语句 一个if语句包含一个布尔表达式和一条或多条语句。 语法 If 语句的用语法如下: if(布尔表达式) {//如果布尔表达…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...