喂食仓鼠的最小食物桶数

标签: 贪心 字符串 动态规划

难度: Medium

给你一个下标从 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' ，要么是 '.' 。

Submission

运行时间: 40 ms

内存: 17.7 MB

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        """
        贪心:
        1. 优先考虑 H.H 情况
        2. H. 与 .H 的情况
        3. 统计剩余H的数量
        """
        ans = 0
        s = hamsters.replace("H.H", "1").replace("H.", "1").replace(".H", "1")
        for x in s:
            if x == 'H':
                return -1
            if x == '1':
                ans += 1
        return ans

Explain

题解采用了贪心策略来求解最小食物桶数量。首先，通过字符串替换的方式，尝试解决那些容易解决的仓鼠位置。具体步骤包括：1. 首先解决形式为'H.H'的情况，即一个食物桶可以同时喂两边的仓鼠。2. 然后解决形式为'H.'和'.H'的情况，即一个食物桶可以喂一个仓鼠。3. 最后检查是否还有无法被喂养的仓鼠('H')，如果有，则返回-1表示无解。通过这种方式，算法在遍历和替换字符串的过程中即可确定所需的最小食物桶数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        \"\"\"
        贪心算法：优先解决可同时喂养两边仓鼠的情况，然后单边情况，最后检查不可解的情况。
        1. 将'H.H'替换为'1'，表示这里可以用一个食物桶喂两边的仓鼠。
        2. 将'H.'和'.H'替换为'1'，表示这里可以用一个食物桶喂单边的仓鼠。
        3. 检查替换后的字符串，统计'1'的数量作为答案，如果还有'H'，则返回-1表示无解。
        \"\"\"
        ans = 0 # 初始化食物桶计数器
        s = hamsters.replace('H.H', '1').replace('H.', '1').replace('.H', '1') # 替换字符串中的特定模式
        for x in s: # 遍历替换后的字符串
            if x == 'H': # 如果发现还有'H'，说明存在无法喂养的仓鼠，返回-1
                return -1
            if x == '1': # 计数替换后的'1'，每个'1'代表一个食物桶
                ans += 1
        return ans # 返回需要的最少食物桶数

Explore

处理'H.H'的情况可以同时喂养两边的仓鼠，是最优的食物桶使用方式。如果先处理这种情况，可以确保在食物桶数量最少的前提下，最大程度地喂养仓鼠。若先处理单边的'H.'或'.H'，可能会导致需要更多的食物桶，例如对于'H.H'，如果先放置两个桶在两边，就需要两个桶，而正确的做法只需要一个桶即可。

连续的'H.H.H'模式在替换过程中需要特别注意。正确的处理方法是从左到右依次替换。首先，将中间的'H.H'替换为'1'，变为'H1H'，然后再替换剩下的'H.'或'.H'。这样，每个'H'都会被至少一个食物桶覆盖，确保所有仓鼠都能被喂养。如果处理顺序不当或替换不全面，可能导致某些'H'未被喂养。

在替换'H.H'为'1'后，处理其周围的'H'需要具体情况具体分析。例如在'HH.HH'模式中，首先替换中间的'H.H'为'1'变为'HH1HH'。然后，需要在每个孤立的'H'旁边至少放置一个食物桶。在这个例子中，可以在第一个'H'的右边和最后一个'H'的左边各放一个食物桶，使得整个字符串中的每个'H'都至少有一个相邻的食物桶。这样，总共需要三个食物桶：一个在中间的'1'，两个分别在两端的'H'旁边。