本文涉及的基础知识点
题目
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。
如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 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
分析
值相等，进制越小，位数越多。进制最小是2，1018大约是264次方，放宽些，假定最大长度为70
求最小的k，也就是最大的位数对应的进制
主函数，从大到小尝试各位数能否存在好进制
Is函数利用二分法判断是否存k进制的m位1刚好等于n，如果存在则返回k，否则返回0。
由于n>=3，所以11一定是好进制。也就是本题一定有解。
Cmp函数：k进制的m个1和n的大小比较,n大返回正数，相等返回0，n小返回负数。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 = mid+1; } else { right = mid; } } return 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 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 C++17
或者 操作系统：win10 开
发环境： VS2022 C++17
