网站建设 类,免费做简单网站,wordpress换域名后图片无法显示,类似站酷的设计网站作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的基础知识点
二分查找算法合集
自写二分函数 的封装
我暂时只发现两种#xff1a; 一#xff0c;在左闭右开的区间寻找最后一个符合条件的元素#xff0c;我封装成FindEnd函数。…作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的基础知识点
二分查找算法合集
自写二分函数 的封装
我暂时只发现两种 一在左闭右开的区间寻找最后一个符合条件的元素我封装成FindEnd函数。 二在左开右闭的区间寻找第一个符合条件的元素我封装成FindFirst函数。
namespace NBinarySearch
{templateclass INDEX_TYPE,class _PrINDEX_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;}templateclass INDEX_TYPE, class _PrINDEX_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(vectorint 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 vectorint 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()
{vectorint 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
{templateclass INDEX_TYPE,class _PrINDEX_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;}templateclass INDEX_TYPE, class _PrINDEX_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(vectorint 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;vectorint m_v;
};
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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;vectorint 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);
}左闭右开的应用
C二分查找算法的应用最小好进制
Is
计算是否存在m位 k进制的1为目标数。m位iRet 进制1大于等于目标数可能有多个符合的iRet取最小值。非最小值一定不是。
namespace NBinarySearch
{templateclass INDEX_TYPE,class _PrINDEX_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;}templateclass INDEX_TYPE, class _PrINDEX_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大返回正数相等返回0n小返回负数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;}
};templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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);
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
