华为OD机试真题 - N进制减法

    static char[] map = new char[35];
    public static void main(String[] args) {
        for (int i = 0; i < map.length; i++) {
            if (i < 10)
                map[i] = (char) ('0' + i);
            else
                map[i] = (char) ('a' + i - 10);
        }
        Scanner inputScanner = new Scanner(System.in);

        int base = inputScanner.nextInt();
        String num1 = inputScanner.next(); // 被减数
        String num2 = inputScanner.next(); // 减数
        StringBuilder num1Builder = new StringBuilder(num1);
        StringBuilder num2Builder = new StringBuilder(num2);
        if (num1Builder.length() > num2Builder.length()) {
            System.out.print(0 + &quot; &quot;);
            System.out.print(getResult(num1Builder, num2Builder, base));
        } else if (num1Builder.length() < num2Builder.length()) {
            System.out.print(1 + &quot; &quot;);
            System.out.println(getResult(num2Builder, num1Builder, base));
        } else {
            for (int i = 0; i < num1Builder.length(); i++) {
                if (num1Builder.charAt(i) > num2Builder.charAt(i)) {
                    System.out.print(0 + &quot; &quot;);
                    System.out.print(getResult(num1Builder, num2Builder, base));
                    break;
                } else if (num1Builder.charAt(i) < num2Builder.charAt(i)){
                    System.out.print(1 + &quot; &quot;);
                    System.out.println(getResult(num2Builder, num1Builder, base));
                    break;
                }
                if (num1Builder.length() - 1 == i) {
                    System.out.print(0 + &quot; &quot;);
                    System.out.print(0);
                }
            }

        }
    }

    public static String getResult(StringBuilder num1Builder, StringBuilder num2Builder, int base) {
        StringBuilder ans = new StringBuilder();
        num1Builder.reverse();
        num2Builder.reverse();
        for (int i = 0; i < num1Builder.length(); i++) {
            if (i >= num2Builder.length()) {
                ans.append(num1Builder.substring(i, num1Builder.length()));
                break;
            }

            char num1 = num1Builder.charAt(i);
            char num2 = num2Builder.charAt(i);
            if (num1 >= num2)
                ans.append(map[num1 - num2]);
            else {
                backtrack(num1Builder, 1 , i, base);
                ans.append(map[num1 + base - num2]);
            }
        }
        return ans.reverse().toString();
    }

    public static void backtrack(StringBuilder num1Builder, int index, int i, int base) {
        if (num1Builder.charAt(i + index) != '0') {
            char ch = num1Builder.charAt(i + index);
            num1Builder.delete(i + index, i + index + 1);
            num1Builder.insert(i + index, (char)(ch - 1));
        } else {
            backtrack(num1Builder, index + 1 , i, base);
            num1Builder.delete(i + index, i + index + 1);
            num1Builder.insert(i + index, (char)(base - 1));
        }
    }