LeetCode 补充题 10. 36进制减法

2022-01-24 HGNULB 约 15 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 补充题 10. 36进制减法

题意分析

给两个用 36 进制字符串表示的非负整数 a 和 b，求 $a - b$，结果同样用 36 进制字符串返回。

先把符号系统说清楚：36 进制每一位的取值范围是 $0$ 到 $35$，其中 $0$ 到 $9$ 沿用数字字符，$10$ 到 $35$ 用字母 a 到 z 表示。面试时要主动确认字母是大写还是小写、输出用哪一种，这属于必须问清的接口约定，而不是可以想当然的细节。

输入是字符串而不是整数，这是本题最强的信号。字符串长度没有上限，意味着数值可以远超任何内置整型的表示范围，所以「先转成整数、算完再转回去」这条路从一开始就被封死了。

减法比加法多两件麻烦事。一是结果可能为负，需要在前面补一个负号；二是本位不够减时要向高位借位，而借位能否成功取决于两个数的大小关系。

边界要提前列全：输入可能带前导零，比较大小之前必须先剥掉；两数相等时结果是 "0" 而不是空串；两数长度不同；相减的结果本身可能比被减数短很多，高位会产生一串需要抹掉的零。

解法：低位到高位模拟借位

核心思路

朴素的想法是把两个字符串各自解析成整数，相减后再转回 36 进制。瓶颈在于取值范围：$36^{13}$ 已经超过了 $9.2 \times 10^{18}$ 这个 64 位有符号整数的上限，输入只要有十三位就会静默溢出，算出的结果毫无意义。

换个角度，回到手算竖式的过程。竖式减法有一条关键性质：某一位的结果只取决于本位的被减数字、本位的减数字，以及从更低位传上来的一个借位标记，与整个数有多大完全无关。这就把一个受数值范围限制的问题，拆成了一串各自独立、只需常数空间的局部运算，字符串多长都不受影响。

具体到某一位，令本位差 $cur = x - y - borrow$。若 $cur \ge 0$，它就是本位结果，新的借位为 $0$；若 $cur < 0$，就向高位借 $1$，这个 $1$ 在本位的价值是 $36$，于是本位结果为 $cur + 36$，新的借位置为 $1$。由于 $x, y \in [0, 35]$ 且 $borrow \in {0, 1}$，$cur$ 的取值范围是 $[-36, 35]$，加一次 $36$ 一定能落回 $[0, 35]$，所以借位永远不会超过 $1$，一个布尔量就够。

维持的不变量是：处理完从低位起的第 t 位后，已经写出的这 t 位所表示的数值，加上 $borrow \times 36^t$，恰好等于 a 的低 t 位与 b 的低 t 位之差。这条不变量在 $cur \ge 0$ 和 $cur < 0$ 两个分支下都成立，因为借来的 $1$ 被记进了 borrow，价值上正好抵消掉本位多加的 $36$。

但这条不变量要一路走到最高位并且 borrow 归零，前提是被减数确实不小于减数。否则最高位借不到东西，borrow 会悬空，输出的是一个模 $36^n$ 的补数而不是真实差值。所以必须先比较两数的绝对大小，让较大的那个当被减数，把符号单独提出来最后再补上。

比较大小本身也不能靠字典序直接比。剥掉前导零之后，位数多的数一定更大；位数相同时才从最高位往低位逐位比较第一处不同。这个顺序不能颠倒。

解题步骤

先分别剥掉 a 和 b 的前导零。这一步必须在比较之前完成，因为后面的比较要用长度作为第一判据，带着前导零会让 "0012" 显得比 "12" 大。若整个串都是零，统一归约成 "0"，避免产生空串。

比较两数的绝对大小。长度不同就直接由长度定胜负；长度相同则从下标 $0$ 开始逐位比较字符对应的数值，第一处不同即可定论。注意比的是映射后的数值而不是字符本身，虽然在小写体系下两者恰好同序，但一旦混入大写字母就会错。

若比较结果为相等，直接返回 "0"。这条早退不只是省事：它把「结果为零」这种唯一会被去零逻辑削成空串的情况提前排除掉了。

