一、题目描述

题目大意：给定一个十进制数 M，以及需要转换的进制数 N。将十进制数 M 转化为 N 进制数。
注意审题：若 M 为负数，应在结果中保留负号。

二、算法1（数学）

解题思路

本题没有什么特别巧妙的做法，就是一个经典的十进制转换 N 进制的问题。
算法步骤如下：

• 判断正负，根据题意添加负号，然后加上为正的结果
• 只要 M 不为零，就一直取模，将余数转换为对应的字符，然后令
• 最后将答案翻转即可

数学解释

1. 考虑 M > 0, M 可以表示为 N 进制的形式：
   
   其中表示 M 在 N 进制表示下第 i 位的值，M 也记为
   考虑 M 对 N 取模，由于取模运算满足性质 ，故对 M 取模的结果为
   除了第一项，其余项都是 N 的整数倍，因此模 N 的余数为0，故 的结果为 ，这样我们就得到了 M 在 N 进制表示下的最低位，然后使得 ，这样第一项变为0，其余项 N 的次数减少1，下次取模就能够得到第二项的值，以此类推，最终得到了的 N 进制序列，由于低位应该在右，因此需要做一次翻转即可得到结果
2. M < 0，在得到的结果前加上负号即可
3. M = 0，直接返回"0"即可

代码实现

class Solution {
public:
    // 将数字转化为对应的进制数字符
    char getCh(int digit) {
        if (digit < 10) return '0' + digit;
        return 'A' + digit - 10;
    }

    string solve(int M, int N) {
        // 若为0, 直接返回
        if(M == 0) return "0";
        // 若为负数, 在前面加上负号
        if (M < 0) return "-" + solve(-M, N);
        string ans;

        // 除N取余
        while (M) {
            int digit = M % N;
            ans += getCh(digit);
            M /= N;
        }

        // 翻转一下
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

时间复杂度： M为给出的十进制数，运算的次数为
空间复杂度： 常数个中间变量

三、算法2（栈）

解题思路

核心思想同上，不过使用了栈来存储中间结果，最后一次将结果出栈即可得到最终结果

代码实现（C++11）

class Solution {
public:
    // 将数字转化为对应的进制数字符
    char getCh(int digit) {
        if (digit < 10) return '0' + digit;
        return 'A' + digit - 10;
    }

    string solve(int M, int N) {
        // 若为0, 直接返回
        if(M == 0) return "0";
        // 若为负数, 在前面加上负号
        if (M < 0) return "-" + solve(-M, N);
        string ans;

        stack<char> stk;
        // 除N取余
        while (M) {
            int digit = M % N;
            stk.push(getCh(digit));
            M /= N;
        }

        // 将元素依次出栈
        while (!stk.empty()) {
            ans += stk.top();
            stk.pop();
        }

        return ans;
    }
};

时间复杂度： M为给出的十进制数，运算的次数为
空间复杂度： 使用了栈来存放中间结果