You are given a 0-indexed string street
. Each character in street
is either 'H'
representing a house or '.'
representing an empty space.
You can place buckets on the empty spaces to collect rainwater that falls from the adjacent houses. The rainwater from a house at index i
is collected if a bucket is placed at index i - 1
and/or index i + 1
. A single bucket, if placed adjacent to two houses, can collect the rainwater from both houses.
Return the minimum number of buckets needed so that for every house, there is at least one bucket collecting rainwater from it, or -1
if it is impossible.
Example 1:
Input: street = "H..H" Output: 2 Explanation: We can put buckets at index 1 and index 2. "H..H" -> "HBBH" ('B' denotes where a bucket is placed). The house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left. Thus, for every house, there is at least one bucket collecting rainwater from it.
Example 2:
Input: street = ".H.H." Output: 1 Explanation: We can put a bucket at index 2. ".H.H." -> ".HBH." ('B' denotes where a bucket is placed). The house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left. Thus, for every house, there is at least one bucket collecting rainwater from it.
Example 3:
Input: street = ".HHH." Output: -1 Explanation: There is no empty space to place a bucket to collect the rainwater from the house at index 2. Thus, it is impossible to collect the rainwater from all the houses.
Example 4:
Input: street = "H" Output: -1 Explanation: There is no empty space to place a bucket. Thus, it is impossible to collect the rainwater from the house.
Example 5:
1 2 3 4 5 |
<strong>Input:</strong> street = "." <strong>Output:</strong> 0 <strong>Explanation:</strong> There is no house to collect water from. Thus, 0 buckets are needed. |
Constraints:
1 <= street.length <= 105
street[i]
is either'H'
or'.'
.
Solution: Greedy
Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int minimumBuckets(string street) { const int n = street.size(); int ans = 0; for (int i = 0; i < n; ++i) if (street[i] == 'H') if (i - 1 >= 0 and street[i - 1] == 'B') continue; else if (i + 1 < n and street[i + 1] == '.') street[i + 1] = 'B', ++ans; else if (i - 1 >= 0 and street[i - 1] == '.') street[i - 1] = 'B', ++ans; else return -1; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment