【C++贪心】2086. 喂食仓鼠的最小食物桶数|1622
CSDN 2024-10-22 12:05:01 阅读 93
本文涉及知识点
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 <= 105
hamsters[i] 要么是 ‘H’ ,要么是 ‘.’ 。
C++贪心
对于最左边的仓鼠,左边和右边一定要放食物。右边放食物不劣于左边,右边的食物可能共用,左边的一定不能共用。处理完最左的仓鼠后,移除最左的仓鼠。问题由f(n)变成f(n-1)。
枚举仓鼠,忽略食物和空地。
如果左边有食物,处理结束。
如果右边有空位,则在右边放食物,处理结束。
如果有左边有空位,则在左边放食物,处理结束。
否则返回-1。
h[i]=‘x’,表示放食物。
避免处理边界问题,s的左右各加’.'。
统计x的数量。
不能前后加’.',加之前"H"无解,加之后有解“xHx"。
代码
核心代码
<code>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++**实现。
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。