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

谷歌(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

思路一:双指针

这个问题可以使用双指针的方法来解决。具体步骤如下:

  1. 初始化左右指针 leftright,分别指向数组的第一个和最后一个元素。
  2. 初始化两个变量 left_maxright_max,分别表示左侧柱子的最大高度和右侧柱子的最大高度,初始值都为0。
  3. 使用循环遍历数组,当 left 指针小于等于 right 指针时,执行以下步骤:
    • 如果 height[left] < height[right],表示左侧柱子较低,则计算当前位置的雨水量,并更新左侧最大高度 left_max
    • 否则,表示右侧柱子较低,则计算当前位置的雨水量,并更新右侧最大高度 right_max
    • 在计算雨水量时,当前位置能够接的雨水量等于当前最小高度(left_maxright_max中的较小值)与当前柱子高度之差。
  4. 返回计算得到的总雨水量。

下面是相应的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

这个函数使用双指针的方法,通过一次遍历就可以计算出雨水的总量。

思路二:栈

除了双指针的方法外,还可以使用栈来解决这个问题。具体步骤如下:

  1. 初始化一个栈 stack 和一个变量 ansans 用于记录接到的雨水量,初始值为0。
  2. 遍历数组 height 中的每一个柱子,依次执行以下操作:
    • 如果栈为空,或当前柱子高度小于等于栈顶柱子高度,则将当前柱子下标入栈。
    • 否则,说明当前柱子可能会形成一个水池,将栈中元素逐个弹出,直到遇到柱子高度大于当前柱子高度的位置。每次弹出时,都计算当前柱子和栈顶柱子之间的距离,并根据距离和高度差计算雨水量,然后累加到 ans 中。
    • 最后将当前柱子下标入栈。
  3. 遍历完成后,返回 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

这个函数使用栈的方法,通过一次遍历就可以计算出雨水的总量。

思路三:动态规划

除了双指针和栈的方法外,还可以使用动态规划来解决这个问题。具体步骤如下:

  1. 初始化两个数组 left_maxright_max,分别用于存储每个柱子左侧和右侧的最大高度。
    • left_max[i] 表示第 i 个柱子左侧(包括自身)的最大高度。
    • right_max[i] 表示第 i 个柱子右侧(包括自身)的最大高度。
  2. 遍历数组 height,从左向右更新 left_max,从右向左更新 right_max
  3. 遍历数组 height,对于每个柱子,计算该位置上可以接到的雨水量,即 min(left_max[i], right_max[i]) - height[i]
  4. 累加所有位置上的雨水量,即为最终的雨水总量。

下面是相应的 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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;…...

golang 归并回源策略

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

【漏洞复现】可视化融合指挥调度平台 dispatch接口处存在任意文件上传漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…...

最讨厌这种字符串问题了!!

题目&#xff1a;洛谷P1957口算练习题 题目大意描述&#xff1a; 第一行输入一个整数表示接下来要进行多少次运算&#xff0c;接下来每行输入一个字母c和两个数字x,y&#xff08;输入的字母为a/b/c,分别表示要进行&#xff0c;-&#xff0c;*运算&#xff09;或者就输入两个数…...

B-名牌赌王(本人遇到的题,做个笔记)

题解&#xff1a; #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

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

【【萌新的学习之Numpy数组的使用】】

萌新的学习之Numpy数组的使用 先记录一下之前的关于函数的设计 通过创造类的形式 复习完毕之后介绍numpy数组的使用 #整数型数组遇到除法 &#xff08;即便是除以整数&#xff09; 不同维度的数组之间 从外形上的本质区别 一维数组用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库&#xff0c;但是这个so里面还需要使用第三方so库pdfium, 首先在Android工程把2个so库都放好 在jni中只能使用dlopen方式&#xff0c;其他的使用函数指针的方式来调用&#xff0c;和windows dll类似&#xff0c;不然虽然编译过了但是会崩溃…...

Vid2seq

Vid2Seq 应该是目前为止,个人最中意得一篇能够实际解决对一段视频进行粗略理解得paper了。个人认为它能够真正能解决视频理解是因为它是对一个模型整体做了训练,而不仅仅是通过visual encoders(e.g BLIP/CLIP/…)和 其它multi modal 的encoder直接过了个projection,做一个…...

Opencv人机交互界面设置

Opencv人机交互界面设置 以下是一些常见的OpenCV人机交互界面设置&#xff1a; 窗口交互 显示窗口&#xff1a;可以使用cv2.imshow()函数在屏幕上显示图像。例如&#xff0c;要显示名为“image”的图像&#xff0c;可以使用以下代码&#xff1a; import cv2img cv2.imread…...

蓝桥杯算法心得——字典树考试(贡献度+前缀和)

大家好&#xff0c;我是晴天学长&#xff0c;贡献度的题&#xff0c;找到技巧非常重要&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数…...

Linux下Qt生成程序崩溃文件

文章目录 1.背景2.Qt编译生成程序2.1.profile模式的本质 3.执行程序&#xff0c;得到core文件4.代码定位4.1.直接使用gdb4.2.使用QtCreator 5.总结6.题外话6.1.profile模式和debug模式的区别 1.背景 在使用Qt时&#xff0c;假如在windows&#xff0c;当软件崩溃时&#xff0c;…...

Go语言中测试和性能

1. 测试:软件开发最重要的方面 测试软件程序可能是软件开发人员能够做的最重要的事情。通过测试代码的功能,开发人员能够在很大程度上确定程序是有效的。另外,每次修改代码后,开发人员都可运行测试,确认没有引入Bug和衰退。通过测试软件,还能够让软件工程师确认程序按期望…...

回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测

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

python 日期字符串转换为指定格式的日期

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

day03-Docker

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

C语言函数实现冒泡排序

前言 今天我们来看看怎么使用函数的方式实现冒泡排序吧&#xff0c;我们以一个数组为例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分位数-卷积-双向长短期记忆神经网络-核密度估计-回归时间序列区间预测 模型输出展示&#xff1a; (图中是只设置了20次迭代的预测结果&#xff0c;宽度较宽&#xff0c;可自行修改迭代参数&#xff0c;获取更窄的预测区间&#xff09; 注&am…...

Java 分支结构 - if…else/switch

顺序结构只能顺序执行&#xff0c;不能进行判断和选择&#xff0c;因此需要分支结构。 Java有两种分支结构&#xff1a; if语句switch语句 if语句 一个if语句包含一个布尔表达式和一条或多条语句。 语法 If 语句的用语法如下&#xff1a; if(布尔表达式) {//如果布尔表达…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...