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 不断重…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...
简单介绍C++中 string与wstring
在C中,string和wstring是两种用于处理不同字符编码的字符串类型,分别基于char和wchar_t字符类型。以下是它们的详细说明和对比: 1. 基础定义 string 类型:std::string 字符类型:char(通常为8位)…...
AT模式下的全局锁冲突如何解决?
一、全局锁冲突解决方案 1. 业务层重试机制(推荐方案) Service public class OrderService {GlobalTransactionalRetryable(maxAttempts 3, backoff Backoff(delay 100))public void createOrder(OrderDTO order) {// 库存扣减(自动加全…...
