题解 | #进制转换#

nc112. 进制转换

题意

给你一个十进制数，求他的进制数对应的字符串。

1. 递归做法

首先看一下进制的定义：N进制就是逢N进一。
任何一个N进制数M都可以表示为如下形式：

其中，就是, 求出a0之后，我们可以继续对上式变形：

再套用上面的逻辑，对左边的数再对N取模即可得到. 以此类推可以设计递归解法，设原问题为f(M, N), 则有：

, 其中=M % N.

class Solution {
public:
    string F(int M, int N, int dep = 1) {
        // 本题数据略弱，没有考虑M为0的情况，如果不加辅助参数depth也能AC
        // 但是这里要特判一下，如果是第一层传进来就为0，那要返回0
        // 如果是递归过程中遇到了终点，要返回空字符串，否则答案中会出现前导0
        if (!M) return dep == 1 ? "0" : "";

        // 负数转化为正数
        if (M < 0) return "-" + F(-M, N);
        int a0 = M % N;
        string s0 = to_string(a0);
        if (a0 > 10) {
            s0 = 'A' + a0 - 10;
        }
        return F((M - a0) / N, N, dep+1) + s0;

    }
    string solve(int M, int N) {
        return F(M, N); // 默认为第一层，据上述公式实现
    }
};

• 时间复杂度：, 因为每次不断把M除以N，总的复杂度是对数级别。
• 空间复杂度：, 算法递归次，每次常数级别空间。

2. 非递归做法

非递归做法就是模拟我们小学奥数课的手算方法：（以4567转16进制为例，实际上也是上面的数学公式不断迭代求N的幂的系数的过程）：

因此，

用代码模拟上述过程即可。

class Solution {
public:
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    string solve(int M, int N) {
        // 特判，本题没有的数据，但是要更加严谨
        if (!M) return "0";

        // 负数转化为正数
        if (M < 0) return "-" + solve(-M, N);
        string res;
        // 迭代出口为M=0
        while(M) {
            int a = M%N; // 求余数
            string s = to_string(a);
            if (a > 10) {
                s = 'A' + a - 10;
            }
            // 向前拼接
            res = s + res;
            // 求商，进行下一轮迭代
            M /= N;
        }
        return res;
    }
};

• 时间复杂度：, 因为每次不断把M除以N，总的复杂度是对数级别。
• 空间复杂度：, 变量res的长度是M的对数级别。