LeetCode第67题_二进制求和_二进制求和算法题

技术文档

LeetCode 第67题：二进制求和

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：a = “11”, b = “1”
输出：“100”
解释：11 + 1 = 100（二进制）

示例 2：

输入：a = “1010”, b = “1011”
输出：“10101”
解释：1010 + 1011 = 10101（二进制）

提示

1 <= a.length, b.length <= 10^4
a 和 b 仅由字符 \'0\' 或 \'1\' 组成
字符串如果不是 \"0\" ，就不含前导零

解题思路

模拟二进制加法

这道题的关键是模拟二进制加法的过程，需要注意以下几点：

从右向左遍历两个字符串
记录进位信息
处理不等长字符串的情况
最后检查是否还有进位

具体步骤：

初始化结果字符串和进位值
从后向前遍历两个字符串
计算当前位的和与进位
更新进位值和结果字符串
处理最后的进位情况

图解思路

算法步骤分析表

步骤操作状态说明初始输入 a=“11”, b=“1” 原始输入第1步 1+1 sum=2, carry=1 最右位相加第2步 1+0+carry sum=2, carry=1 次右位加进位第3步 0+0+carry sum=1, carry=0 处理最后进位

状态/情况分析表

情况输入输出说明基本情况 “11”+“1” “100” 有进位无进位 “1”+“1” “10” 简单相加多位进位 “111”+“111” “1110” 连续进位

代码实现

C# 实现

public class Solution { public string AddBinary(string a, string b) { StringBuilder result = new StringBuilder(); int carry = 0; int i = a.Length - 1; int j = b.Length - 1; // 从右向左遍历两个字符串 while (i >= 0 || j >= 0 || carry > 0) { int sum = carry; // 获取a的当前位 if (i >= 0) { sum += a[i] - \'0\'; i--; } // 获取b的当前位 if (j >= 0) { sum += b[j] - \'0\'; j--; } // 添加当前位的结果 result.Insert(0, sum % 2); // 更新进位 carry = sum / 2; } return result.ToString(); }}

Python 实现

class Solution: def addBinary(self, a: str, b: str) -> str: result = [] carry = 0 i = len(a) - 1 j = len(b) - 1 # 从右向左遍历两个字符串 while i >= 0 or j >= 0 or carry: total = carry # 获取a的当前位 if i >= 0: total += int(a[i]) i -= 1 # 获取b的当前位 if j >= 0: total += int(b[j]) j -= 1 # 添加当前位的结果 result.append(str(total % 2)) # 更新进位 carry = total // 2 return \'\'.join(result[::-1])

C++ 实现

class Solution {public: string addBinary(string a, string b) { string result; int carry = 0; int i = a.length() - 1; int j = b.length() - 1; // 从右向左遍历两个字符串 while (i >= 0 || j >= 0 || carry > 0) { int sum = carry; // 获取a的当前位 if (i >= 0) { sum += a[i] - \'0\'; i--; } // 获取b的当前位 if (j >= 0) { sum += b[j] - \'0\'; j--; } // 添加当前位的结果 result = to_string(sum % 2) + result; // 更新进位 carry = sum / 2; } return result; }};

执行结果

执行用时：84 ms
内存消耗：37.2 MB

代码亮点

🎯 使用StringBuilder优化字符串操作
💡 统一处理了字符串长度不等的情况
🔍 巧妙处理进位逻辑
🎨 代码结构清晰，易于理解

常见错误分析

🚫 没有处理进位情况
🚫 字符串长度处理错误
🚫 字符转数字计算错误
🚫 结果字符串拼接顺序错误

解法对比

解法时间复杂度空间复杂度优点缺点字符串模拟 O(max(n,m)) O(max(n,m)) 直观易懂需要额外空间内置函数 O(n) O(1) 代码简短不符合面试要求位运算 O(n) O(1) 性能最优实现复杂

LeetCode第67题_二进制求和_二进制求和算法题