若被减数较小，交换 a 和 b，并记下答案为负。交换之后就永远是大减小，主循环里再也不必操心负数。

用两个下标 i、j 分别从 a 和 b 的末尾出发，borrow 初始化为 $0$，准备一个可变缓冲区按低位到高位的顺序追加结果。缓冲区里存的是逆序，最后统一反转，比每次往头部插入要高效得多。

循环条件是 i >= 0 || j >= 0，用「或」而不是「与」。较短的那个数走完之后，缺失的位按 $0$ 补齐继续参与运算，这样才能把借位一路传到被减数的最高位。

每轮计算 cur = x - y - borrow，为负则加 $36$ 并把 borrow 置为 $1$，否则把 borrow 置为 $0$。borrow 必须在两个分支里都被显式赋值，漏掉「归零」这一支会让借位一直传下去。

循环结束后去掉高位多余的零。因为缓冲区是逆序的，高位在末尾，所以从末尾往前删。删除时保留至少一个字符作为下界，这是防止把全零结果削成空串的安全网。

若答案为负，此时把负号追加到缓冲区末尾。缓冲区还是逆序状态，末尾就是反转后的最前面，所以负号要加在这里而不是开头。

最后整体反转并转成字符串返回。

以 a = "1z0"、b = "2b" 走一遍：两串都没有前导零。比较大小时长度 $3$ 大于 $2$，所以 a 更大，不需要交换，negative 为假。i 指向 a 的下标 $2$，j 指向 b 的下标 $1$，borrow 为 $0$。

第一轮：x 取 '0' 对应的 $0$，y 取 'b' 对应的 $11$，cur = 0 - 11 - 0 = -11 小于零，加 $36$ 得 $25$，borrow 置为 $1$。数值 $25$ 映射回字符是 'p'，缓冲区变为 "p"。i 变为 $1$，j 变为 $0$。

第二轮：x 取 'z' 对应的 $35$，y 取 '2' 对应的 $2$，cur = 35 - 2 - 1 = 32 非负，borrow 置为 $0$。数值 $32$ 映射回字符是 'w'，缓冲区变为 "pw"。i 变为 $0$，j 变为 $-1$。

第三轮：i 仍非负所以 x 取 '1' 对应的 $1$，j 已越界所以 y 按 $0$ 补，cur = 1 - 0 - 0 = 1 非负，borrow 保持 $0$。缓冲区变为 "pw1"。两个下标都变为负，循环结束。

缓冲区末尾是 '1' 不是 '0'，无需去零；negative 为假，不加负号。反转后得到 "1wp"。验算：$a = 1 \times 1296 + 35 \times 36 + 0 = 2556$，$b = 2 \times 36 + 11 = 83$，差为 $2473$；而 $1 \times 1296 + 32 \times 36 + 25 = 1296 + 1152 + 25 = 2473$，完全吻合。

再看一个需要交换的例子，a = "1b"、b = "2x"。比较时长度相同，最高位 $1$ 小于 $2$，判定 a 更小，于是交换成 a = "2x"、b = "1b" 并记 negative 为真。第一轮 cur = 33 - 11 - 0 = 22，映射为 'm'，缓冲区 "m"；第二轮 cur = 2 - 1 - 0 = 1，缓冲区 "m1"。无需去零，追加负号得 "m1-"，反转后返回 "-1m"。验算：$105 - 47 = 58 = 1 \times 36 + 22$，正是 "1m"，符号为负，正确。

代码实现

class Solution {
    // 减法必须先比较两个数的绝对大小，用较大的数减较小的数，最后再决定是否补负号。
    public String sub36(String a, String b) {
        a = trimLeadingZeros(a);
        b = trimLeadingZeros(b);

        int compare = compareAbs(a, b);
        if (compare == 0) {
            return "0";
        }

        boolean negative = compare < 0;
        if (negative) {
            String swapValue = a;
            a = b;
            b = swapValue;
        }

        int i = a.length() - 1;
        int j = b.length() - 1;
        int borrow = 0;
        StringBuilder builder = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int x = 0;
            if (i >= 0) {
                x = val(a.charAt(i));
            }
            int y = 0;
            if (j >= 0) {
                y = val(b.charAt(j));
            }
            int cur = x - y - borrow;
            if (cur < 0) {
                cur += 36;
                borrow = 1;
            } else {
                borrow = 0;
            }
            builder.append(digit(cur));
            i--;
            j--;
        }

