LeetCode 67：二进制求和（详细技术解析）

LeetCode 67二进制求和详细技术解析大家好今天给大家带来 LeetCode 简单难度题目——67. 二进制求和这道题是二进制运算的经典入门题考察对二进制加法规则、进位处理的理解同时涉及字符串操作技巧适合巩固基础编程思维也是面试中常见的基础考点。本文将从题目解析、多种解题思路、代码实现、避坑指南到同类问题扩展一步步讲透新手也能轻松掌握进阶学习者也能收获优化思路。一、题目背景与描述题目核心要求给定两个二进制字符串 a 和 b按照二进制加法规则计算它们的和并以二进制字符串的形式返回结果。关键说明核心约束二进制字符串仅由字符 ‘0’ 或 ‘1’ 组成长度范围 1 ≤ 长度 ≤ 10⁴需考虑大数处理避免直接转十进制溢出字符串若不是 “0”则不含前导零输入无需处理前导零输出也需遵循此规则如不能返回 “0100”需返回 “100”二进制加法规则逢二进一0000111110本位为0进位为111111本位为1进位为1。1. 输入输出示例帮助理解题意示例 1输入a 11, b 1→ 输出100计算过程对齐低位逐位相加处理进位低位对齐a “11”b 1补前导零对齐第0位最低位1 1 10 → 本位0进位1第1位1 0 进位1 10 → 本位0进位1进位1无对应位直接补在最高位组合结果1 0 0 → 即 “100”。示例 2输入a 1010, b 1011→ 输出10101计算过程低位对齐a “1010”b “1011”长度一致无需补零第0位0 1 1 → 本位1进位0第1位1 1 10 → 本位0进位1第2位0 0 进位1 1 → 本位1进位0第3位1 1 10 → 本位0进位1进位1补在最高位组合结果1 0 1 0 1 → 即 “10101”。2. 题目提示易错点提前规避长度约束10⁴ 位的二进制字符串若直接转为十进制计算会超出多数语言的整数范围Python 无此问题但仍不推荐需掌握通用解法前导零约束输出结果不能有前导零除非结果本身是 “0”如 a“0”b“0”输出 “0”而非 “00”进位处理需全程跟踪进位直到所有位处理完毕且进位为0避免遗漏最高位的进位。二、解题思路分析多种思路由浅入深本题的核心逻辑是模拟二进制加法的手工计算过程从低位到高位逐位相加同步处理进位最后将结果反转因逐位计算是从低位到高位存储顺序相反并处理前导零。以下提供3种常用思路新手优先掌握思路一模拟手工计算通用且易理解思路二Python 内置函数简化适合实际开发思路三位运算优化面试加分。思路一模拟手工加法最通用推荐新手核心思想模仿我们手工计算二进制加法的过程从两个字符串的末尾低位开始逐位相加记录本位结果和进位最后将结果反转得到最终答案。初始化指针i 指向 a 的末尾a[-1]j 指向 b 的末尾b[-1]进位 carry 0结果列表 res []用列表存储本位结果避免字符串拼接的效率损耗循环处理直到 i、j 都遍历完且 carry 为 0获取当前位的数值a_val int(a[i]) if i ≥ 0 else 0b_val int(b[j]) if j ≥ 0 else 0计算当前位的和total a_val b_val carry确定本位结果current total % 2二进制加法逢二进一取余得到本位更新进位carry total // 2取商得到进位0或1将本位结果加入 res 列表此时存储的是从低位到高位的顺序指针左移i - 1j - 1反转 res 列表将其转为字符串此时得到从高位到低位的正确顺序返回结果无需处理前导零因循环结束后无多余前导零除非结果为 “0”。优势逻辑清晰完全模拟手工计算不依赖任何内置函数适用于所有编程语言无溢出问题劣势需手动处理指针和进位步骤稍多但难度低。思路二Python 内置函数简化最简洁适合实际开发核心思想利用 Python 内置的进制转换函数将二进制字符串转为十进制整数求和后再转为二进制字符串最后去掉前缀 “0b”。将二进制字符串 a、b 转为十进制整数int(a, 2)、int(b, 2)int 函数的第二个参数表示进制计算两个十进制整数的和sum_val int(a, 2) int(b, 2)将和转为二进制字符串bin(sum_val)结果为 “0bxxxx” 格式去掉前缀 “0b”返回剩余部分即最终的二进制求和结果。优势代码极简开发效率高无需手动处理进位和指针劣势依赖 Python 内置函数若二进制字符串过长超过 Python 整数范围虽 Python 无此限制但其他语言有此方法不适用面试中若要求手动实现加法不建议使用。思路三位运算优化进阶面试高频核心思想利用二进制的位运算特性替代加法运算避免使用算术加法进一步提升效率适合深入理解二进制特性。关键位运算规则二进制异或模拟无进位加法000011110与二进制加法本位结果一致无进位与获取进位000010111再左移1位1得到进位的位置循环将异或结果作为新的 a与运算左移后的结果作为新的 b直到 b 为 0无进位此时 a 即为求和结果。步骤将二进制字符串 a、b 转为整数 x、y循环while y ! 0还有进位carry (x y) 1计算进位x x ^ y计算无进位和y carry更新进位下一轮处理将 x 转为二进制字符串去掉前缀 “0b”返回结果。优势效率高利用位运算特性避免算术运算的开销劣势逻辑较抽象需熟练掌握位运算规则适合面试中展示对二进制的理解。关键辅助二进制加法基础新手必看本位和计算当前两位数字 进位结果的个位为当前本位十位为新的进位指针处理从字符串末尾开始逐步左移直到所有位处理完毕同时需处理其中一个字符串先遍历完的情况补0继续计算结果反转因逐位计算是从低位到高位存储在列表中是逆序需反转后才能得到正确的高位到低位顺序。三、复杂度分析思路一模拟手工加法时间复杂度O(max(len(a), len(b)))最多遍历两个字符串中较长的一个长度 1处理最后进位属于线性时间空间复杂度O(max(len(a), len(b)))结果列表的长度最多为较长字符串长度 1进位属于线性空间。思路二Python 内置函数时间复杂度O(len(a) len(b))内置函数转换进制的时间与字符串长度成正比空间复杂度O(1)仅使用少量变量存储中间结果结果字符串的空间视为输出不计入额外空间。思路三位运算优化时间复杂度O(max(len(a), len(b)))循环次数与二进制字符串的最长长度成正比每轮循环处理一个进位空间复杂度O(1)仅使用少量变量存储 x、y、carry无额外空间开销。总结三种思路的时间复杂度相近实际开发中可根据需求选择简洁选思路二通用选思路一面试展示能力选思路三空间复杂度上思路二和思路三更优。四、代码实现Python严格符合要求格式带详细注释以下实现三种思路均严格遵循题目要求的类和方法格式class Solution: def addBinary(self, a: str, b: str) - str重点讲解思路一通用必掌握思路二和思路三作为补充。思路一模拟手工加法新手推荐通用解法classSolution:defaddBinary(self,a:str,b:str)-str:# 初始化指针指向字符串末尾即最低位、进位、结果列表ilen(a)-1jlen(b)-1carry0res[]# 循环处理所有位和剩余进位whilei0orj0orcarry0:# 获取当前位的数值若指针越界则视为0a_valint(a[i])ifi0else0b_valint(b[j])ifj0else0# 计算当前位的总和当前两位 进位totala_valb_valcarry# 本位结果总和取余2逢二进一currenttotal%2# 更新进位总和取商2得到0或1carrytotal//2# 将本位结果加入列表此时是低位到高位的顺序res.append(str(current))# 指针左移处理下一位高位i-1j-1# 反转列表转为字符串得到高位到低位的正确顺序return.join(reversed(res))思路二Python 内置函数简化简洁高效classSolution:defaddBinary(self,a:str,b:str)-str:# 1. 二进制字符串转十进制整数int(字符串, 2) 表示按二进制解析num_aint(a,2)num_bint(b,2)# 2. 十进制求和sum_valnum_anum_b# 3. 十进制转二进制字符串去掉前缀0breturnbin(sum_val)[2:]思路三位运算优化面试高频classSolution:defaddBinary(self,a:str,b:str)-str:# 二进制字符串转整数xint(a,2)yint(b,2)# 循环处理进位直到y为0无进位whiley!0:# 计算进位与运算获取相同位为1的位置左移1位即为进位carry(xy)1# 计算无进位和异或运算获取不同位为1的位置xx^y# 更新进位下一轮处理ycarry# 整数转二进制字符串去掉前缀0breturnbin(x)[2:]代码关键说明核心易错点指针越界处理思路一中当其中一个字符串先遍历完i0 或 j0需将其当前位视为 0避免索引错误确保所有位都能正确相加。进位处理循环条件必须包含carry 0否则会遗漏最后一位的进位如示例1中最后进位为1需补在最高位。结果反转思路一中列表存储的是从低位到高位的结果必须反转后才能得到正确的顺序否则结果会完全颠倒。前导零处理三种思路均无需额外处理前导零因为思路一循环结束后反转后的字符串无多余前导零进位只会补1不会补0思路二、三bin() 函数返回的二进制字符串无前置零除了 “0b0”转为字符串后为 “0”。大数处理思路一和思路三可处理任意长度的二进制字符串无溢出问题思路二依赖 Python 整数无大小限制的特性在其他语言中需谨慎使用。五、测试用例验证直接运行以下代码可验证题目示例确保三种思路的代码正确性同时覆盖边缘案例# 测试代码三种思路均可使用替换Solution类即可solSolution()# 示例1a 11, b 1 → 输出 100print(sol.addBinary(11,1))# 输出100# 示例2a 1010, b 1011 → 输出 10101print(sol.addBinary(1010,1011))# 输出10101# 边缘案例1a 0, b 0 → 输出 0print(sol.addBinary(0,0))# 输出0# 边缘案例2a 10000000000, b 10000000000 → 输出 100000000000print(sol.addBinary(10000000000,10000000000))# 输出100000000000# 边缘案例3a 1111, b 1111 → 输出 11110print(sol.addBinary(1111,1111))# 输出11110运行结果与预期完全一致边缘案例全0、超长字符串、全1均能正确处理三种思路的输出结果完全相同。六、常见错误与避坑指南新手常犯的4个错误一定要避开遗漏进位处理循环条件只判断 i ≥ 0 和 j ≥ 0忘记判断 carry 0导致最后一位进位被遗漏如示例1最后进位1未处理会返回 “00” 而非 “100”解决方案循环条件必须包含i 0 or j 0 or carry 0。指针越界未处理当其中一个字符串较短指针先左移到负数时未将其视为0导致索引错误解决方案用int(a[i]) if i 0 else 0处理指针越界情况。结果未反转思路一中将本位结果直接拼接字符串未用列表反转导致结果顺序颠倒如示例1得到 “001” 而非 “100”解决方案用列表存储本位结果最后反转后再转为字符串。前导零冗余手动处理结果时多余添加前导零如 a“0”b“0”返回 “00” 而非 “0”解决方案无需手动添加前导零三种思路的实现均已规避此问题。七、进阶思考与优化面试加分项1. 思路一的效率优化思路一中使用列表存储本位结果最后反转拼接比直接使用字符串拼接如 res str(current) res效率更高字符串是不可变对象每次拼接都会创建新对象时间复杂度为 O(n²)列表append是 O(1)反转是 O(n)总时间复杂度 O(n)。2. 空间优化思路一思路一的空间复杂度为 O(n)可优化为 O(1)不使用额外列表直接操作字符串但会牺牲一定的可读性适合对空间要求严格的场景代码示例如下classSolution:defaddBinary(self,a:str,b:str)-str:i,j,carrylen(a)-1,len(b)-1,0reswhilei0orj0orcarry0:a_valint(a[i])ifi0else0b_valint(b[j])ifj0else0totala_valb_valcarry resstr(total%2)res# 直接拼接无需列表反转carrytotal//2i-1j-1returnres3. 同类问题扩展巩固二进制运算思维本题属于「二进制运算」类基础题掌握本题思路后可轻松解决以下同类题目面试高频LeetCode 415. 字符串相加十进制字符串求和思路与本题思路一完全一致仅进位规则改为逢十进一LeetCode 989. 数组形式的整数加法整数的数组形式与另一个整数求和可复用模拟加法思路LeetCode 190. 颠倒二进制位二进制位运算的延伸巩固二进制操作技巧。八、总结核心考点回顾这道题的核心考点是「二进制加法规则」掌握逢二进一的计算逻辑能正确处理本位和进位「字符串操作」学会处理字符串的指针遍历、越界处理以及结果的反转和拼接「效率优化」理解列表与字符串拼接的效率差异掌握基础的优化技巧「位运算应用」掌握异或、与运算在二进制加法中的应用提升面试竞争力。本题难度较低但却是二进制运算的入门经典题也是后续复杂二进制问题如位掩码、状态压缩的基础。解题时新手优先掌握模拟手工加法的思路通用且易理解再学习内置函数和位运算的优化思路逐步提升对二进制运算的理解和应用能力。如果觉得本文对你有帮助欢迎点赞、收藏、关注你的支持是我持续创作 LeetCode 题解的动力如果有疑问也可以在评论区留言我会及时回复~后续会持续更新 LeetCode 基础算法系列题解关注不迷路咱们下期见