作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的基础知识点
自写二分函数 的封装
我暂时只发现两种：
一，在左闭右开的区间寻找最后一个符合条件的元素，我封装成FindEnd函数。
二，在左开右闭的区间寻找第一个符合条件的元素，我封装成FindFirst函数。
namespace NBinarySearch { template<class INDEX_TYPE,class _Pr> INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr) { while (rightInclue - left > 1) { const auto mid = left + (rightInclue - left) / 2; if (pr(mid)) { rightInclue = mid; } else { left = mid; } } return rightInclue; } template<class INDEX_TYPE, class _Pr> INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr) { while (right - leftInclude > 1) { const auto mid = leftInclude + (right - leftInclude) / 2; if (pr(mid)) { leftInclude = mid; } else { right = mid; } } return leftInclude; } }
左闭右开 左开右闭的例子
LeetCode33: C++算法：二分查找旋转数组
class Solution { public: int search(vector<int>& nums, int target) { int rBegin = NBinarySearch::FindFrist(-1, (int)nums.size() - 1, [&](const int mid) {return nums[mid] <= nums.back(); }); if (target <= nums.back()) { return Find(nums, rBegin, nums.size(), target); } return Find(nums, 0, rBegin, target); } int Find(const vector<int>& nums, int left, int r, int target) { int iRet = NBinarySearch::FindEnd(left,r, [&](const int mid) {return nums[mid] <= target; }); return (target == nums[iRet]) ? iRet : -1; } }; int main() { vector<int> vNums = { 1,2,3,4,6 }; auto res = Solution().search(vNums, 4); std::cout << "index:" << res; if (-1 != res) { std::cout << " value:" << vNums[res]; } }
左闭右开的例子
Leetcode2790:C++二分查找算法的应用：长度递增组的最大数目
namespace NBinarySearch { template<class INDEX_TYPE,class _Pr> INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr) { while (rightInclue - left > 1) { const auto mid = left + (rightInclue - left) / 2; if (pr(mid)) { rightInclue = mid; } else { left = mid; } } return rightInclue; } template<class INDEX_TYPE, class _Pr> INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr) { while (right - leftInclude > 1) { const auto mid = leftInclude + (right - leftInclude) / 2; if (pr(mid)) { leftInclude = mid; } else { right = mid; } } return leftInclude; } } class Solution { public: int maxIncreasingGroups(vector<int>& usageLimits) { m_c = usageLimits.size(); m_v = usageLimits; sort(m_v.begin(), m_v.end()); auto Can = [&](int len) { int i = m_c - 1; long long llNeed = 0; for (; len > 0; len--, i--) { llNeed -= (m_v[i] - len); if (m_v[i] >= len) { llNeed = max(0LL, llNeed); } } for (; i >= 0; i--) { llNeed -= m_v[i]; } return llNeed <= 0; }; return NBinarySearch::FindEnd(1, m_c + 1, Can); } int m_c; vector<int> m_v; }; template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { Solution slu; vector<int> usageLimits; int res = 0; usageLimits = { 2,2,2 }; res = slu.maxIncreasingGroups(usageLimits); Assert(res, 3); usageLimits = { 1,2,5 }; res = slu.maxIncreasingGroups(usageLimits); Assert(res, 3); usageLimits = { 2,1,2 }; res = slu.maxIncreasingGroups(usageLimits); Assert(res, 2); usageLimits = { 1,1 }; res = slu.maxIncreasingGroups(usageLimits); Assert(res, 1); //CConsole::Out(res); }
左闭右开的应用
Is
计算是否存在m位 k进制的1为目标数。m位iRet 进制1大于等于目标数，可能有多个符合的iRet，取最小值。非最小值一定不是。
namespace NBinarySearch { template<class INDEX_TYPE,class _Pr> INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr) { while (rightInclue - left > 1) { const auto mid = left + (rightInclue - left) / 2; if (pr(mid)) { rightInclue = mid; } else { left = mid; } } return rightInclue; } template<class INDEX_TYPE, class _Pr> INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr) { while (right - leftInclude > 1) { const auto mid = leftInclude + (right - leftInclude) / 2; if (pr(mid)) { leftInclude = mid; } else { right = mid; } } return leftInclude; } } class Solution { public: string smallestGoodBase(string n) { long long llN = 0; for (const auto& ch : n) { llN = (llN * 10 + ch - '0'); } for (int i = 70; i > 2; i--) { long long llRet = Is(i, llN); if (llRet > 0) { return std::to_string(llRet); } } return std::to_string(llN - 1); } long long Is(int m, long long n) { int iRet = NBinarySearch::FindEnd(2LL, n + 1LL, [&](const auto mid) {return Cmp(mid, m, n) >= 0; }); return (0 == Cmp(iRet,m,n))? iRet : 0; } //k进制的m个1和n的大小比较,n大返回正数，相等返回0，n小返回负数 long long Cmp(long long k, int m, long long n) { long long llHas = 1; for (; m > 0; m--) { if (n < llHas) { return -1; } n -= llHas; if (m > 1) {// 最后一次llHas并不使用，所以越界不影响 if (LLONG_MAX / k < llHas) { return -1; } llHas *= k; } } return n; } }; template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { Solution slu; string res; res = slu.smallestGoodBase("470988884881403701"); Assert(res, std::string("686286299")); res = slu.smallestGoodBase("2251799813685247"); Assert(res, std::string("2")); res = slu.smallestGoodBase("13"); Assert(res, std::string("3")); res = slu.smallestGoodBase("4681"); Assert(res, std::string("8")); res = slu.smallestGoodBase("1000000000000000000"); Assert(res, std::string("999999999999999999")); res = slu.smallestGoodBase("1333"); Assert(res, std::string("36")); res = slu.smallestGoodBase("463381"); Assert(res, std::string("463380")); //CConsole::Out(res); }
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
