Leetcode2086. 从房屋收集雨水需要的最少水桶数
Every day a Leetcode
题目来源:2086. 从房屋收集雨水需要的最少水桶数
解法1:贪心
我们可以对字符串 hamsters 从左到右进行一次遍历。
每当我们遍历到一个房屋时,我们可以有如下的选择:
-
如果房屋的两侧已经有水桶,那么我们无需再放置水桶了;
-
如果房屋的两侧没有水桶,那么我们优先在房屋的「右侧」放置水桶,这是因为我们是从左到右进行遍历的,即当我们遍历到第 i 个位置时,前 i−1 个位置的房屋周围都是有水桶的。因此我们在左侧放置水桶没有任何意义,而在右侧放置水桶可以让之后的房屋使用该水桶。
-
如果房屋的右侧无法放置水桶(例如是另一栋房屋或者边界),那么我们只能在左侧放置水桶。如果左侧也不能放置,说明无解。
我们可以通过修改字符串来表示水桶的放置,从而实现上述算法。一种无需修改字符串的方法是,每当我们在房屋的右侧放置水桶时,可以直接「跳过」后续的两个位置,因为如果字符串形如 H.H,我们在第一栋房屋的右侧(即两栋房屋的中间)放置水桶后,就无需考虑第二栋房屋;如果字符串形如 H…,后续没有房屋,我们也可以全部跳过。
代码:
/** @lc app=leetcode.cn id=2086 lang=cpp** [2086] 从房屋收集雨水需要的最少水桶数*/// @lc code=start
class Solution
{
public:int minimumBuckets(string hamsters){int n = hamsters.size();int bucket = 0;for (int i = 0; i < n; i++){if (hamsters[i] == 'H'){if (i + 1 < n && hamsters[i + 1] == '.'){bucket++;i += 2;}else if (i - 1 >= 0 && hamsters[i - 1] == '.')bucket++;elsereturn -1;}}return bucket;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n),其中 n 是字符串 hamsters 的长度。
空间复杂度:O(1)。
解法2:动态规划
设遍历至前 i 个字符满足条件的最小水桶数为 dp[i]。
若 street[i - 1] 为 ‘.’:
- 不放置水桶。此时有
- 若前面一个为房屋(street[i - 2] == ‘H’),可放置水桶。此时有
else if street[i - 1] 为 ‘H’:
- 前方必须放置水桶,则必须满足 street[i - 2] == ‘.’。此时有
- 上一个条件满足情况下如果水桶前方是房子(street[i - 3] == ‘H’),则这个水桶也可以接到前面房子的水。此时有
所有的状态转移取最小值即可。
代码:
/** @lc app=leetcode.cn id=2086 lang=cpp** [2086] 从房屋收集雨水需要的最少水桶数*/// @lc code=start// 贪心// class Solution
// {
// public:
// int minimumBuckets(string hamsters)
// {
// int n = hamsters.size();
// int bucket = 0;
// for (int i = 0; i < n; i++)
// {
// if (hamsters[i] == 'H')
// {
// if (i + 1 < n && hamsters[i + 1] == '.')
// {
// bucket++;
// i += 2;
// }
// else if (i - 1 >= 0 && hamsters[i - 1] == '.')
// bucket++;
// else
// return -1;
// }
// }
// return bucket;
// }
// };class Solution
{
private:
#define INF 0x3F3F3F3F
#define MAX_LEN 1e5 + 10public:int minimumBuckets(string street){int n = street.size();vector<int> dp(MAX_LEN, INF);// 初始化dp[0] = 0;// 状态转移for (int i = 1; i <= n; i++){if (street[i - 1] == '.'){dp[i] = dp[i - 1];if (i - 2 >= 0 && street[i - 2] == 'H')dp[i] = min(dp[i], dp[i - 2] + 1);}else if (street[i - 1] == 'H'){if (i - 2 >= 0 && street[i - 2] == '.'){dp[i] = dp[i - 2] + 1;if (i - 3 >= 0 && street[i - 3] == 'H'){dp[i] = min(dp[i], dp[i - 3] + 1);}}}}return dp[n] >= INF ? -1 : dp[n];}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(n),其中 n 是字符串 street 的长度。
空间复杂度:O(MAX_LEN)。状态数组开销,MAX_LEN = 1e5 + 10。
相关文章:
Leetcode2086. 从房屋收集雨水需要的最少水桶数
Every day a Leetcode 题目来源:2086. 从房屋收集雨水需要的最少水桶数 解法1:贪心 我们可以对字符串 hamsters 从左到右进行一次遍历。 每当我们遍历到一个房屋时,我们可以有如下的选择: 如果房屋的两侧已经有水桶ÿ…...
Pandas教程(非常详细)(第一部分)
Pandas 库是一个免费、开源的第三方 Python 库,是 Python 数据分析必不可少的工具之一,它为 Python 数据分析提供了高性能,且易于使用的数据结构,即 Series 和 DataFrame。Pandas 自诞生后被应用于众多的领域,比如金融…...
typing.Union` 标注一多种变量类型
typing.Union 标注一多种变量类型 typing.Union 是Python typing 模块中用于标注一个变量可以是多种类型之一的类型提示。在Python 3.10版本及以后,推荐使用 | 运算符代替 Union。不过,在详细介绍 Union 的用法前,值得注意的是在大多数情况下…...
OSPF高级特性
OSPF高级特性(1) 一、OSPF不规则区域类型 产生原因:区域划分不合理,导致的问题 1、非骨干区域无法和骨干区域保持连通 2、骨干区域被分割 造成后果:非骨干区域没和骨干区域相连,导致ABR将不会帮忙转发区域间的路由信息。非骨干区…...
mysql中日期的加减 date_add()、date_sub() 函数
一、说明 DATE_ADD() :从日期增加指定的时间间隔,返回的是一个字符串 DATE_ADD(date,INTERVAL expr type) date 参数是合法的日期表达式。expr 参数是您希望添加的时间间隔。 type 参数可以是下列值 二、使用 now() //now函数为获取当前时间 sele…...
实在智能携手品牌商家,在活动会面中共谋发展
金秋十月,丰收的季节,也是商家们在双11大展拳脚的时刻。为迎战一年一度的双11大促,品牌商家在10月份卯足劲,制定一系列营销方案,争取为店铺带来更多流量和订单。 其中,舍得、同科医药、梅子熟了、宝洁、维…...
EXSi系统安装与使用
文章目录 EXSi系统安装与使用EXSi系统安装1.打开VMware Workstation软件2.安装系统3.配置虚拟机 使用EXSi登录web页面扩充存储创建虚拟机使用虚拟机 EXSi系统安装与使用 EXSi系统安装 1.打开VMware Workstation软件 创建虚拟机 2.安装系统 等待 回车 F11 回车 回车 设置密码…...
Spring MVC (Next-1)
1.Restful请求 restFul是符合rest架构风格的网络API接口,完全承认Http是用于标识资源。restFul URL是面向资源的,可以唯一标识和定位资源。 对于该URL标识的资源做何种操作是由Http方法决定的。 rest请求方法有4种,包括get,post,put,delete.分别对应获取…...
双目视觉检测 KX02-SY1000型测宽仪 有效修正和消除距离变化对测量的影响
双目视觉检测的基本原理 利用相机测量宽度时,由于单个相机在成像时存在“近大远小”的现象,并且单靠摄入的图像无法知道被测物的距离,所以由被测物的跳动导致的被测物到工业相机之间距离变化,使测量精度难以提高。 因此测宽仪需…...
C++ 面向对象 学习 优秀教程
油管看视频 沉浸式翻译插件,实现中文字幕! 文章目录 Object Oriented Programming (OOP) in C Course Object Oriented Programming (OOP) in C Course https://www.youtube.com/watch?vwN0x9eZLix4 博主:https://www.youtube.com/CodeBeau…...
Python笔记——pyChram连接linux子系统,使用linux下的Python进行编译
Python笔记——pyChram连接linux子系统,使用linux下的Python进行编译 Linux子系统安装与配置安装前准备安装Linux子系统安装Python3.8配置pyCharm 最近要跑的实验里,python有个机器学习的库windows环境下是没有的,在linux环境下有。虚拟机又不…...
【数据结构】数组和字符串(七):特殊矩阵的压缩存储:三元组表的转置、加法、乘法操作
文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表4.2.3三元组表的转置、加法、乘法、操作转置加法乘法算法测试实验结果代码整合 4.2.1 矩阵的数组表示 【数据结构】数组和字符串…...
Spring底层原理(四)
Spring底层原理(四) 本章内容 模拟实现Spring中的几个常见BeanFactory后置处理器 常见的BeanFactory后置处理器 GenericApplicationContext context new GenericApplicationContext(); context.registerBean("config",Config.class); context.registerBean(Conf…...
Android 14 rook替代Postern进行中间人抓包
以下是关于使用Brook替代Postern进行中间人抓包的说明: 先来解释下,为什么用Postern而不用fd,fd属于代理抓包。Postern属于是模拟出来一张虚拟网卡抓包。性质不一样,所以害怕大哥问我。我就先放在这里 在Android 14及之前的版本中…...
[rancher] rancher部署和使用的一些思考
最近因为工作需要,学习调研rancher的使用 k8s作为主流微服务部署的基础,已经逐渐在工作中普及。但是k8s dashboard用于生产管理,还是有所欠缺:我们需要一个k8s之上的管理平台。经过调研,目前rancher已经迭代开发至v2.8…...
迅镭激光董事长颜章健荣膺“2023年如皋市科技强企人物”!
10月28日,2023如皋科技人才洽谈会开幕式在如皋隆重举行。江苏省科学技术厅副厅长、党组成员蒋洪,江苏省商务厅副厅长、党组成员孙津,中共南通市委副书记、政法委书记沈雷,中共如皋市市委书记何益军,中共如皋市委副书记…...
专业医学病例翻译公司推荐
我们知道,医学病例翻译在涉外看病的患者中具有广泛的应用,它可以帮助医生快速了解患者的病情,为治疗和药物处方提供关键信息。因此,对于出国看病的患者,医学病例翻译便成了不可或缺的重要工具。 翻译医学病例不仅要求译…...
英飞凌TC3xx-Overlay
目录 1.数据访问重定向 2.寄存器说明 3.Overlay功能配置 3.1 确认用于重定向的CPU 3.2 配置重定向Block大小 3.3 配置目标地址和重定向地址 4.结果验证 5.小结 今天说要开个专栏讲讲XCP标定,但在将标定之前,先把英飞凌专门为标定功能设计overlay…...
Win10系统有几种复制文件的命令,哪种最强大?
环境: Win10 专业版 问题描述: Win10系统有几种复制文件的命令,哪种最强大? 解决方案: 在 Windows 10 中,复制文件的命令有以下几种: 使用 xcopy 命令:xcopy 是一个功能强大的…...
力扣202.快乐数
原题链接:202.快乐数 要记住的就是,需要判断元素是否出现过,或者是否在集合里存在,就可以考虑用哈希法去做 因为是每一位都进行平方后相加得到新的数,所以需要单独写一个函数进行每位相加的运算得到最终的sum 不断重…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
