2021-06-18 LeetCode每日一题
链接：https://leetcode-cn.com/problems/smallest-good-base/
标签：数学、二分查找
题目
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
输入："13"
输出："3"
解释：13 的 3 进制是 111。
输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。
输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。
提示：
- n的取值范围是 [3, 10^18]。
- 输入总是有效且没有前导 0。
分析
首先题目给的是一个字符串，范围是[3, 10^18]，我们需要把它转换为数字型进行操作，int是放不下的，所以我们这里转换为long类型。
我们要判断一个数字m是不是数字n的好进制很简单，只需要把所有位加起来看看是不是等于n即可。但这里有两个问题
- 如果你从[2, n - 1]去枚举n的所有好进制，那么肯定是会超时的，因为n的范围是[3, 10^18]。这里可以使用二分加快查找速度。
- 对于每一个可能的好进制，如何确定它有多少位。最简单的就是取long的上限即2 ^ 64，最多有64位。
这时候需要处理溢出，因为当好进制很大，并且位数很大的时候，会超过long的上限。
所以我们的思路就是：外层循环从[1, 64]，作为好进制的位，内层循环从[2, n - 1]，使用二分查找寻找每一个可能的好进制，最后求得最小的好进制即可。
编码
class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
long res = Long.MAX_VALUE;
// K（K >= 2）进制数最多不超过64位，对每一位进行二分查找
for (int i = 2; i <= 64; i++) {
// K进制有i位时，K是否是好进制
long left = 2, right = num - 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long result = checkNum(num, mid, i);
// mid是num的好进制数,直接退出本次查找
if (result == 0) {
res = Math.min(res, mid);
break;
} else if (result > 0) {
// 好进制数在mid右边
left = mid + 1;
} else if (result < 0) {
// 好进制数在mid左边
right = mid - 1;
}
}
}
return String.valueOf(res);
}
/**
* base进制位数为bit时，求对应的十进制
* base和bit都很大的时候，会超过long的范围
*/
private long checkNum(long num, long base, int bit) {
long sum = 1;
for (int i = 1; i < bit; i++) {
if (sum > ((num - 1) / base)) {
return -1;
}
sum = sum * base + 1;
}
if (sum == num) {
return 0;
} else if (sum < num) {
return 1;
} else {
return -1;
}
}
}