LeetCode 补充题 9. 36进制加法
目录
题目描述
✅ 补充题 9. 36进制加法
给定两个用 36 进制表示的非负整数字符串 num1 和 num2，返回它们之和的 36 进制字符串表示。
36 进制使用字符 '0'-'9' 表示数字 0–9，使用字符 'a'-'z' 表示数字 10–35。
题意分析
输入是两个用 36 进制书写的非负整数字符串，要求返回它们和的 36 进制字符串形式。字符与数值的映射固定：
0到9表示 0 到 9，a到z表示 10 到 35。最重要的约束信号是不能先转成整数再算。字符串长度没有上界暗示，只要稍长一点，转成 64 位整数就会溢出；何况若能转成整数，这题也就没有存在意义了。所以必须停留在字符串层面逐位处理。
第二个信号是两个字符串长度可以不同，短的那个在高位相当于补 0，处理时必须允许一侧先耗尽。
边界要留意：最高位可能产生额外进位，结果会比两个输入都长一位；输入允许是单个字符；结果是从低位往高位生成的，最终顺序与书写顺序相反。此外只需处理非负整数与加法，不必考虑负号和借位。
解法：逐位模拟 36 进制加法
核心思路
问题关键：输入可能远超整数范围，不能整体转成十进制数；应像竖式加法一样，从最低位开始逐位相加。
状态与进位：两个指针分别指向尚未处理的最低位，短串耗尽后该位按
0处理。当前和为sum = x + y + carry，本位写sum % 36，下一位进位为sum / 36。边界上界：单个数位最大为 35，因此
sum最大是 $35+35+1=71$，carry始终只能是0或1。循环条件必须包含carry != 0，这样最高位进位会自然生成新的一位，例如z + 1 = 10、z + z = 1y。不变量与正确性：每轮开始时，结果缓冲区按低位到高位保存了已处理后缀之和，
carry是该后缀向当前位的唯一进位。取模确定当前位、整除确定下一位，正是 36 进制加法定义；指针全部耗尽且无进位时，所有位均已正确处理。最后反转即可恢复正常书写顺序。
解题步骤
- 令
i、j指向两个字符串末尾，carry = 0，结果先按低位到高位追加。- 当任一指针未耗尽或仍有进位时继续；越界的一侧当前位取
0。- 把字符转成
0..35，计算当前和，将余数转回字符并更新进位。- 循环结束后反转结果。
口述样例：
1b + 2x中，最低位11+33=44，写8、进1；高位1+2+1=4，逆序缓冲区为84，反转得到48。边界检查：
0+0=0；z+1=10检查跨位进位；z+z=1y检查最大位和；100+1=101检查长度不等。
代码实现
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))$，用于保存最多比较长输入多一位的结果；除输出外为 $O(1)$。
关键点总结
- 大数不能整体转换，逐位运算让中间值始终不超过 71。
- 数字字符映射到
0..9，字母映射到10..35；反向转换的偏移必须对应。- 循环条件包含最终进位，可统一处理结果多一位的情况。
- 低位先生成时应“末尾追加 + 最后反转”；每次头插会退化为 $O(n^2)$。
- 将取模、整除中的
36换为base，同一思路即可推广到任意正进制加法。
易错点总结
- 整体转成
long：长字符串会溢出，失去高精度加法的意义。- 将
a映射为 11：a+0会错误得到b；正确值是 10。- 沿用十进制的
%10、/10：z+1会得到错误结果，必须使用 36。- 循环条件遗漏
carry：z+z会漏掉最高位1，得到y而不是1y。- 两个指针条件使用
&&：100+1会在短串耗尽时提前停止。- 忘记反转：
1b+2x会返回逆序的84，正确答案是48。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 415. 字符串相加 | 简单 | 本题的十进制原型，把 36 换成 10 即完全一致 |
| 67. 二进制求和 | 简单 | 同一模板的 base 取 2，字符集只有 0 和 1 无需字母映射 |
| LCR 002. 二进制求和 | 简单 | 与 67 题同构，适合用来验证模板参数化后是否仍然正确 |
| 66. 加一 | 简单 | 只有一个加数且加数为 1，重点在数组扩容与全 9 进位 |
| 989. 数组形式的整数加法 | 简单 | 一侧是整数而非字符串，进位可能连续跨越多位 |
| 43. 字符串相乘 | 中等 | 乘法需先在长度 m + n 的数组里累加再统一进位并去前导零 |
| 1073. 负二进制数相加 | 中等 | 基数为负导致进位可能是 -1，模板的取模整除需重新推导 |