LeetCode 补充题 9. 36 进制加法
题目描述
给定两个字符串
num1和num2，分别表示两个 36 进制正整数。请计算它们的和，并返回结果的 36 进制字符串。36 进制使用
0到9表示数值0到9，使用小写字母a到z表示数值10到35。不能先把两个字符串整体转换为十进制整数，完成加法后再转换回 36 进制。
示例 1：
输入：num1 = "1b", num2 = "2x"
输出："48"
解释：1b、2x 和 48 分别表示十进制的 47、105 和 152。
示例 2：
输入：num1 = "z", num2 = "1"
输出："10"
提示：
- 两个字符串均非空，只包含
0-9和a-z。 - 输出继续使用小写字母表示大于
9的数位。
题意分析
原题的两个输入字符串表示正整数，数位字符为
0..9和a..z，分别对应数值0..9和10..35。求它们的和，并按同样的 36 进制规则返回字符串，字母仍使用小写。下方实现也能处理表示零的字符串，这是对原题输入范围的扩展。字符串长度可以不同；运算针对整个整数的值，不是把对应字符直接相加。逐位计算即可处理超出整数类型范围的输入，不需要先将整串转换为
int或long。
解法：逐位模拟 36 进制加法
核心思路
[!blue]
加法的进位从低位传向高位，而字符串最低位在末尾，所以用
i、j分别从两个字符串末尾向左扫描。carry表示此前低位相加传来的进位，某个字符串提前耗尽后，该侧后续数位按零参与。每轮先把当前字符转为数值。数字字符减去
'0'；字母字符减去'a'再加10。令sum = first + second + carry，根据sum = 36 * carryNext + digit，本位为sum % 36，下一位进位为sum / 36。两个数位最大均为
35，旧进位最大为1，因此sum最多为71，新的进位仍只可能是零或一。运算过程中保存的都是单个数位和进位，不会随输入总长度增大而溢出。将余数按相反的映射转回字符，追加到结果末尾。这样每轮都正确确定一个低位，并将尚未处理的高位问题交给下一轮。只有两串都耗尽且进位为零时才结束，最后反转按低位到高位生成的字符，得到正常顺序。
解题步骤
- 令
i、j指向两串末尾，carry = 0，准备结果缓冲区。- 当任一指针仍有效或还有进位时继续。读取有效数位并转换到
0..35，耗尽的一侧取零。- 计算
sum，将sum % 36编码成字符追加，令carry = sum / 36，有效输入指针各自左移。- 所有位与最终进位处理完成后，反转缓冲区并返回。
代码实现
class Solution {
public String add36Strings(String num1, String num2) {
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
StringBuilder builder = new StringBuilder();
// 两串耗尽后若仍有进位，还要生成最高位。
while (i >= 0 || j >= 0 || carry != 0) {
int first = 0;
if (i >= 0) {
first = toDigit(num1.charAt(i));
i--;
}
int second = 0;
if (j >= 0) {
second = toDigit(num2.charAt(j));
j--;
}
int sum = first + second + carry;
// 余数写入当前位，商作为下一位的进位。
builder.append(toChar(sum % 36));
carry = sum / 36;
}
return builder.reverse().toString();
}
private int toDigit(char ch) {
if (ch >= '0' && ch <= '9') {
return ch - '0';
}
return ch - 'a' + 10;
}
private char toChar(int value) {
if (value < 10) {
return (char) ('0' + value);
}
return (char) ('a' + value - 10);
}
}
func add36Strings(num1 string, num2 string) string {
i := len(num1) - 1
j := len(num2) - 1
carry := 0
res := make([]byte, 0)
// 两串耗尽后若仍有进位，还要生成最高位。
for i >= 0 || j >= 0 || carry != 0 {
first := 0
if i >= 0 {
first = toDigit(num1[i])
i--
}
second := 0
if j >= 0 {
second = toDigit(num2[j])
j--
}
sum := first + second + carry
// 余数写入当前位，商作为下一位的进位。
res = append(res, toChar(sum%36))
carry = sum / 36
}
for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
res[left], res[right] = res[right], res[left]
}
return string(res)
}
func toDigit(ch byte) int {
if ch >= '0' && ch <= '9' {
return int(ch - '0')
}
return int(ch-'a') + 10
}
func toChar(value int) byte {
if value < 10 {
return byte('0' + value)
}
return byte('a' + value - 10)
}
复杂度分析
- 时间复杂度：$O(\max(m,n))$，逐位扫描一次，最后再线性反转。
- 空间复杂度：$O(\max(m,n))$，用于保存最多比较长输入多一位的结果，包括构造结果的缓冲区。
关键点总结
[!green]
- 大数不能整体转换，逐位运算让中间值始终不超过 71。
- 数字字符映射到
0..9，字母映射到10..35；反向转换的偏移必须对应。- 循环条件包含最终进位，可统一处理结果多一位的情况。
- 低位先生成时应“末尾追加 + 最后反转”；每次头插会退化为 $O(n^2)$。
易错点总结
[!yellow]
- 整串转换为固定宽度整数会受数值范围限制，失去逐位处理长整数的作用。
- 字母
'a'对应10，字符转数值和数值转字符必须使用互为逆运算的偏移。- 本位与进位都以
36为基数，不能沿用十进制的取模和整除。- 循环条件必须包含
carry，否则会丢掉输入耗尽后的最高位进位。- 两个输入条件要用“或”，否则短串耗尽时会提前结束，漏掉长串的剩余部分。
- 当前生成顺序从低位到高位，最后必须反转；逐次头插则会增加搬移成本。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 415. 字符串相加 | 简单 | 十进制逐位加法可直接推广，本题只需把进位基数改为36并映射字母数码。 |
| 补充题 10. 36 进制减法 | 中等 | 相同进制的减法还需比较大小、处理借位及结果负号，可对照检查数码转换。 |