题解 | #进制转换#

进制转换

http://www.nowcoder.com/practice/2cc32b88fff94d7e8fd458b8c7b25ec1

进制转换

描述

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

方法一（递归）

思路分析

本题需要将十进制M数转换为N进制，接着我们通过几个例子对其进行分析：

我们首先分析N=2，M=10的情况，如果我们需要将十进制数10转换为二进制数，我们要做的就是不断的将10对2进行整除，直到商小于2，并且记录所有的余数，之后将所有的余数逆序输出即可得到十进制数转换为二进制数。
我们分析当N=8，M=1000的情况，如果我们需要将十进制数1000转换为八进制数，我们要做的就是不断的将1000对8进行整除，直到商小于8，并且记录所有的余数，之后将所有的余数逆序输出即可得到十进制数转换为八进制数。
我们分析当N=16，M=10000的情况，如果我们需要将十进制数10000转换为十六进制数，我们要做的就是不断的将10000对16进行整除，直到商小于16，并且记录所有的余数，之后将所有的余数逆序输出即可得到十进制数转换为十六进制数，需要注意的是我们需要将余数大于 10 的一位使用大写字母表示，例如10使用A表示等等。

通过分析我们得到一般性的结论十进制数在转换成任何进制数时，均为除其进制取余，因为中间过程涉及逆序输出，因此使用递归的办法比较有效。需要注意的是当M小于0时，对其取负进行计算，最后增加负号即可。

图解

思路分析中的图解如下：

核心代码

import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    static String s=new String();
    public static void convert(int n,int b) {
		if(n>0) 
        {
			switch(n%b) {
			case 10:s="A"+s;break;
			case 11:s="B"+s;break;
			case 12:s="C"+s;break;
			case 13:s="D"+s;break;
			case 14:s="E"+s;break;
			case 15:s="F"+s;break;
			default:s=String.valueOf(n%b)+s;
			}
		}
		if(n!=0) {
			convert(n/b,b);
		}
	}    
    public String solve (int M, int N) {
        // write code here
        int index=1;//判断正负数标志
        if(M<0) 
        {
            M=-M; 
            index=-1;
        } 
        convert(M,N);
        if(index==-1) s="-"+s;
        return s;
    }
}

复杂度分析

时间复杂度：对M不断的整除N，因此时间复杂度为 $O( log_{N}M)$ 。
空间复杂度：该算法使用递归操作，递归过程中使用栈，栈空间为 $O( log_{N}M)$ ，因此时间复杂度为 $O( log_{N}M)$

方法二+迭代

思路分析

方法二是对方法一的改变，将递归过程转换为迭代过程，即不断的对M进行整除，然后将余数再次赋值给M，迭代的思想更易理解。

核心代码

import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    static String s=new String();
    public static void convert(int n,int b) {
		while(n>0) 
        {
			switch(n%b) {
			case 10:s="A"+s;break;
			case 11:s="B"+s;break;
			case 12:s="C"+s;break;
			case 13:s="D"+s;break;
			case 14:s="E"+s;break;
			case 15:s="F"+s;break;
			default:s=String.valueOf(n%b)+s;
			}
            n=n/b;
		}
	}    
    public String solve (int M, int N) {
        // write code here
        int index=1;//判断正负数标志
        if(M<0) 
        {
            M=-M; 
            index=-1;
        } 
        convert(M,N);
        if(index==-1) s="-"+s;
        return s;
    }
}

复杂度分析