题意整理

  • 给定一个十进制数M，将M转换为N进制数。
  • N大于10时，应在结果中使用大写字母表示大于10的一位，如'A'表示此位为10。
  • 如果M为负数，结果中要保留负号。

方法一（利用库函数）

1.解题思路

  • 首先利用java自带的库函数，将M转化为N进制数。
  • 由于结果中大于10的部分是以小写字母表示的，再通过toUpperCase函数转化为大写字母形式。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve (int M, int N) {
        //直接利用自带的进制转换，再将小写字母变为大写形式
        return new Integer(M).toString(M,N).toUpperCase();
    }
}

3.复杂度分析

  • 时间复杂度：每次M变为原来的N分之一，所以时间复杂度是O(logNM)O(log_NM)。
  • 空间复杂度：不需要额外的空间，所以空间复杂度为O(1)O(1)。

方法二（循环取余）

1.解题思路

  • 首先建立一个字符映射数组arr，用于表示大于10的情况。
  • 再用一个boolean型变量f标识M是否为负数，如果为负数，要多加一个负号。
  • 只要M不为0，不断地取余，加入到sb。并且每次将M除N。
  • 最后将得到的sb反转之后正好是所求N进制的数对应的字符串。

图解展示： alt

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve (int M, int N) {
        //记录转换后的字符串
        StringBuilder sb=new StringBuilder();
        //用于表示大于10的情况
        char[] arr={'A','B','C','D','E','F'};
        //判断是否为负数
        boolean f=false;
        if(M<0){
            //测试用例里不包含Integer.MIN_VALUE，所以可以这么写
            M=-M;
            f=true;
        }
        while(M!=0){
            //记录每一次除N的余数
            int temp=M%N;
            //大于等于10，加对应的字母
            if(temp>=10){
                sb.append(arr[temp-10]); 
            }
            //小于10，直接加到sb
            else{
                sb.append(temp); 
            }            
            M/=N;
        }
        //负数要多加一个负号
        if(f){
            sb.append('-');
        }
        //反转后转为字符串返回
        return sb.reverse().toString();
    }
}

3.复杂度分析

  • 时间复杂度：每次M变为原来的N分之一，所以时间复杂度是O(logNM)O(log_NM)。
  • 空间复杂度：arr数组大小为常数级别，需要额外常数大小的空间，所以空间复杂度为O(1)O(1)。