文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载导读67. 二进制求和Add Binary是 LeetCode 精选 300 刷题笔记中字符串分类下的一道 Easy 题目也是大数加法这一高频面试考点的二进制形态当数字的长度远超内置整数类型能表示的范围时必须改用字符串/数组模拟竖式加法。本文以仓库中的原始 C 解法为骨架完整继承题目、示例与实测数据并在此基础上补充标准模拟解法、位运算解法、复杂度分析与边界条件总结帮助你在笔试、面试中一次性吃透这类题目。1. 题目回顾输入输出与考点题目给定两个二进制字符串返回它们的和同样用二进制字符串表示。输入为非空字符串且只包含数字1和0。示例 1输入: a 11, b 1 输出: 100示例 2输入: a 1010, b 1011 输出: 10101核心考点可以归纳为三点大数溢出字符串长度没有上限1重复 1000 次时任何内置整数类型都无法承载因此必须用字符串模拟加法二进制进位规则满 2 进 1这与十进制满 10 进 1 的唯一区别就是进位阈值字符串与字符的算术转换1 - 0得到数值 10 1得到字符1这是处理字符数字的通用技巧。2. 思路分析为什么不能直接转数字相加最容易想到的方案是把两个字符串用stoi/stoll转成整数再相加最后转回二进制字符串。但这一步在题目给出的输入规模下是不成立的二进制串长度超过 64 位时long long已经溢出面试官考察本题的意图恰恰是手写逐位加法与字符串处理能力直接挂钩。正确思路与人类列竖式完全一致从**最低位个位**开始逐位相加同时维护一个进位carry每一位的结果为(a_i b_i carry) % 2新的进位为(a_i b_i carry) / 2。仓库笔记中记录的原始解法正是这一思路的实现只不过它选择先用reverse把低位对齐到数组头部从而免去从尾部反向遍历时对索引的繁琐控制。3. 第一版解法反转对齐 字符数组逐位进位以下是仓库笔记67.二进制求和.md中记录的第一版原始解法用 C 实现。笔记同时记录了当时的实测数据执行用时8 ms击败 48.84% 的 cpp 提交内存消耗8.7 MB击败 45.19% 的 cpp 提交。string addBinary(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); if (a.size() b.size()) swap(a, b); vectorchar res; int len b.size(), minus a.size() - b.size(); for (int i 0; i len; i) { res.push_back(b[i] - 0 a[i]); // 重叠部分字符 数值 } for (int i len; i len minus; i) res.push_back(a[i]); // 长串多出的高位直接补上 for (int i 0; i len minus - 1; i) { if (res[i] 2) { // 满 2 进 1 res[i 1] res[i 1] (res[i] - 0) / 2; // 向高一位进位 res[i] 0 (res[i] - 0) % 2; // 本位保留余数 } } string result; for (auto a : res) result a; reverse(result.begin(), result.end()); if (result[0] 1) { // 最高位仍需进位 result[0] result[0] - 2; result 1 result; // 在前面补一个 1 } return result; }3.1 分步拆解为什么这样写第一步对齐低位reverse两个字符串让个位落在下标 0。例如a 1010反转后是0101这样a[0]与b[0]恰好是同一数位后续遍历即可从低到高同步进行。第二步归一化长度if (a.size() b.size()) swap(a, b)保证a始终是较长者。随后len b.size()是重叠部分的位数minus a.size() - b.size()是a独有的高位位数。第三步合并两段先对重叠部分执行res.push_back(b[i] - 0 a[i])——注意这里把b[i]转成数值1 - 0得 1加到字符a[i]上结果可能是1、2甚至后续进位后会变成3再把a剩余的高位原样追加。此时res中每个元素都是字符且值域为0~3。第四步低位向高位传播进位遍历0到len minus - 2不含最高位本身只要当前位 2就进位res[i 1] res[i 1] (res[i] - 0) / 2;——二进制满 2 进 1当前位为2时商为 1、为3时整数除法3 / 2仍为 1恰好都向高位加 1res[i] 0 (res[i] - 0) % 2;——2取余得 0、3取余得 1本位留下余数。第五步处理最高位可能的溢出所有进位传播到最高位后若翻转后的result[0]仍 1说明最高位产生了一个新的进位就把它减 2 归位并在最前面补字符1。3.2 用示例验证流程以a 11, b 1为例阶段状态反转a 11b 1合并res [2, 1]低位11产生字符2进位传播res[1] 1→2res[0] 0得[0, 2]翻转result 20最高位处理2 - 2 0前置1得100✔3.3 复杂度分析时间复杂度O(n m)其中n、m分别为两个字符串的长度。反转、合并、进位传播、翻转各是一趟线性遍历总开销与较长串的长度成正比。空间复杂度O(max(n, m))结果容器res与结果串result各占与较长串同量级的空间未使用额外的大规模存储。4. 补充解法一标准模拟法从右往左 carry 变量相比反转对齐更常见、也更易读的写法是直接从字符串尾部向左遍历用一个carry变量贯穿全程。它在可读性上更胜一筹也是面试中最推荐优先表达的版本string addBinary(string a, string b) { int i a.size() - 1, j b.size() - 1; int carry 0; string result; while (i 0 || j 0 || carry 0) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; result char(0 sum % 2); carry sum / 2; } reverse(result.begin(), result.end()); return result; }要点说明循环条件i 0 || j 0 || carry 0天然覆盖一长一短与最后还有进位两种边界无需单独处理sum的取值范围是 0~3sum % 2是当前位、sum / 2是进位与原始解法中的进位公式完全等价结果按低位到高位依次追加最后一次性reverse即可。两种写法在算法思想上等价仓库原版是先反转、后进位标准模拟法是从右往左、边加边进位都可直接 AC。5. 补充解法二位运算思路了解即可二进制加法的另一个本质视角是位运算a b可以拆成无进位加法和与进位两部分——a ^ b得到无进位和(a b) 1得到需要继续传递的进位两者相加可能再次产生进位直到进位为 0。写成循环如下string addBinary(string a, string b) { // 先将二进制字符串转为数值再做位运算适用于长度不超长的情况 long long x stoll(a, nullptr, 2); long long y stoll(b, nullptr, 2); while (y ! 0) { long long carry (x y) 1; x x ^ y; y carry; } // 将结果转回二进制字符串 string result; if (x 0) return 0; while (x 0) { result char(0 (x 1)); x 1; } reverse(result.begin(), result.end()); return result; }这种解法在概念上很优雅但要注意它受限于内置整数类型的位宽超长输入时依然会溢出。因此它更适合作为理解异或 无进位加、与 左移 进位这一本质的辅助手段真正的通用解法仍应以字符串模拟为准。6. 易错点与边界情况清单场景说明应对一长一短如1010与1长串多出的高位要原样保留短串越界前停止取值最高位最终进位如11 1结果为100比两个输入都长收尾时必须检查 carry 是否为 1不能丢掉结果反转逐位计算结果是从低位到高位的顺序返回前必须reverse字符与数值混算1 1是字符拼接而非数值加法先- 0转数值结果再 0转回字符全零与极端长度0 0→0保证空串与纯零输入也能正确返回7. 举一反三大数加法的同源题目二进制求和属于大数加法这一家族仓库刷题笔记中与其思路高度同源的题目还包括989. 数组形式的整数加法整数K与数组形式的数字逐位相加同样是低位对齐 → 逐位求和 → 处理进位 → 反转四部曲笔记中记录了从第一版到第三版的渐进优化过程与本题的进位处理逻辑完全一致字符串分类下的其他题目如13. 罗马数字转整数等可参考字符串分类目录系统刷练。如果进一步延伸把二进制换成十进制如415. 字符串相加只需把进位阈值从2改成10其余流程一字不改——这正是逐位模拟 进位模板的普适性所在。面试中常把这类题目作为考察候选人能否把竖式加法正确地翻译成代码、并处理好边界的试金石。8. 总结67. 二进制求和是一道以字符串为载体的经典大数加法题。仓库笔记中的第一版解法采用反转对齐 字符数组逐位进位其res[i 1] (res[i] - 0) / 2与res[i] 0 (res[i] - 0) % 2两句本质上就是二进制满 2 进 1的紧凑表达而标准模拟法用carry变量把同一逻辑写得更加直观。两类写法的时间复杂度均为O(n m)空间复杂度均为O(max(n, m))。掌握这道题就掌握了字符串大数运算这一类题目的核心模板无论是校招还是社招面试都能举一反三。本文内容整理自阿秀的精选力扣 300 道算法题刷题笔记该系列按照 13 个标签数组、字符串、链表、数学、哈希表、二分查找、栈、双指针、贪心、回溯、动态规划、DFS、树分类每个标签下再按 Easy / Medium / Hard 三个等级组织适合校招、社招以及转行求职者参考不了解如何上手刷题的话可先阅读基础算法部分的使用说明。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐LeetCode-Go 题解 0067 Add BinaryGo 实现二进制字符串逐位进位加法LeetCode Go 题解 0067 Add BinaryGo 实现二进制字符串逐位进位加法 本篇文章基于 LeetCode Go 开源仓库中 0067.A示例工程LeetCode 190. 颠倒二进制位简单题解对称位、逐位分离与分组互换三种位运算构造法 | LogicStack-LeetCode 刷题笔记LeetCode 190. 颠倒二进制位简单题解对称位、逐位分离与分组互换三种位运算构造法 | LogicStack LeetCode 刷题笔记 导读 本教程文档算法通关手册题解 0067二进制求和LeetCode Add Binary—— 位运算与字符串模拟实现解析算法通关手册题解 0067二进制求和LeetCode Add Binary—— 位运算与字符串模拟实现解析 本篇题解以「算法通关手册」仓库中的 add b教程文档知识库上一篇如何安全合规地处理微信数据从开源项目下架看技术合规的重要性下一篇10个JavaScript开发者必学的lodash defaultsDeep技巧告别对象属性覆盖烦恼创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考