LeetCode 题解工作台
喂食仓鼠的最小食物桶数
给你一个下标从 0 开始的字符串 hamsters ，其中 hamsters[i] 要么是： 'H' 表示有一个仓鼠在下标 i ，或者 '.' 表示下标 i 是空的。 你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，就可以喂食它。更正式地说，如果你在位置 i …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
从左到右遍历字符串，遇到 `H` 时，优先考虑右边是否有空位，如果有则放置水桶，并且跳过水桶的下一个位置；如果右边没有空位，则考虑左边是否有空位，如果有则放置水桶，否则无解。 时间复杂度 ，空间复杂度 。其中 为字符串 `street` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 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 <= 105hamsters[i]要么是'H'，要么是'.'。
解题思路
方法一：贪心
从左到右遍历字符串，遇到 H 时，优先考虑右边是否有空位，如果有则放置水桶，并且跳过水桶的下一个位置；如果右边没有空位，则考虑左边是否有空位，如果有则放置水桶，否则无解。
时间复杂度 ，空间复杂度 。其中 为字符串 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate apply dynamic programming to solve state transition problems?
- question_mark
Is the candidate able to use greedy methods for optimization problems?
- question_mark
How does the candidate handle edge cases where feeding hamsters is impossible?
常见陷阱
外企场景- error
Overlooking cases where hamsters are grouped together with no adjacent empty space.
- error
Failing to account for all possible placements of food buckets in a greedy solution.
- error
Misunderstanding the conditions under which feeding all hamsters is impossible.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow placing food buckets at non-adjacent positions only.
- arrow_right_alt
Consider different variations where hamsters need to be fed in specific sequences.
- arrow_right_alt
Extend the problem by adding constraints on the number of buckets that can be placed.