        while (builder.length() > 1 && builder.charAt(builder.length() - 1) == '0') {
            builder.deleteCharAt(builder.length() - 1);
        }

        if (negative) {
            builder.append('-');
        }

        return builder.reverse().toString();
    }

    private String trimLeadingZeros(String s) {
        int idx = 0;
        while (idx < s.length() && s.charAt(idx) == '0') {
            idx++;
        }
        if (idx == s.length()) {
            return "0";
        }
        return s.substring(idx);
    }

    private int compareAbs(String a, String b) {
        if (a.length() != b.length()) {
            return a.length() - b.length();
        }
        for (int i = 0; i < a.length(); i++) {
            int x = val(a.charAt(i));
            int y = val(b.charAt(i));
            if (x != y) {
                return x - y;
            }
        }
        return 0;
    }

    private int val(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        }
        c = Character.toLowerCase(c);
        return c - 'a' + 10;
    }

    private char digit(int v) {
        if (v < 10) {
            return (char) ('0' + v);
        }
        return (char) ('a' + v - 10);
    }
}

func sub36(a string, b string) string {
    // 减法必须先比较两个数的绝对大小，用较大的数减较小的数，最后再决定是否补负号。
    a = trimLeadingZeros36(a)
    b = trimLeadingZeros36(b)

    compare := compareAbs36(a, b)
    if compare == 0 {
        return "0"
    }

    negative := compare < 0
    if negative {
        a, b = b, a
    }

    i := len(a) - 1
    j := len(b) - 1
    borrow := 0
    res := make([]byte, 0, len(a)+1)

    for i >= 0 || j >= 0 {
        x := 0
        if i >= 0 {
            x = val36(a[i])
        }
        y := 0
        if j >= 0 {
            y = val36(b[j])
        }

        cur := x - y - borrow
        if cur < 0 {
            cur += 36
            borrow = 1
        } else {
            borrow = 0
        }

        res = append(res, digit36(cur))
        i--
        j--
    }

    for len(res) > 1 && res[len(res)-1] == '0' {
        res = res[:len(res)-1]
    }

    if negative {
        res = append(res, '-')
    }

    reverseBytes(res)
    return string(res)
}

func trimLeadingZeros36(s string) string {
    idx := 0
    for idx < len(s) && s[idx] == '0' {
        idx++
    }
    if idx == len(s) {
        return "0"
    }
    return s[idx:]
}

func compareAbs36(a, b string) int {
    if len(a) != len(b) {
        return len(a) - len(b)
    }
    for i := 0; i < len(a); i++ {
        x := val36(a[i])
        y := val36(b[i])
        if x != y {
            return x - y
        }
    }
    return 0
}

func val36(c byte) int {
    if c >= '0' && c <= '9' {
        return int(c - '0')
    }
    if c >= 'A' && c <= 'Z' {
        return int(c-'A') + 10
    }
    return int(c-'a') + 10
}

func digit36(v int) byte {
    if v < 10 {
        return byte('0' + v)
    }
    return byte('a' + v - 10)
}

func reverseBytes(arr []byte) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是两个字符串长度的较大值。剥前导零、比较大小、逐位相减、去高位零、整体反转各扫描常数遍，每一位上的字符映射和加减都是常数时间，没有任何嵌套循环。

空间复杂度：$O(n)$，结果缓冲区最长与被减数等长，再加一个可能的负号；剥前导零时切出的子串同样是 $O(n)$。除此之外只有 i、j、borrow、cur 等常数个整型变量。

关键点总结

输入以字符串给出、长度不设上限，就是在明说「不许转成内置整型」。凡是这类大数题，都要退回到竖式逐位模拟，让每一位的运算只依赖本位和一个进位或借位标记。

减法要先定符号再算数值。把「谁减谁」这件事在进入主循环之前一次性解决，主循环就能保持在「大减小」这一种情形上，分支数量少一半，正确性也容易论证。

