Every day a Leetcode

題目來源：2086. 從房屋收集雨水需要的最少水桶數

解法1：貪心

我們可以對字符串 hamsters 從左到右進行一次遍歷。

每當我們遍歷到一個房屋時，我們可以有如下的選擇：

• 如果房屋的兩側已經有水桶，那么我們無需再放置水桶了；

• 如果房屋的兩側沒有水桶，那么我們優(yōu)先在房屋的「右側」放置水桶，這是因為我們是從左到右進行遍歷的，即當我們遍歷到第 i 個位置時，前 i?1 個位置的房屋周圍都是有水桶的。因此我們在左側放置水桶沒有任何意義，而在右側放置水桶可以讓之后的房屋使用該水桶。

• 如果房屋的右側無法放置水桶（例如是另一棟房屋或者邊界），那么我們只能在左側放置水桶。如果左側也不能放置，說明無解。

我們可以通過修改字符串來表示水桶的放置，從而實現上述算法。一種無需修改字符串的方法是，每當我們在房屋的右側放置水桶時，可以直接「跳過」后續(xù)的兩個位置，因為如果字符串形如 H.H，我們在第一棟房屋的右側（即兩棟房屋的中間）放置水桶后，就無需考慮第二棟房屋；如果字符串形如 H…，后續(xù)沒有房屋，我們也可以全部跳過。

代碼：

/** @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：動態(tài)規(guī)劃

設遍歷至前 i 個字符滿足條件的最小水桶數為 dp[i]。

若 street[i - 1] 為 ‘.’：

• 不放置水桶。此時有
• 若前面一個為房屋（street[i - 2] == ‘H’），可放置水桶。此時有

else if street[i - 1] 為 ‘H’：

• 前方必須放置水桶，則必須滿足 street[i - 2] == ‘.’。此時有
• 上一個條件滿足情況下如果水桶前方是房子（street[i - 3] == ‘H’），則這個水桶也可以接到前面房子的水。此時有

所有的狀態(tài)轉移取最小值即可。

代碼：

/** @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;// 狀態(tài)轉移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)。狀態(tài)數組開銷，MAX_LEN = 1e5 + 10。