LeetCode LCR 002. 二进制求和
题目描述
题意分析
两个非空字符串
a、b只含零和一，分别表示二进制非负整数，返回它们相加后的二进制字符串。除字符串本身为零外，输入没有前导零。两串长度可以不同，且长度可达一万，不能整体转为固定宽度整数再相加。最低位在字符串末尾，结果可能因最高位进位而比较长输入再多一位。
解法：从低位相加并维护进位
核心思路
[!blue]
二进制加法同样从低位开始，只有确定低位后，才知道传向高位的进位。用两个下标从各自末尾向左读取，较短一侧耗尽后按零参与，无需真正补出对齐字符。
循环开始时，
carry表示上一轮的进位。加入两侧当前位后，它临时表示本位总和，范围为零到三。根据“本位总和 = 两倍的新进位 + 本位数字”，先输出carry % 2，再执行carry /= 2，把同一个变量恢复为下一轮所需的零或一进位。缓冲区始终逆序保存已经确定的低位，这些位不会被尚未处理的高位改变。只有两个输入都耗尽且进位为零时，答案才完整，因此循环条件必须是两下标有效或仍有进位，三个条件取“或”。
当前生成顺序由低到高，向缓冲区末尾追加即可；最后统一反转为正常书写顺序。这样每位只追加一次，避免每轮头插导致重复搬移。两侧均为零时仍会处理输入的那一位，得到单个零字符。
解题步骤
- 将两个下标指向各自串尾，进位初始化为零。
- 任一输入未结束或进位非零时继续，将合法数位加入旧进位，耗尽的一侧贡献零。
- 先追加总和对二的余数，再将进位更新为总和整除二。
- 两个下标向左移动，越界下标后续始终按零读取。
- 全部位处理完后反转缓冲区并返回。
代码实现
class Solution {
public String addBinary(String a, String b) {
var sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
// carry 进入循环体时是上一轮的进位，累加后临时充当本位总和。
for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) {
carry += (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0);
sb.append(carry % 2);
carry /= 2;
}
// 结果是从低位往高位追加的，最后统一反转一次。
return sb.reverse().toString();
}
}
func addBinary(a string, b string) string {
i, j := len(a)-1, len(b)-1
answer := []byte{}
for carry := 0; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
if i >= 0 {
carry += int(a[i] - '0')
}
if j >= 0 {
carry += int(b[j] - '0')
}
answer = append(answer, byte(carry%2+'0'))
carry /= 2
}
for i, j := 0, len(answer)-1; i < j; i, j = i+1, j-1 {
answer[i], answer[j] = answer[j], answer[i]
}
return string(answer)
}
复杂度分析
- 时间复杂度：$O(\max(m,n))$，逐位相加至多进行较长字符串长度加一轮，末尾再线性反转。
- 空间复杂度：$O(\max(m,n))$，用于结果缓冲，其他变量为常数。
关键点总结
[!green]
carry在一轮内部先从进位变成总和，再恢复为新进位，要按此顺序使用。- 三个继续条件取“或”，共同覆盖长度不等与最终进位。
- 字符要先减去
'0'得到数位，输出也要按字符形式保存。- 低位先生成、统一反转，比逐次头插更直接且保持线性时间。
易错点总结
[!yellow]
- 短串耗尽就结束，会漏掉长串剩余高位。
- 忘记把最终进位放进循环条件，会丢掉结果新增的最高位。
- 先整除更新进位再取余，会丢失本轮应输出的数位。
- 未减字符零或未将结果转回数字字符，会混淆字符编码与位值。
- 从低位追加的缓冲必须反转，不能直接当成正常顺序返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 415. 字符串相加 | 简单 | 同样从低位向高位处理进位，原题为十进制字符串，本题进位基数为2。 |
| 43. 字符串相乘 | 中等 | 复用逐位累加与进位，乘法还要汇总不同位置的部分积。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！