题解 | #进制转换#

题目描述
给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。
当 N 大于 10 以后，应在结果中使用大写字母表示大于 10 的一位，如 'A' 表示此位为 10 ， 'B' 表示此位为 11 。
若 M 为负数，应在结果中保留负号。

方法一：暴力求解--连除取余，逆向相加

求解思路
对于本题，实现进制之间的转化，我们自然想到连除取余的方法，但是题目给的是进制N，因此有可能会出现超过9的数字，因此我们先设定一个字符串常量“0123456789ABCDEF”即可。对于暴力求解，使用连除法每次取余数，连接字符串的时候每次新出现的字符需要连接在前头。

图片说明

解题代码

class Solution {
public:
    string solve(int M, int N) {
        if(M == 0)
            return "0"; // 若是0，直接返回
        string hyans = ""; 
        bool myflag = false; // 记录是正数还是负数
        if(M < 0)
        {
            myflag = true;
            M = -M;
        }
        string temp = "0123456789ABCDEF"; // 字符串常量
        while(M)
        {  //连除法
            hyans = temp[M % N] + hyans; // 新字符在前，取余
            M /= N;//连除操作
        }
        if(myflag)
            hyans = "-" + hyans; // 负数添加符号
        return hyans; // 返回结果
    }
};

复杂度分析
时间复杂度：连除操作，log级别的时间复杂度，因此为 $O(logM)$ ,M为十进制数大小。
空间复杂度：没有引入新的内存地址空间，空间复杂度为 $O(1)$

方法二：优化解法--连除取余，字符串优化

求解思路
在第一种暴力解法的基础上，我们加入一个字符串从上到下记录数据，最后对字符串中的元素进行翻转操作即可。

图片说明

解题代码

class Solution {
public:
    string solve(int M, int N) 
    {
            string t = "0123456789ABCDEF";
            string myans = ""; // 存储结果
            if(M==0)
                return "0";
            bool nag = false; // 记录负数
            if(M<0)
            {   //负数的处理
                nag = true;
                M=-M;
            }
            while(M)
            {
                 myans += t[M%N];
                 M/=N;
            }
            if(nag)
                myans+="-";
            reverse(myans.begin(), myans.end()); // 翻转
            return myans; // 返回结果
    }
};

复杂度分析
时间复杂度：连除操作，log级别的时间复杂度，因此为 $O(logM)$ ,M为十进制数大小。
空间复杂度：数组空间的大小为结果的大小，即连除了多少次，也是log级别，因此为 $O(logM)$ .