LeetCode题练习与总结：最小好进制--483

一、题目描述

以字符串的形式给出 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

二、解题思路

1. 首先将字符串 n 转换为长整型数字。
2. 由于 n 的 k 进制表示中所有数位都是 1，因此可以表示为 1 + k + k^2 + k^3 + … + k^m = n，其中 m 是 1 的个数。
3. 这是一个等比数列求和的问题，可以使用等比数列求和公式 S = (k^(m+1) - 1) / (k - 1) = n 来求解。
4. 由于 m 的最大值为 log2(n)，因此可以从 m = log2(n) 开始向下枚举，寻找满足条件的最小的 k。
5. 对于每个 m，计算 k = n^(1/m) 并检查是否满足等比数列求和公式。
6. 一旦找到满足条件的 k，即可返回。

三、具体代码

public class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        // 从最大的 m 开始枚举
        for (int m = (int)(Math.log(num) / Math.log(2)); m >= 1; m--) {
            // 计算 k 的值
            long k = (long)Math.pow(num, 1.0 / m);
            // 检查是否满足等比数列求和公式
            long sum = 0;
            long term = 1;
            for (int i = 0; i <= m; i++) {
                sum += term;
                term *= k;
            }
            // 如果满足条件，返回 k
            if (sum == num) {
                return String.valueOf(k);
            }
        }
        // 如果没有找到，返回 n-1（根据题目提示，n 一定有解）
        return String.valueOf(num - 1);
    }
}

这段代码首先将输入的字符串 n 转换为长整型数字，然后从最大的 m 值开始枚举，计算对应的 k 值，并检查是否满足等比数列求和公式。如果找到满足条件的 k，则返回对应的字符串。如果没有找到，根据题目提示，返回 n-1。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 枚举 m 的循环：循环的次数是 O(log n)，因为 m 的最大值是 log2(n)。
• 对于每个 m，我们需要计算 k 的值并检查是否满足等比数列求和公式。计算 k 的时间复杂度是 O(1)，因为 Math.pow 是一个常数时间操作。
• 检查等比数列求和公式时，我们有一个循环，该循环运行 m+1 次，因此这个循环的时间复杂度是 O(m)。

综合以上分析，总的时间复杂度是 O(log n * m)。由于 m 的最大值是 log2(n)，因此时间复杂度可以进一步表示为 O(log^2 n)。

2. 空间复杂度

• 变量 num、m、k、sum 和 term 都是常数空间，不随输入规模 n 变化。
• 没有使用额外的数据结构，如数组或集合，来存储数据。

因此，空间复杂度是 O(1)，即常数空间复杂度。

五、总结知识点

• 基本类型转换：

  • 使用 Long.parseLong(n) 将字符串 n 转换为长整型数字 num。

• 数学计算：

  • 使用 Math.log(num) 和 Math.log(2) 来计算 num 的以 2 为底的对数，从而确定枚举 m 的上限。
  • 使用 Math.pow(num, 1.0 / m) 来计算 num 的 1/m 次幂，即 k 的值。

• 循环与迭代：

  • 使用一个 for 循环来枚举 m 的值，从 log2(num) 递减到 1。
  • 在每个 m 的迭代中，使用另一个 for 循环来计算等比数列的和。

• 等比数列求和：

  • 通过循环计算等比数列的和，其中 term 代表数列的当前项，并且每次循环时乘以 k 来得到下一项。

• 条件判断：

  • 使用 if 语句来检查计算出的等比数列和是否等于 num，如果是，则找到了一个有效的好进制 k。

• 字符串处理：

  • 使用 String.valueOf(k) 将 k 转换为字符串，以便返回。

• 算法逻辑：

  • 理解并实现了一种基于数学原理的算法，该算法通过枚举和数学公式来找到最小的好进制。

• 边界条件处理：

  • 当循环结束时，如果没有找到合适的好进制，根据题目提示返回 num - 1。

• 数学知识：

  • 理解等比数列的求和公式。
  • 理解对数在算法中的应用。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。