借位只有 $0$ 和 $1$ 两种取值，这一点需要论证而不是默认：本位差的下界是 $-36$，加一次基数必定回到合法区间，所以永远不会出现连借两次。

逆序写入再统一反转，是所有竖式模拟的标准结构。它顺带决定了负号该追加在缓冲区末尾——写代码时要始终清楚手上这个缓冲区是正序还是逆序。

前导零要在比较之前剥、结果的高位零要在输出之前剥，两处方向相反、时机不同，混淆任何一处都会出错。

面试视角：这题的第一轮追问几乎必然是「如果字母有大小写混排怎么办」。答案是把字符到数值的映射抽成一个独立函数，所有读取字符的地方都走它，这样只需改一处就能适配任意符号表，比在主循环里散写判断更能体现设计感。

面试视角：另一个常见追问是「怎么推广到任意 $k$ 进制」。要能指出代码里出现的 $36$ 只有借位那一处、加上字符映射函数，把它提成参数即可通用，说明你写的是模拟框架而不是一次性的硬编码。

易错点总结

错误写法：先把两个字符串解析成 64 位整数再相减 → 输入只要有十三位，数值就超过 $36^{13} \approx 1.7 \times 10^{20}$，远超整型上限，溢出后得到的差值和真实答案毫无关系，而且不会抛异常，属于最难排查的一类错误。

错误写法：不比较绝对大小就直接用 a 减 b → 以 a = "1b"、b = "2x" 为例，最高位借不到东西，borrow 悬空为 $1$，输出 "ye" 这样一个模 $36^2$ 的补数，而正确答案是 "-1m"。

错误写法：不剥前导零就比较大小 → 比较以长度为第一判据，以 a = "12"、b = "0021" 为例会误判 b 更大而交换并置负号，最终返回 "-z"（即 $-35$），正确答案是 "-11"（即 $-37$）。

错误写法：借位时给本位加 $10$ 而不是 $36$ → 沿用了十进制的肌肉记忆。以 a = "1z0"、b = "2b" 为例，最低位得到 $-11 + 10 = -1$ 仍是负数，映射回字符时下标越界或产生非法字符。

错误写法：字符到数值的映射只写 c - '0' → 字母 'a' 会被算成 $49$，远超 $35$ 的合法上限，本位差和借位判断全部失真，且数字输入时又恰好正确，导致只在含字母的用例上出错。

错误写法：主循环条件写成 i >= 0 && j >= 0 → 较短的数走完就停。以 a = "1z0"、b = "2b" 为例只处理两位，被减数最高位的 '1' 连同它要吸收的借位一起丢失，返回 "wp" 而不是 "1wp"。

错误写法：borrow 只在需要借位时赋值为 $1$，非借位分支忘了置回 $0$ → 一旦发生过一次借位，后面每一位都会白白多减 $1$，从借位点往上的所有高位全部偏小。

错误写法：去高位零时不留「至少保留一个字符」的下界，同时又省掉了两数相等的早退 → 结果全为零时缓冲区被删空，返回空字符串而不是 "0"。

错误写法：在缓冲区反转之前把负号插到开头 → 缓冲区此时是低位在前的逆序串，负号会被反转到结果末尾。以 a = "1b"、b = "2x" 为例，缓冲区 "m1" 被写成 "-m1"，反转后输出 "1m-"，负号跑到了最后一位。

错误写法：结果为负时先算 $a - b$ 的补数再想办法取反 → 补数与真实差值之间还差一个 $36^n$ 的偏移，且 n 取多少依赖于被减数长度，远不如开头交换一次来得干净可靠。

相似题目

题目	难度	考察点
415. 字符串相加	简单	十进制加法，只有进位没有借位，也不必判符号，是本题的简化版
67. 二进制求和	简单	基数换成 $2$，字符集只有两个，适合用来验证进位逻辑与基数的解耦
2. 两数相加	中等	载体从字符串换成链表且天然低位在前，省去反转但要处理长度不等的尾部
989. 数组形式的整数加法	简单	一侧是数组一侧是整数，进位可能一次跨越多位，不能假设进位只有 $0$ 和 $1$
43. 字符串相乘	中等	竖式乘法，需要开长度为两串之和的中间数组并统一处理跨位进位