怎么查网站的域名备案价格,linux 做网站用哪个版本,桃城网站建设公司,公司起名字大全免费2023本文涉及的基础知识点
C二分查找
LeetCode2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在…本文涉及的基础知识点
C二分查找
LeetCode2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。 给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上从左起第 i 间房屋中放有 nums[i] 美元。 另给你一个整数 k 表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。 返回小偷的 最小 窃取能力。 示例 1 输入nums [2,3,5,9], k 2 输出5 解释 小偷窃取至少 2 间房屋共有 3 种方式
窃取下标 0 和 2 处的房屋窃取能力为 max(nums[0], nums[2]) 5 。窃取下标 0 和 3 处的房屋窃取能力为 max(nums[0], nums[3]) 9 。窃取下标 1 和 3 处的房屋窃取能力为 max(nums[1], nums[3]) 9 。 因此返回 min(5, 9, 9) 5 。 示例 2 输入nums [2,7,9,3,1], k 2 输出2 解释共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) 2 。 提示 1 nums.length 105 1 nums[i] 109 1 k (nums.length 1)/2
二分查找
性质一如果存在某种方案窃取能力为x则一定存在盗取了k间房屋的方案窃取能力为x。方案变换规则删除现金少的房屋直到房间数为k。 Check函数 是否存在方案窃取能力小于等于mid。 cnt[0]记录没有窃取nums[i-1]盗窃房屋的数量,cnt[1]记录盗窃了nums[i-1]房屋的数量。 return max(cnt[0],ctn[1]) k。 二分方式寻找首端 Check函数的参数范围[1,1e9]
代码
核心代码
templateclass INDEX_TYPE
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}templateclass _PrINDEX_TYPE FindFrist( _Pr pr){auto left m_iMin - 1;auto rightInclue m_iMax;while (rightInclue - left 1){const auto mid left (rightInclue - left) / 2;if (pr(mid)){rightInclue mid;}else{left mid;}}return rightInclue;}templateclass _PrINDEX_TYPE FindEnd( _Pr pr){int leftInclude m_iMin;int right m_iMax 1;while (right - leftInclude 1){const auto mid leftInclude (right - leftInclude) / 2;if (pr(mid)){leftInclude mid;}else{right mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int minCapability(vectorint nums, int k) {auto Check [](int mid) {int cnt[2] { 0 };for (const auto n: nums) {auto tmp max(cnt[0], cnt[1]);if (n mid) {cnt[1] cnt[0] 1;}else {cnt[1] 0;}cnt[0] tmp;}return max(cnt[0], cnt[1]) k;};return CBinarySearchint(1, 1e9).FindFrist(Check);}};单元测试
vectorint nums;int k;TEST_METHOD(TestMethod1){nums { 1 }, k 1;auto res Solution().minCapability(nums, k);AssertEx(1, res);}TEST_METHOD(TestMethod2){nums { 1000000000 }, k 1;auto res Solution().minCapability(nums, k);AssertEx(nums[0], res);}TEST_METHOD(TestMethod11){nums { 2,3,5,9 },k2;auto res Solution().minCapability(nums,k);AssertEx(5, res);}TEST_METHOD(TestMethod12){nums { 2,7,9,3,1 },k2;auto res Solution().minCapability(nums,k);AssertEx(2, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
