完美世界培訓機構seo研究中心vip課程
本文涉及的基礎知識點
C++二分查找
LeetCode2560. 打家劫舍 IV
沿街有一排連續(xù)的房屋。每間房屋內都藏有一定的現(xiàn)金?，F(xiàn)在有一位小偷計劃從這些房屋中竊取現(xiàn)金。
由于相鄰的房屋裝有相互連通的防盜系統(tǒng)，所以小偷 不會竊取相鄰的房屋 。
小偷的 竊取能力 定義為他在竊取過程中能從單間房屋中竊取的 最大金額 。
給你一個整數(shù)數(shù)組 nums 表示每間房屋存放的現(xiàn)金金額。形式上，從左起第 i 間房屋中放有 nums[i] 美元。
另給你一個整數(shù) k ，表示竊賊將會竊取的 最少 房屋數(shù)。小偷總能竊取至少 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。方案變換規(guī)則：刪除現(xiàn)金少的房屋，直到房間數(shù)為k。
Check函數(shù)： 是否存在方案，竊取能力小于等于mid。
cnt[0]記錄沒有竊取nums[i-1]盜竊房屋的數(shù)量,cnt[1]記錄盜竊了nums[i-1]房屋的數(shù)量。
return max(cnt[0],ctn[1]) >= k。
二分方式：尋找首端
Check函數(shù)的參數(shù)范圍：[1,1e9]
代碼
核心代碼
template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_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;}template<class _Pr>INDEX_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(vector<int>& 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 CBinarySearch<int>(1, 1e9).FindFrist(Check);}};
單元測試
vector<int> nums;int k;TEST_METHOD(TestMethod1){nums = { 1 }, k = 1;auto res = Solution().minCapability(nums, k);AssertEx(1, res);}TEST_METHOD(TestMethod2){nums = { 1000'000'000 }, k = 1;auto res = Solution().minCapability(nums, k);AssertEx(nums[0], res);}TEST_METHOD(TestMethod11){nums = { 2,3,5,9 },k=2;auto res = Solution().minCapability(nums,k);AssertEx(5, res);}TEST_METHOD(TestMethod12){nums = { 2,7,9,3,1 },k=2;auto res = Solution().minCapability(nums,k);AssertEx(2, res);}
擴展閱讀
| 我想對大家說的話 |
|---|
| 工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數(shù)據(jù)匯總》。 |
| 學習算法：按章節(jié)學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作 |
| 有效學習：明確的目標 及時的反饋 拉伸區(qū)（難度合適） 專注 |
| 聞缺陷則喜(喜缺)是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。 |
| 子墨子言之：事無終始，無務多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
| 失敗+反思=成功 成功+反思=成功 |
視頻課程
先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成戰(zhàn)斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
測試環(huán)境
操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實現(xiàn)。
