思路：

题目的主要信息：

• 将十进制整数M转化为N进制整数，其中M可正可负可零，N最大为16
• 结果返回一个string字符串

进制之间的转化，我们常用的是连除取余法，但是因为余数可能会超过9，需要用ABCDEF来表示，我们可以事先设定一个字符串常量"0123456789ABCDEF"，每次余数对应该数字的下标即可。 连除法如下图： M=7，N=2，最终逆向连接为111 M=156，N=11，最终逆向连接为132

方法一：连除取余，逆向相加

具体做法：

使用连除法每次取余数，但是因为连除是从下取到上，因此我们连接字符串的时候每次新出现的需要连接在前头。

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

复杂度分析：

• 时间复杂度：$O\left(lo{g}_{N}M\right)O(log\_NM)$O(logN​M)，连除直到为0，就是一个log级别
• 空间复杂度：$O\left(1\right)O(1)$O(1)，返回的字符串为必要空间，因此无额外空间

方法二：连除取余+栈

具体做法：

连除取余是从下加到上，因此我们可以使用一个栈从上到下记录数据，最后遍历栈相连即可得到结果。

class Solution {
public:
    string solve(int M, int N) {
        if(M == 0)
            return "0"; //若是0，直接返回
        string ans = "";
        bool flag = false;//记录是正数还是负数
        if(M < 0){
            flag = true;
            M = -M;
        }
        string temp = "0123456789ABCDEF";
        stack<int> s;
        while(M){  //连除法
            s.push(M % N);  //自顶向下入栈
            M /= N;
        }
        if(flag)
            ans = "-";   //负数添加符号
        while(!s.empty()){
            ans += temp[s.top()];   //出栈字符相连
            s.pop();
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：$O\left(lo{g}_{N}M\right)O(log\_NM)$O(logN​M)，连除直到为0，就是一个log级别
• 空间复杂度：$O\left(lo{g}_{N}M\right)O(log\_NM)$O(logN​M)，栈空间的大小为结果的大小，即连除了多少次，故也是一个log级别