【C++贪心】2086. 喂食仓鼠的最小食物桶数|1622

本文涉及知识点

C++贪心

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

给你一个下标从 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 <= 10⁵
hamsters[i] 要么是 ‘H’ ，要么是 ‘.’ 。

C++贪心

对于最左边的仓鼠，左边和右边一定要放食物。右边放食物不劣于左边，右边的食物可能共用，左边的一定不能共用。处理完最左的仓鼠后，移除最左的仓鼠。问题由f(n)变成f(n-1)。
枚举仓鼠，忽略食物和空地。
如果左边有食物，处理结束。
如果右边有空位，则在右边放食物，处理结束。
如果有左边有空位，则在左边放食物，处理结束。
否则返回-1。
h[i]=‘x’,表示放食物。
避免处理边界问题，s的左右各加’.'。
统计x的数量。

不能前后加’.'，加之前"H"无解，加之后有解“xHx"。

代码

核心代码

class Solution {
		public:
			int minimumBuckets(string hamsters) {
				for (int i = 0; i  < hamsters.length(); i++) {
					if ('H' != hamsters[i]) { continue; }
					if ((i > 0) && ('x' == hamsters[i - 1])) { continue; }
					if((i+1 < hamsters.length())&& ('x' == hamsters[i + 1])) { continue; }
					
					if ((i + 1 < hamsters.length()) && ('.' == hamsters[i + 1])) { hamsters[i + 1] = 'x'; continue; }
					if ((i > 0) && ('.' == hamsters[i - 1])) { hamsters[i - 1] = 'x'; continue; }
					return -1;
				}
				return count(hamsters.begin(), hamsters.end(), 'x');
			}
		};

单元测试

string hamsters;
		TEST_METHOD(TestMethod11)
		{
			hamsters = "H..H";
			auto res = Solution().minimumBuckets(hamsters);
			AssertEx(2,res);
		}
		TEST_METHOD(TestMethod12)
		{
			hamsters = ".H.H.";
			auto res = Solution().minimumBuckets(hamsters);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			hamsters = ".HHH.";
			auto res = Solution().minimumBuckets(hamsters);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod14)
		{
			hamsters = "H";
			auto res = Solution().minimumBuckets(hamsters);
			AssertEx(-1, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。