谷歌(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(布尔表达式) {//如果布尔表达…...
【Unity每日一记】如何从0到1将特效图集制作成一个特效
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:Uni…...
磁力链接的示例与解释
磁力链接(Magnet URI scheme)是一种特殊类型的统一资源标识符(URI),它包含了通过特定散列函数(如SHA-1)得到的文件内容的散列值,而不是基于位置或名称的引用。这使得磁力链接成为在分…...
云存储中常用的相同子策略的高效、安全的基于属性的访问控制的论文阅读
参考文献为2022年发表的Efficient and Secure Attribute-Based Access Control With Identical Sub-Policies Frequently Used in Cloud Storage 动机 ABE是实现在云存储中一种很好的访问控制手段,但是其本身的计算开销导致在实际场景中应用收到限制。本论文研究了一种LSSS矩…...
JVM高级篇之GC
文章目录 版权声明垃圾回收器的技术演进ShenandoahShenandoah GC体验Shenandoah GC循环过程 ZGCZGC简介ZGC的版本更迭ZGC体验&使用ZGC的参数设置ZGC的调优 版权声明 本博客的内容基于我个人学习黑马程序员课程的学习笔记整理而成。我特此声明,所有版权属于黑马…...
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
原题链接:三国游戏 小蓝正在玩一款游戏。 游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。 游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时…...
java之static详细总结
static也叫静态,可以修饰成员变量、成员方法。 成员变量 按照有无static分为两种: 类变量:static修饰,属于类,与类一起加载一次,在内存中只有一份,会被类的全部对象共享实例变量(…...
RabbitMQ3.13.x之六_RabbitMQ使用场景
RabbitMQ3.13.x之六_RabbitMQ使用场景 文章目录 RabbitMQ3.13.x之六_RabbitMQ使用场景1. 为什么选择 RabbitMQ?1. 可互操作2. 灵活3. 可靠 2. 常见用户案例1. 服务解耦2. 远程过程调用3. 流处理4. 物联网 1. 为什么选择 RabbitMQ? RabbitMQ 是一个可靠且…...
C++ 类和对象(初篇)
类的引入 C语言中,结构体中只能定义变量,在C中,结构体内不仅可以定义变量,也可以定义函数。 而为了区分C和C我们将结构体重新命名成class去定义 类的定义 标准格式: class className {// 类体:由成员函…...
微软推出GPT-4 Turbo优先使用权:Copilot for Microsoft 365商业用户享受无限制对话及增强图像生成能力
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
Spring Boot Actuator
概述 Spring Boot Actuator是Spring Boot的一个功能模块,用于提供生产环境中常见的监控和管理功能。它提供了各种端点(endpoints),可以用于监视应用程序的运行状况、收集应用程序的指标数据以及与应用程序进行交互。 以下是Spri…...
基于liferay portal的乡镇企业门户网站建设研究/关键词数据
一. System: 首先是System类,因为从一开始从接触java起,我们就无时无刻都在接触它,经常用它来向屏幕,向控制台打印输出一些信息,System.out.println(“hello world”);这个只是在控制台输出一条信息“hello world”&am…...
机械网站模板/有什么平台可以发布推广信息
我以前进入嵌入式开发都是在Windows上通过Keil和IAR等IDE开进行的。为了更深入的学习和了解mcu的程序编译过程,决心要将mcu的开发工作转到Linux环境下进行。由于有一些工作还需要在Windows下进行,所以只能在Windows环境下来搭建Linux开发环境。以前都是通…...
徐州市 两学一做网站/百度一下搜索网页
2019独角兽企业重金招聘Python工程师标准>>> 按行读取文件 with open(1.txt, r) as f:for line in f:print line按行读取gzip文件 import gzipdef x_read_gzip(filename):with gzip.open(filename, rb) as f:for line in f:yield line按行读取zip文件 import zipfil…...
做商业网站没有注册公司/小米的推广软文
OpenSSL使用SSL_read() 函数来读取数据,跟使用read()一样,我们只需要简单的选择一个合适大小的缓冲,然后将它传递给SS L_read()函数。注意到缓冲区的大小在此处并没有多么的重要,SSL_read() 和read()一样,返回可用的数…...
做商城网站/上海空气中检测出病毒
本文地址:https://blog.csdn.net/qq_40885085 在我们写代码的时候,会书写许多日志代码,但是有些敏感数据是需要进行安全脱敏处理的。 对于日志脱敏的方式有很多,常见的有①使用conversionRule标签,继承MessageConver…...
网站开发工程师怎么样/免费网站推广软件哪个好
*bootstrap官方说明:http://v3.bootcss.com/javascript/#popovers一. popover常用配置参数:1 //常用配置参数:2 $(document).ready(function() {3 $(#temp).popover(4 {5 trigger:click, //触发方式6 template: , //你自定义的模板7 title:&q…...