Question

2086. 喂食仓鼠的最小食物桶数

English Version

题目描述

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

• 'H' 表示有一个仓鼠在下标 i ，或者
• '.' 表示下标 i 是空的。

你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，就可以喂食它。更正式地说，如果你在位置 i - 1 或者 i + 1 放置一个食物桶，就可以喂养位置为 i 处的仓鼠。

在 空的位置 放置食物桶以喂养所有仓鼠的前提下，请你返回需要的 最少 食物桶数。如果无解请返回 -1 。

示例 1：

输入：hamsters = "H..H"
输出：2
解释：
我们可以在下标为 1 和 2 处放食物桶。
可以发现如果我们只放置 1 个食物桶，其中一只仓鼠将得不到喂养。

示例 2：

输入：street = ".H.H."
输出：1
解释：
我们可以在下标为 2 处放置一个食物桶。

示例 3：

输入：street = ".HHH."
输出：-1
解释：
如果我们如图那样在每个空位放置食物桶，下标 2 处的仓鼠将吃不到食物。

提示：

• 1 <= hamsters.length <= 105
• hamsters[i] 要么是 'H' ，要么是 '.' 。

解法

方法一：贪心

从左到右遍历字符串，遇到 H 时，优先考虑右边是否有空位，如果有则放置水桶，并且跳过水桶的下一个位置；如果右边没有空位，则考虑左边是否有空位，如果有则放置水桶，否则无解。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 street 的长度。

class Solution:
  def minimumBuckets(self, street: str) -> int:
    ans = 0
    i, n = 0, len(street)
    while i < n:
      if street[i] == 'H':
        if i + 1 < n and street[i + 1] == '.':
          i += 2
          ans += 1
        elif i and street[i - 1] == '.':
          ans += 1
        else:
          return -1
      i += 1
    return ans

class Solution {
  public int minimumBuckets(String street) {
    int n = street.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (street.charAt(i) == 'H') {
        if (i + 1 < n && street.charAt(i + 1) == '.') {
          ++ans;
          i += 2;
        } else if (i > 0 && street.charAt(i - 1) == '.') {
          ++ans;
        } else {
          return -1;
        }
      }
    }
    return ans;
  }
}

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 && street[i - 1] == '.') {
          ++ans;
        } else {
          return -1;
        }
      }
    }
    return ans;
  }
};

func minimumBuckets(street string) int {
  ans, n := 0, len(street)
  for i := 0; i < n; i++ {
    if street[i] == 'H' {
      if i+1 < n && street[i+1] == '.' {
        ans++
        i += 2
      } else if i > 0 && street[i-1] == '.' {
        ans++
      } else {
        return -1
      }
    }
  }
  return ans
}