0067. Add Binary¶
题目信息¶
- 题号:
二进制求和
- 难度:
Easy
- 主题:
字符串、二进制、双指针、进位
- 原题:
- 重点:
从左侧补零的逐位相加,推导到无需补齐长度的双指针进位扫描
题目重述¶
给定两个非空二进制字符串 a 和 b,返回它们相加后的二进制字符串。
两个输入都只包含字符 '0' 和 '1'。除字符串 "0" 外,输入没有前导零。字符串长度均在
[1, 10^4] 内,因此不能先转换为固定宽度整数再计算。
自建示例¶
输入:a = "10101", b = "111"
输出:"11100"
两个字符串按最低位对齐。10101₂ = 21,111₂ = 7,两者之和为 28,对应二进制
11100。
输入:a = "1000", b = "1000"
输出:"10000"
最高位相加后仍留下进位,因此结果比输入多一位。
输入:a = "0", b = "0"
输出:"0"
没有任何进位,结果保持单个零。
C++ 实现¶
#include <algorithm>
#include <string>
class Solution {
private:
std::string padAndAdd(std::string a, std::string b) {
if (a.size() < b.size()) {
a.insert(a.begin(), b.size() - a.size(), '0');
}
if (b.size() < a.size()) {
b.insert(b.begin(), a.size() - b.size(), '0');
}
std::string result(a.size(), '0');
int carry = 0;
for (int index = static_cast<int>(a.size()) - 1;
index >= 0;
--index) {
const int total =
(a[index] - '0') + (b[index] - '0') + carry;
result[index] = static_cast<char>('0' + total % 2);
carry = total / 2;
}
if (carry != 0) {
result.insert(result.begin(), '1');
}
return result;
}
std::string addWithTwoPointers(
const std::string& a,
const std::string& b
) {
int first = static_cast<int>(a.size()) - 1;
int second = static_cast<int>(b.size()) - 1;
int carry = 0;
std::string reversed;
reversed.reserve(std::max(a.size(), b.size()) + 1);
while (first >= 0 || second >= 0 || carry != 0) {
int total = carry;
if (first >= 0) {
total += a[first] - '0';
--first;
}
if (second >= 0) {
total += b[second] - '0';
--second;
}
reversed.push_back(static_cast<char>('0' + total % 2));
carry = total / 2;
}
std::reverse(reversed.begin(), reversed.end());
return reversed;
}
public:
std::string addBinary(std::string a, std::string b) {
return addWithTwoPointers(a, b);
}
};
题解¶
固定宽度转换¶
输入最多包含一万位二进制数字,远超常见整数类型的表示范围。即使最终操作只是加法,转换阶段也已经发生 溢出。字符串本身就是逐位表示,因此应直接模拟二进制竖式加法。
左侧补零¶
两个二进制数相加时按最低位对齐。最直接的实现先在较短字符串左侧补零,使两者长度相同,然后使用同一个 下标从右向左处理。
每轮读取两个输入位和旧进位。三者都只可能是 0 或 1,所以总和只可能位于 [0, 3]:
resultBit = total % 2
carry = total / 2
模二得到当前结果位,整除二得到传向更高位的进位。扫描完成后若 carry == 1,就在结果前面增加一个
最高位 1。
这种方法的下标关系直观,但补零会复制并扩展输入字符串。补出的零只用于表示“该侧已经没有数位”,可以用 指针越界条件代替。
双指针对齐¶
addWithTwoPointers 分别让 first 和 second 指向两个字符串的末尾。每轮按以下顺序处理:
以旧
carry初始化total;对仍未越界的输入读取当前位;
写入
total % 2;更新
carry = total / 2;两个指针各自向左移动。
某个指针越界后,该侧本轮不再贡献数位,效果与左侧补零完全相同。两个字符串长度不同不会产生额外分支,也 不需要构造对齐后的副本。
进位不变量¶
每轮开始时,两个指针右侧的输入后缀已经全部处理。reversed 保存这些低位对应的正确结果,只是顺序为
从低位到高位;carry 保存已处理后缀向当前更高位产生的唯一影响。
当前两位与旧进位相加后,total % 2 正是本位结果,total / 2 正是下一轮需要的进位。因此处理一位后,
同一不变量继续成立。
循环条件包含 carry != 0。当两个输入指针都越界但仍有最高位进位时,循环会再执行一次并写入字符
'1'。若没有进位,循环立即结束,不会产生多余前导零。
状态演化¶
以 a = "1011"、b = "110" 为例:
当前输入位 |
旧进位 |
|
写入低位 |
新进位 |
|---|---|---|---|---|
|
0 |
1 |
1 |
0 |
|
0 |
2 |
0 |
1 |
|
1 |
2 |
0 |
1 |
|
1 |
2 |
0 |
1 |
输入均耗尽 |
1 |
1 |
1 |
0 |
追加顺序为从低位到高位,缓冲区得到 "10001";整体反转后仍为 "10001",即正确答案。
反向构造¶
竖式加法天然从最低位产生字符,而结果字符串要求最高位在前。向字符串末尾追加字符具有常数摊还成本,完成 后再整体反转一次,总工作仍为线性。
若每轮直接在字符串头部插入新字符,已有内容会被反复后移,最坏会产生平方级字符移动。反向追加再反转避免了 这一代价。
方法关系¶
padAndAdd 通过实际补零统一两个输入的下标。addWithTwoPointers 把“缺失位等于零”编码为指针越界,
删除了输入扩展过程。两种方法使用完全相同的本位公式和进位状态,主入口选择双指针实现。
复杂度分析¶
设两个字符串长度分别为 m 和 n。
左侧补零需要
O(m+n)时间,并为补齐后的输入和结果使用O(m+n)空间;双指针方法访问每个输入位一次,再反转结果,时间为
O(m+n);双指针方法除返回字符串外只维护常数个整数状态,额外工作空间为
O(1);返回字符串长度最多为
max(m,n)+1。