2086-从房屋收集雨水需要的最少水桶数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个下标从 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 <= 105
  • street[i] 要么是 'H' ，要么是 '.' 。

方法一：贪心

思路与算法

我们可以对字符串 street 从左到右进行一次遍历。

每当我们遍历到一个房屋时，我们可以有如下的选择：

  • 如果房屋的两侧已经有水桶，那么我们无需再放置水桶了；

  • 如果房屋的两侧没有水桶，那么我们优先在房屋的「右侧」放置水桶，这是因为我们是从左到右进行遍历的，即当我们遍历到第 i 个位置时，前 i-1 个位置的房屋周围都是有水桶的。因此我们在左侧放置水桶没有任何意义，而在右侧放置水桶可以让之后的房屋使用该水桶。

    如果房屋的右侧无法放置水桶（例如是另一栋房屋或者边界），那么我们只能在左侧放置水桶。如果左侧也不能放置，说明无解。

我们可以通过修改字符串来表示水桶的放置，从而实现上述算法。一种无需修改字符串的方法是，每当我们在房屋的右侧放置水桶时，可以直接「跳过」后续的两个位置，因为如果字符串形如 H.H，我们在第一栋房屋的右侧（即两栋房屋的中间）放置水桶后，就无需考虑第二栋房屋；如果字符串形如 H..，后续没有房屋，我们也可以全部跳过。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimumBuckets(string street) {
        int n = street.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (street[i] == 'H') {
                if (i + 1 < n && street[i + 1] == '.') {
                    ++ans;
                    // 直接跳过后续的两个位置
                    i += 2;
                }
                else if (i - 1 >= 0 && street[i - 1] == '.') {
                    ++ans;
                }
                else {
                    return -1;
                }
            }
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 street 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
2086-从房屋收集雨水需要的最少水桶数