class Solution {
public:
int minimumBuckets(string hamsters) {
}
};
2086. 从房屋收集雨水需要的最少水桶数
给你一个下标从 0 开始的字符串 street 。street 中每个字符要么是表示房屋的 'H' ，要么是表示空位的 '.' 。
你可以在 空位 放置水桶，从相邻的房屋收集雨水。位置在 i - 1 或者 i + 1 的水桶可以收集位置为 i 处房屋的雨水。一个水桶如果相邻两个位置都有房屋，那么它可以收集 两个 房屋的雨水。
在确保 每个 房屋旁边都 至少 有一个水桶的前提下，请你返回需要的 最少 水桶数。如果无解请返回 -1 。
示例 1：
输入：street = "H..H" 输出：2 解释： 我们可以在下标为 1 和 2 处放水桶。 "H..H" -> "HBBH"（'B' 表示放置水桶）。 下标为 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 <= 105street[i] 要么是 'H' ，要么是 '.' 。原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 5.3 MB, 提交时间: 2023-09-19 16:19:33
func minimumBuckets(street string) (ans int) {
bucketPos := -2 // 上一个水桶的放置位置
for i, ch := range street {
if ch == 'H' { // 遍历每个房屋
if bucketPos == i-1 { // 左侧已有水桶，不做任何处理
} else if i+1 < len(street) && street[i+1] == '.' { // 贪心：先考虑在右侧放水桶
bucketPos = i + 1
ans++
} else if i > 0 && street[i-1] == '.' { // 再考虑在左侧放水桶
ans++
} else { // 左右均无空位，无解
return -1
}
}
}
return
}
java 解法, 执行用时: 7 ms, 内存消耗: 43.3 MB, 提交时间: 2023-09-19 16:44:47
/**
* 先决条件：把无解的情况先排除掉 第一遍扫描：一个房子一桶水
* 第二遍扫描：若两个房子可以共用一桶水，则答案减1，同时注意跳过H.H
*/
class Solution {
public int minimumBuckets(String street) {
if ("H".equals(street) || street.startsWith("HH") || street.endsWith("HH") || street.contains("HHH")) {
return -1;
}
int res = 0;
for (char c : street.toCharArray()) {
if (c == 'H') {
++res;
}
}
for (int i = 0; i < street.length() - 2; ++i) {
if (street.charAt(i) == 'H' && street.charAt(i+1)=='.' && street.charAt(i+2)=='H') {
--res;
i += 2;
}
}
return res;
}
}
python3 解法, 执行用时: 68 ms, 内存消耗: 17.1 MB, 提交时间: 2023-09-19 16:45:18
class Solution:
def minimumBuckets(self, hamsters: str) -> int:
hamsters = "H" + hamsters + "H"
if "HHH" in hamsters: return -1
hamsters, lenh, cnt = list(hamsters), len(hamsters), 0
for i in range(1, lenh - 1):
if hamsters[i] == 'H':
if hamsters[i - 1] == 'B': continue
elif hamsters[i - 1] == '.' and hamsters[i + 1] == 'H': cnt += 1
elif hamsters[i + 1] == '.':
hamsters[i + 1] = 'B'
cnt += 1
return cnt
golang 解法, 执行用时: 4 ms, 内存消耗: 5.3 MB, 提交时间: 2023-09-19 16:43:14
func minimumBuckets(street string) (ans int) {
bucketPos := -2 // 上一个水桶的放置位置
for i, ch := range street {
if ch == 'H' { // 遍历每个房屋
if bucketPos == i-1 { // 左侧已有水桶，不做任何处理
} else if i+1 < len(street) && street[i+1] == '.' { // 贪心：先考虑在右侧放水桶
bucketPos = i + 1
ans++
} else if i > 0 && street[i-1] == '.' { // 再考虑在左侧放水桶
ans++
} else { // 左右均无空位，无解
return -1
}
}
}
return
}
python3 解法, 执行用时: 84 ms, 内存消耗: 15.4 MB, 提交时间: 2022-11-09 11:22:39
class Solution:
def minimumBuckets(self, street: str) -> int:
'''
贪心法，遍历每个位置
'''
n = len(street)
i = ans = 0
while i < n:
if street[i] == "H":
if i + 1 < n and street[i + 1] == ".": # 看右边是否有空位，优先放右边
ans += 1
# 直接跳过后续的两个位置
i += 2
elif i - 1 >= 0 and street[i - 1] == ".": # 否则就放左边空位
ans += 1
else:
return -1
i += 1
return ans