廊坊建设部网站,优秀行业网站,做网站公司汉狮网络,石家庄新钥匙做网站文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的字符串 street 。street 中每个字符要么是表示房屋的 ‘H’ #xff0c;要么是表示空位的 ‘.’ 。
你可以在 空位 放置水桶#xff0c;从相邻的房屋收集雨水。 位置在 i - 1 或者 i 1 的水桶可以收集位置为 i 处房…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的字符串 street 。street 中每个字符要么是表示房屋的 ‘H’ 要么是表示空位的 ‘.’ 。
你可以在 空位 放置水桶从相邻的房屋收集雨水。 位置在 i - 1 或者 i 1 的水桶可以收集位置为 i 处房屋的雨水。 一个水桶如果相邻两个位置都有房屋那么它可以收集 两个 房屋的雨水。
在确保 每个 房屋旁边都 至少 有一个水桶的前提下请你返回需要的 最少 水桶数。 如果无解请返回 -1 。
示例 1
输入street H..H
输出2
解释
我们可以在下标为 1 和 2 处放水桶。
H..H - HBBHB 表示放置水桶。
下标为 0 处的房屋右边有水桶下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水。示例 2
输入street .H.H.
输出1
解释
我们可以在下标为 2 处放置一个水桶。
.H.H. - .HBH.B 表示放置水桶。
下标为 1 处的房屋右边有水桶下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水。示例 3
输入street .HHH.
输出-1
解释
没有空位可以放置水桶收集下标为 2 处的雨水。
所以没有办法收集所有房屋的雨水。示例 4
输入street H
输出-1
解释
没有空位放置水桶。
所以没有办法收集所有房屋的雨水。示例 5
输入street .
输出0
解释
没有房屋需要收集雨水。
所以需要 0 个水桶。提示
1 street.length 10^5
street[i] 要么是 H 要么是 . 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-number-of-buckets-required-to-collect-rainwater-from-houses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
不是最优解也是贪心的思路先把. 左右都有的位置放上然后再处理单个的
class Solution {
public:int minimumBuckets(string street) {int n street.size();vectorint ct(n, 0); // 记录 . 左右有没有满足条件的 H 的数量for(int i 0; i n; i){if(street[i]H){if(i-10 street[i-1].)ct[i-1];if(i1n street[i1].)ct[i1];}}vectorbool have(n, false);int ans 0;for(int i 0; i n; i){if(ct[i] 2) // 先处理2个的情况{have[i-1] have[i1] true;if(i-20 street[i-2].)ct[i-2]--;if(i2n street[i2].)ct[i2]--;ct[i] 0;ans;}}for(int i 0; i n; i){if(ct[i] 1){ans;if(i-10 street[i-1]H) {have[i-1]true;}if(i1n street[i1]H) {have[i1]true;if(i2n street[i2].)ct[i2]--;//记得更新后面的计数}}}for(int i 0; i n; i){if(street[i]H have[i]false) return -1;}return ans;}
};28 ms 14.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
