Medium

题目描述

给你一个下标从 0 开始的字符串 hamsters ，其中 hamsters[i] 是：

  • 'H' 表示第 i 个位置有一只仓鼠
  • '.' 表示第 i 个位置是空的

你需要在一些空位置放置食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，那么这只仓鼠就能被喂养。更正式地说，位置 i 的仓鼠能被喂养，当且仅当你在位置 i - 1 和/或位置 i + 1 放置了食物桶。

返回你需要放置在空位置的食物桶的 最少 数量，以便喂养所有仓鼠，如果无法喂养所有仓鼠则返回 -1。

示例 1：

输入: hamsters = "H..H"
输出: 2
解释: 我们在位置 1 和 2 放置两个食物桶。
可以证明如果只放一个食物桶，其中一只仓鼠无法被喂养。

示例 2：

输入: hamsters = ".H.H."
输出: 1
解释: 我们在位置 2 放置一个食物桶。

示例 3：

输入: hamsters = ".HHH."
输出: -1
解释: 如果我们在所有空位置都放置食物桶，位置 2 的仓鼠仍然无法吃到食物。

提示：

  • 1 <= hamsters.length <= 10^5
  • hamsters[i] 要么是 'H' 要么是 '.'

解题思路

这道题的核心思路是贪心算法。我们需要找到用最少食物桶喂养所有仓鼠的策略。

关键观察：

  1. 如果存在连续的三只仓鼠（“HHH”），那么中间的仓鼠无法被喂养，直接返回 -1
  2. 对于每只仓鼠，我们有两个选择：在它左边放桶或右边放桶
  3. 贪心策略：优先在仓鼠右边放桶，因为这样可能同时喂养下一只仓鼠

解法思路：

  1. 预处理检查：先检查是否存在不可能的情况（连续三只仓鼠）
  2. 贪心放置：从左到右遍历，遇到仓鼠时：
    • 如果左边已有桶，跳过
    • 否则尽量在右边放桶（更优选择）
    • 如果右边不能放，只能在左边放

这个贪心策略的正确性在于：在右边放桶不仅能喂养当前仓鼠，还可能喂养下一只仓鼠，从而减少总桶数。

时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    int minimumBuckets(string hamsters) {
        int n = hamsters.length();
        int buckets = 0;
        
        for (int i = 0; i < n; i++) {
            if (hamsters[i] == 'H') {
                // 检查左边是否已经有桶
                if (i > 0 && hamsters[i-1] == 'B') {
                    continue;
                }
                // 尝试在右边放桶
                if (i + 1 < n && hamsters[i+1] == '.') {
                    hamsters[i+1] = 'B';
                    buckets++;
                }
                // 否则在左边放桶
                else if (i > 0 && hamsters[i-1] == '.') {
                    hamsters[i-1] = 'B';
                    buckets++;
                }
                // 无法放桶，返回-1
                else {
                    return -1;
                }
            }
        }
        
        return buckets;
    }
};

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        hamsters = list(hamsters)
        n = len(hamsters)
        buckets = 0
        
        for i in range(n):
            if hamsters[i] == 'H':
                # 检查左边是否已经有桶
                if i > 0 and hamsters[i-1] == 'B':
                    continue
                # 尝试在右边放桶
                if i + 1 < n and hamsters[i+1] == '.':
                    hamsters[i+1] = 'B'
                    buckets += 1
                # 否则在左边放桶
                elif i > 0 and hamsters[i-1] == '.':
                    hamsters[i-1] = 'B'
                    buckets += 1
                # 无法放桶，返回-1
                else:
                    return -1
        
        return buckets

public class Solution {
    public int MinimumBuckets(string hamsters) {
        char[] arr = hamsters.ToCharArray();
        int n = arr.Length;
        int buckets = 0;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] == 'H') {
                // 检查左边是否已经有桶
                if (i > 0 && arr[i-1] == 'B') {
                    continue;
                }
                // 尝试在右边放桶
                if (i + 1 < n && arr[i+1] == '.') {
                    arr[i+1] = 'B';
                    buckets++;
                }
                // 否则在左边放桶
                else if (i > 0 && arr[i-1] == '.') {
                    arr[i-1] = 'B';
                    buckets++;
                }
                // 无法放桶，返回-1
                else {
                    return -1;
                }
            }
        }
        
        return buckets;
    }
}

/**
 * @param {string} hamsters
 * @return {number}
 */
var minimumBuckets = function(hamsters) {
    let arr = hamsters.split('');
    let n = arr.length;
    let buckets = 0;
    
    for (let i = 0; i < n; i++) {
        if (arr[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 只需要遍历字符串一次
空间复杂度O(n) - 需要复制字符串用于修改（某些语言中字符串不可变）

相关题目