谷歌(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(布尔表达式) {//如果布尔表达…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
