526互联

36进制加法Java语言

发布时间 2023-07-14 23:19:25作者: BAISHUN66

三十六进制加法

题目

给两个字符串num1，num2，实现36进制的数字相加。
10进制加法，逢十进一，每个位数数字可以为0-9，最小为0，最大为9，共10种情况
36进制加法，逢36进一，每个位数数字可以为0-35，最小为0，最大为35，共36种情况，这36种情况为0-9 10种 a-z 26种
36进制通过0 - 9 和a - z表示每个位数字0 - 35的情况。

输入输出

输入 输出
bca1 a053 lcf4
zzzaa zz11 10zybb

初步分析

十进制加法我们先对齐两个数字，然后从后到前计算每个位相加结果。
1.进位问题：对于0-9的数字我们可以直接相加然后逢10进一，但这里是0-z相加，该如何做？
我们可以先将0-z转换为0-35，然后逢36进1。

//根据字符转数字
public int toNumber(char c){
    if(Character.isDigit(c)){
        return c - '0';
    }else{
        return c - 'a' + 10;
    }
}

2.两个数位数不同问题：十进制中，199+99 = 298,999+99 = 1098，所以我们这里该如何实现同时遍历两个不同位数数字从后向前遍历？
一种解决办法是将位数较少的那一个数字左边补零，例如999+99看做999+099。

//补零操作,str为目标字符串，n为需要补充0的个数
public String padWithZeros(String str, int n){
    StringBuilder sb = new StringBuilder(str);
    for(int i=0;i<n;i++){
        sb.insert(0,'0');
    }
    return sb.toString();
}

3.十进制相加后得到的和如果需要进位，减10剩下的就是该位上的结果，但是36进制相加后如果需要进位，减36后可能还剩0-35，如何通过数字0-35得到最终36进制的表示结果0-z?

public static final String DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";
public char getCharValue(int num){
    //我们发现直接通过一个0-35之间的数字转化为0-z没有很好的工具，但是0-35正好一一对应0-z，所以考虑将0-z放入数组中，通过0-35下标去取。
    return DIGITS.charAt(num);
}

我的思路

  • 传入两个字符串，记录较长字符串的长度为n作为遍历次数，遍历到n - 较短字符串长度 + 1时证明断字符串已经遍历完了，剩下根据是否进位拼接较长字符串剩余部分。
    • 存在的问题：倒着遍历字符串时，无法确定起始索引，因为两个字符串长度不同。
    • 正确做法：先把字符串长度补齐
  • 使用boolean变量标志是否进位发生，注意：每次进位只可能进1。
    • 存在缺陷：每次需要判断boolean值，然后去确定两数相加是否要加进位的那个1
    • 改进：使用int型变量count存储，每次计算两数和都加上count
  • 后续改进：1.char值转为对应的0-35数字应该包装到一个方法中2.0-35数字转为36进制值应该包装到方法中。

题解思路

  • 传入str1，str2取较长字符串长度n，通过padWithZeros方法补齐两个字符串
  • 使用StringBuilder记录加法最终结果
  • 记录是否有进位不选择boolean型而是选择int型，方便进位计算
  • 两个字符串长度一致后，从后向前遍历，每次遍历要做的事：1.将对应位置char值根据toNumber方法得到对应数字2.相加两个数字，小于36不进位，carry赋值为0，通过getCharValue方法获取对应的36进制表示形式3.大于36进位，carry赋值为1，然后getCharValue方法获取36进制表示形式4.注意相加两个数字时要加上carry
  • for循环结束后，如果carry>0代表还有进位发生，需要在结果字符串首部插入字符1。因为进位最多只可能进1位，不可能进2位。
  • 最终返回sb

图示

代码

public class Add36 {
    private static final String DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        System.out.println(getResult(str1, str2));
    }

    private static String getResult(String str1, String str2) {
        int maxLength = Math.max(str1.length(), str2.length());
        StringBuffer sb = new StringBuffer();
        int carry = 0;
        //补齐长度
        str1 = padWithZeros(str1, maxLength);
        str2 = padWithZeros(str2, maxLength);
        for (int i = maxLength - 1; i >= 0; i--) {
            char c1 = str1.charAt(i);char c2 = str2.charAt(i);
            int digit1 = getDigitValue(c1);int digit2 = getDigitValue(c2);
            int sum = digit1 + digit2 + carry;
            carry = sum / 36;
            int remainder = sum % 36;
            sb.insert(0, getCharValue(remainder));
        }
        if (carry > 0){
            sb.insert(0, getCharValue(carry));
        }
        return sb.toString();
    }

    private static char getCharValue(int remainder) {
        return DIGITS.charAt(remainder);
    }

    private static int getDigitValue(char c) {
        if (Character.isDigit(c)){
            return Character.getNumericValue(c);
        }else {
            return c - 'a' + 10;
        }
    }

    private static String padWithZeros(String str, int length) {
        StringBuilder sb = new StringBuilder(str);
        while (sb.length() < length){
            sb.insert(0, '0');
        }
        return sb.toString();
    }
}