描述

题目描述

给定我们一个十进制数, 然后给定我们要转换的一个进制, 让我们输出转换后的一个结果

样例解释

首先样例输入是

7, 2

让我们把十进制数的$77$转换为我们二进制的数, 那么我们最后的输出就是

111

题解

解法一: 取巧做法

实现思路

我们直接使用我们$JavaJava$里面自带的进制转换函数, 但是这里注意一个问题, 他返回的字母是小写的, 我们要转换为大写

代码实现

import java.util.*;


public class Solution {
    public String solve (int M, int N) {
        return Integer.toString(M ,N).toUpperCase();
    }
}

时空复杂度分析

时间复杂度: $O({}_{n}m)O(\backslash log\_nm)$

理由如下: 通过阅读源码可以知道, 其实它本质就是手动实现了一个除$NN$取余的过程

空间复杂度: $O(1)O(1)$

理由如下: 我们除了结果的那个字符串之外的所有变量都是常数级别的

解法二: 手动实现取余操作

实现思路

我们先是判断正负, 如果是正数直接一直取模, 负数先转为正数再判断

代码实现

class Solution {
    string turn = "0123456789ABCDEF";

   public:
    string solve(int M, int N) {
        if (M == 0) return 0;
        // 如果是0直接返回
        string res = "";
        // 答案字符串
        bool flag = false;
        // 记录是不是负数
        if (M < 0) {
            flag = true;
            M = abs(M);
        }
        // 如果是负数转为正数
        while (M) {
            res += turn[M % N];
            M /= N;
        }
        // 对N取模
        if (flag) res += "-";
        reverse(res.begin(), res.end());
        return res;
    }
};

时空复杂度分析

时间复杂度: $O({}_{n}m)O(\backslash log\_nm)$

理由如下: 我们其实进行了$({}_{n}m)(\backslash log\_nm)$次操作，除$nn$取余

空间复杂度: $O(1)O(1)$

理由如下: 我们除了结果的那个字符串之外的所有变量都是常数级别的