网站建设的业务好做吗,公司网站服务器维护,免费做图片链接网站,建设网站作用本文涉及的基础知识点
二分查找
题目
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。 如果 n 的 k(k2) 进制数的所有数位全为1#xff0c;则称 k(k2) 是 n 的一个 好进制 。 示例 1#xff1a; 输入#xff1a;n “13” 输出#xff1a;“3” …本文涉及的基础知识点
二分查找
题目
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。 如果 n 的 k(k2) 进制数的所有数位全为1则称 k(k2) 是 n 的一个 好进制 。 示例 1 输入n “13” 输出“3” 解释13 的 3 进制是 111。 示例 2 输入n “4681” 输出“8” 解释4681 的 8 进制是 11111。 示例 3 输入n “1000000000000000000” 输出“999999999999999999” 解释1000000000000000000 的 999999999999999999 进制是 11。 参数范围 n 的取值范围是 [3, 10^18] n 没有前导 0
分析
值相等进制越小位数越多。进制最小是21018大约是264次方放宽些假定最大长度为70 求最小的k也就是最大的位数对应的进制 主函数从大到小尝试各位数能否存在好进制 Is函数利用二分法判断是否存k进制的m位1刚好等于n如果存在则返回k否则返回0。 由于n3所以11一定是好进制。也就是本题一定有解。 Cmp函数k进制的m个1和n的大小比较,n大返回正数相等返回0n小返回负数。llHas记录当前位的值。 注意各值的范围
代码
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) { long long left 2, right n 1; while (right - left 0 ) { const auto mid left (right - left) / 2; const auto llRet Cmp(mid, m, n); if (0 llRet) { return mid; } if (llRet 0) { left mid1; } else { right mid; } } return 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; } };
测试用例
template void Assert(const T t1, const T t2) { assert(t1 t2); }
template void Assert(const vector v1, const vector 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
