LeetCode 补充题 10. 36 进制减法
题目描述
给定两个字符串
a和b，分别表示两个 36 进制正整数。请计算a - b，并返回结果的 36 进制字符串。36 进制使用
0到9表示数值0到9，使用小写字母a到z表示数值10到35。结果为负数时，在字符串开头添加-；两数相等时返回"0"。不能先把两个字符串整体转换为十进制整数，相减后再转换回 36 进制。
示例 1：
输入：a = "48", b = "2x"
输出："1b"
解释：对应十进制计算为 152 - 105 = 47。
示例 2：
输入：a = "1b", b = "2x"
输出："-1m"
解释：对应十进制计算为 47 - 105 = -58。
提示：
- 两个输入均为非空字符串，只包含
0-9和小写字母a-z。 - 结果不保留多余前导零，数值为零时不添加负号。
题意分析
原题用两个字符串表示三十六进制正整数，计算前者减后者，并返回字符串形式的差。数码
0到9表示零到九，小写字母a到z表示十到三十五。下方实现还额外支持零和大写字母输入，输出统一使用小写。实现也会归一化输入的前导零，并去掉结果中的多余前导零；差为负时加负号，相等时返回
"0"。字符串可能超过普通整数能容纳的长度，因此不能把整个输入转成固定宽度整数再相减。
解法：低位到高位模拟借位
核心思路
[!blue]
先确定绝对值大小和结果符号，再统一执行大数减小数，可以让借位过程只处理非负结果。比较前要去掉前导零：有效位数更长的值更大；位数相同时，从高位开始按数码值比较。大小写字母表示相同数值，不能直接按原字符编码决定大小。
若两数相同，直接返回零，避免产生负零。若原被减数更小，就交换两个字符串，并记录最终需要负号；此后主循环始终保证第一个数不小于第二个数。
从最低位向高位计算。
borrow表示低位已经向当前位借走的一，当前原始差为x - y - borrow；缺失的高位按零处理。如果差为负，就向更高位借一，相当于当前位补上三十六，并把下一轮借位设为一；否则下一轮借位为零。每个数码范围为零到三十五，原始差最小为负三十六，因此最多只需借一次，加三十六后就恢复到合法数码范围。处理完一位后，它的结果已经确定，下一位只需要知道新的借位。由于已经保证大数减小数，全部数位处理完后不会还欠最高位借位。
低位先计算，所以结果缓冲是逆序的。先从缓冲末尾移除代表高位的多余零，再把负号放到缓冲末尾，最后整体反转；反转后数字顺序正确，负号也正好位于开头。
解题步骤
- 去掉两个输入的前导零，并将全零输入规范为
"0"。- 按有效长度和数码值比较大小；相等直接返回零，前者较小时交换并记录负号。
- 从右到左读取数码，计算
x - y - borrow，必要时补三十六并向高位借一。- 将每位结果转换为小写数码，追加到逆序缓冲。
- 去掉缓冲末尾的高位零，按需要追加负号，再反转并返回。
代码实现
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]
}
}
复杂度分析
设较长输入的字符数为 $L$。
- 时间复杂度：$O(L)$，去零、比较、逐位减法与反转都只做线性扫描。
- 空间复杂度：$O(L)$，用于结果缓冲及字符串处理所需空间，不把数值装入固定宽度整数。
关键点总结
[!green]
- 先比较绝对值并决定符号，逐位过程统一为大数减小数。
- 借位让当前位补三十六，同时让更高位下一轮减一。
- 输入前导零影响大小比较，输出高位零影响表示规范，分别在前后处理。
- 逆序缓冲中的负号放在最后，整体反转后才在最前面。
易错点总结
[!yellow]
- 不去前导零就按长度比较，可能误判大小和结果符号。
- 混合大小写时直接比较字符，会让编码顺序代替数码大小；应统一映射到数值。
- 本位差必须扣除已有借位，不借位时也必须把下一轮借位重新清零。
- 借位补的是三十六，不是十；字母数码也不能直接按十进制字符转换。
- 在逆序缓冲开头添加负号，反转后负号会落到末尾。
- 相等输入统一返回零，不能返回空串或负零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 21. 字符串相减 | 中等 | 减法、比较绝对值与借位框架相同，本题把基数10换成36并增加字母数码映射。 |
| 补充题 9. 36 进制加法 | 中等 | 数码转换规则相同，加法处理进位，本题处理借位并可能产生负号。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！