算法刷题-数组-4

        本次刷题主要是关于进制相关的题目。

题一：LeetCode66：给定一个由整数数组组成的非空数组所表示的非负整数，在该整数的基础上加 1 ，最高位存放在数组的首位，数组中每个位置只存放单个数字，你可以假设除了 0 之外，这个整数不会以 0 开头。

        这道题目的关键是要知道数字为 9 的时候，加 1 会进位，其它情况直接加上即可。还需要解决 99 999 9999 等这种需要连续进位的情况。如果遇到都是 9 的情况，我们申请一个数组，首位是 1 ，其它位置都为 0 ，就可以了。代码如下：

    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i] != 0){
                return digits;
            }
        }
        digits = new int[len + 1];
        digits[0] = 1;
        return digits;
    }

这种解法利用到了新数组每个位置上的默认值都是 0 ，这一特性。

题二：进制转换题：给定一个十进制的数 M 和需要转换的进制 N，M 是32位整数， 2 <= N <= 60

        本题有很多难点：1、超过进制最大范围之后如何准确映射到其他进制，简单的方式是采用大量的 if 判断，如果一个个定义，代码太多。

        2、需要对结果进行一次字符串反转。

        3、需要判断正负号。

解决第一个问题，我们可以定义一个长度为 16 的数组，保存 2 到 16 进制各个值进行标记，这样赋值的时候就不用考虑不同进制的转换关系了。

第二个问题用 StringBuffer 的 reverse 方法就可以进行字符串反转，

正负号可以通过一个 flag 标记进行处理。

下面是代码：

public class Solution {

    public static final String[] F = {"0", "1", "2", "3", "4",
         "5", "6", "7", "8", "9",
            "A", "B", "C", "D", "E", "F"};

    public static void main(String[] args) {
        int M = 3600;
        int N = 16;
        String solve = solve(M, N);
        System.out.println(solve);
    }

    private static String solve(int M, int N) {
        boolean flag = false;
        if (M < 0){
            flag = true;
            M = M * -1;
        }
        StringBuffer sb = new StringBuffer();
        int temp;
        while (M != 0){
            temp = M % N;
            //通过 F 数组 解决了进制转换后的映射问题
            sb.append(F[temp]);
            M = M / N;
        }
        //反转字符串
        sb.reverse();
        //判断正负号
        return (flag ? "-" : "")+ sb.toString();
    }
}

运行得到结果：E10

以上就是进制转换相关的刷题。

下一部分刷二维数组相关题目。