leetcode
leetcode 1801 ~ 1850
喂食仓鼠的最小食物桶数

喂食仓鼠的最小食物桶数

难度:

标签:

题目描述

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

代码结果

运行时间: 40 ms, 内存: 17.7 MB


/*
 * Problem: Given a string 'hamsters', where 'H' indicates a hamster and '.' indicates an empty spot, we need to place food buckets in the empty spots such that each hamster has access to at least one food bucket either to its left or right. Return the minimum number of food buckets needed, or -1 if it is impossible to feed all hamsters.
 * 
 * Solution: Using Java Streams, we can iterate through the string, count the minimum number of buckets required and ensure all 'H' characters have access to a bucket. 
 */

import java.util.stream.IntStream;

public class HamstersFeedingStream {
    public int minBuckets(String hamsters) {
        int[] result = {0, 0}; // {buckets, lastBucketPosition}
        IntStream.range(0, hamsters.length()).forEach(i -> {
            if (hamsters.charAt(i) == 'H') {
                if (i > 0 && hamsters.charAt(i - 1) == '.') {
                    result[0]++;
                    result[1] = i - 1;
                } else if (i < hamsters.length() - 1 && hamsters.charAt(i + 1) == '.') {
                    result[0]++;
                    result[1] = i + 1;
                } else if (i == 0 || result[1] != i - 1) {
                    result[0] = -1;
                }
            }
        });
        return result[0];
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么先处理'H.H'的情况,这种顺序对最终结果有何影响?
处理'H.H'的情况可以同时喂养两边的仓鼠,是最优的食物桶使用方式。如果先处理这种情况,可以确保在食物桶数量最少的前提下,最大程度地喂养仓鼠。若先处理单边的'H.'或'.H',可能会导致需要更多的食物桶,例如对于'H.H',如果先放置两个桶在两边,就需要两个桶,而正确的做法只需要一个桶即可。
🦆
在替换'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'后,处理其周围的'H'需要具体情况具体分析。例如在'HH.HH'模式中,首先替换中间的'H.H'为'1'变为'HH1HH'。然后,需要在每个孤立的'H'旁边至少放置一个食物桶。在这个例子中,可以在第一个'H'的右边和最后一个'H'的左边各放一个食物桶,使得整个字符串中的每个'H'都至少有一个相邻的食物桶。这样,总共需要三个食物桶:一个在中间的'1',两个分别在两端的'H'旁边。

相关问题