织梦cms 做视频网站,百度智能云建站,装潢设计师,盐城做网站找哪家好本文涉及知识点
C贪心
LeetCode2086. 喂食仓鼠的最小食物桶数
给你一个下标从 0 开始的字符串 hamsters #xff0c;其中 hamsters[i] 要么是#xff1a; ‘H’ 表示有一个仓鼠在下标 i #xff0c;或者’.’ 表示下标 i 是空的。 你将要在空的位置上添加一定数量的食物桶…本文涉及知识点
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。
代码
核心代码
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((i1 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
