最小好进制Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
以字符串的形式给出 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, 1018]
- n 没有前导 0
# 思路
/**
* 其实是一个满K叉树的样子,n就是满足k叉树的节点和。
* 位数其实就是k叉树的深度h=logk(n)
* 相同节点个数,当k最小,k=2,即二叉树的时候,深度最深。本题就是求得[完全最小k叉树] 就理解为满足完全树的最小k叉树吧...
* 于是乎,我们想如果能满足完全二叉树那么一定是深度最深的。深度有多深呢?log2(n).那这个就是最深的深度了max_h=log2(n)
* 最小深度就是除了一个根节点,其他节点都是叶子节点。min_h=2
* 从最大的深度开始找。
* k怎么计算?通过两个公式夹逼。
* n = k^0 + k^1 + k^2 + ... + k^(m-1) + k^m // k叉树总节点数 k < n.sqrt(m)
* (k+1)^m = ... > k^0 + k^1 + ... + k^(m-1) + k^m = n // 二次项展开式 二次项分别为k和1.所以1的n次方都是1。 k+1 > n.sqrt(m)
* 得 k < n.sqrt(m) < k+1
* k=n开m次方 就是n的1/m次方
* 然后从2位开始计算,如果sum=n就成功。
*
* sum = sum * k + 1; // 就是左移一位+1
*/
# 解法
class Solution {
/**
* 其实是一个满K叉树的样子,n就是满足k叉树的节点和。
* 位数其实就是k叉树的深度h=logk(n)
* 相同节点个数,当k最小,k=2,即二叉树的时候,深度最深。本题就是求得[完全最小k叉树] 就理解为满足完全树的最小k叉树吧...
* 于是乎,我们想如果能满足完全二叉树那么一定是深度最深的。深度有多深呢?log2(n).那这个就是最深的深度了max_h=log2(n)
* 最小深度就是除了一个根节点,其他节点都是叶子节点。min_h=2
* 从最大的深度开始找。
* k怎么计算?通过两个公式夹逼。
* n = k^0 + k^1 + k^2 + ... + k^(m-1) + k^m // k叉树总节点数 k < n.sqrt(m)
* (k+1)^m = ... > k^0 + k^1 + ... + k^(m-1) + k^m = n // 二次项展开式 二次项分别为k和1.所以1的n次方都是1。 k+1 > n.sqrt(m)
* 得 k < n.sqrt(m) < k+1
* k=n开m次方 就是n的1/m次方
* 然后从2位开始计算,如果sum=n就成功。
*
* sum = sum * k + 1; // 就是左移一位+1
*/
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
long maxh = (long)(Math.log(num) / Math.log(2)+1);
// 从大bit位开始
for (long h = maxh; h >= 2; h--) {
long k = (long) Math.pow(num, 1.0 / (h-1));
long sum = 0;
for (int i = 0; i < h; i++) {
// 左移一位+1 就是原值*k+1
sum = sum * k + 1;
if (sum == num) {
return String.valueOf(k);
}
}
}
return Long.toString(num - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 总结
- 分析出几种情况,然后分别对各个情况实现