0067. Add Binary
================
题目信息
--------
:题号: 0067. 二进制求和
:难度: Easy
:主题: 字符串、二进制、双指针、进位
:原题: `LeetCode 0067 `_
:重点: 从左侧补零的逐位相加,推导到无需补齐长度的双指针进位扫描
题目重述
--------
给定两个非空二进制字符串 ``a`` 和 ``b``,返回它们相加后的二进制字符串。
两个输入都只包含字符 ``'0'`` 和 ``'1'``。除字符串 ``"0"`` 外,输入没有前导零。字符串长度均在
``[1, 10^4]`` 内,因此不能先转换为固定宽度整数再计算。
自建示例
--------
.. code-block:: text
输入:a = "10101", b = "111"
输出:"11100"
两个字符串按最低位对齐。``10101₂ = 21``,``111₂ = 7``,两者之和为 ``28``,对应二进制
``11100``。
.. code-block:: text
输入:a = "1000", b = "1000"
输出:"10000"
最高位相加后仍留下进位,因此结果比输入多一位。
.. code-block:: text
输入:a = "0", b = "0"
输出:"0"
没有任何进位,结果保持单个零。
C++ 实现
--------
.. code-block:: cpp
#include
#include
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(a.size()) - 1;
index >= 0;
--index) {
const int total =
(a[index] - '0') + (b[index] - '0') + carry;
result[index] = static_cast('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(a.size()) - 1;
int second = static_cast(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('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]``:
.. code-block:: text
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"`` 为例:
.. list-table::
:header-rows: 1
* - 当前输入位
- 旧进位
- ``total``
- 写入低位
- 新进位
* - ``1 + 0``
- 0
- 1
- 1
- 0
* - ``1 + 1``
- 0
- 2
- 0
- 1
* - ``0 + 1``
- 1
- 2
- 0
- 1
* - ``1 + 0``
- 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``。