LeetCode 67 Add Binary 题解字符串二进制加法与进位传播的两种迭代实现leetcode 仓库多语言版本【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 articles/add-binary.md 为核心骨架系统讲解 LeetCode 67 号问题 Add Binary二进制字符串相加的两种迭代解法先反转字符串再逐位相加的直观做法以及使用双指针从末尾向前扫描的优化做法。文章结合本仓库 python/0067-add-binary.py、cpp/0067-add-binary.cpp、java/0067-add-binary.java 等多语言实现覆盖算法直觉、分步流程、复杂度分析、常见陷阱与多语言代码对照读完即可独立写出可复制、可运行的完整解法。前置知识动手解决本题前建议先熟悉以下三块基础能力它们直接决定你能否独立推导出正确解法二进制数制Binary Number System二进制只有0和1两个数字加法按位从低位向高位进行逢二进一。理解进位carry如何在相邻位之间传播是本题的核心。字符串操作String Manipulation遍历字符串、反转字符串、逐字符拼接结果串。本题的输入是两个二进制字符串输出也必须是一个字符串因此字符串的构建方式前插还是后追加再整体反转会直接影响代码效率。双指针Two Pointers用两个指针同时从两个字符串的末尾最低有效位向前遍历天然适配两串长度不同的场景长度较短的串在越界后按0处理即可。解法一反转字符串 逐位迭代直觉二进制加法与十进制笔算过程完全一致区别只是十进制有0~9十个数字、二进制只有0和1两个数字。我们从最右侧的数字最低有效位LSB开始逐位相加并把上一位产生的进位一起加进来当某一位的和 2时向更高位进位1。为了让从右往左的索引更自然解法一先把两个字符串都反转这样索引0就对应最低有效位逐位计算结果时把字符前插到结果串头部最后整体一次反转得到正确顺序的结果。仓库中 python/0067-add-binary.py 就是这一思路的直接实现。算法步骤反转输入字符串a和b便于从左到右即从低位到高位处理初始化carry 0和空的结果字符串res对位置i从0到两个字符串长度的最大值遍历取出每个字符串在i处的数字字符若i已超过该串长度则视为0计算total digitA digitB carry将total % 2转换为字符并写入结果当前位的值更新carry total / 2向高位的进位遍历结束后若carry仍为1在结果头部补1反转结果字符串并返回。多语言实现Pythonclass Solution: def addBinary(self, a: str, b: str) - str: res carry 0 a, b a[::-1], b[::-1] for i in range(max(len(a), len(b))): digitA ord(a[i]) - ord(0) if i len(a) else 0 digitB ord(b[i]) - ord(0) if i len(b) else 0 total digitA digitB carry char str(total % 2) res char res carry total // 2 if carry: res 1 res return resJavapublic class Solution { public String addBinary(String a, String b) { StringBuilder res new StringBuilder(); int carry 0; StringBuilder sa new StringBuilder(a).reverse(); StringBuilder sb new StringBuilder(b).reverse(); for (int i 0; i Math.max(sa.length(), sb.length()); i) { int digitA i sa.length() ? sa.charAt(i) - 0 : 0; int digitB i sb.length() ? sb.charAt(i) - 0 : 0; int total digitA digitB carry; char c (char)((total % 2) 0); res.append(c); carry total / 2; } if (carry 0) { res.append(1); } return res.reverse().toString(); } }Cclass Solution { public: string addBinary(string a, string b) { string res ; int carry 0; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); for (int i 0; i max(a.length(), b.length()); i) { int digitA i a.length() ? a[i] - 0 : 0; int digitB i b.length() ? b[i] - 0 : 0; int total digitA digitB carry; char c (total % 2) 0; res c; carry total / 2; } if (carry) { res 1; } reverse(res.begin(), res.end()); return res; } };JavaScriptclass Solution { /** * param {string} a * param {string} b * return {string} */ addBinary(a, b) { let res []; let carry 0; a a.split().reverse().join(); b b.split().reverse().join(); for (let i 0; i Math.max(a.length, b.length); i) { const digitA i a.length ? a[i] - 0 : 0; const digitB i b.length ? b[i] - 0 : 0; const total digitA digitB carry; const char (total % 2).toString(); res.push(char); carry Math.floor(total / 2); } if (carry) { res.push(1); } res.reverse(); return res.join(); } }C#public class Solution { public string AddBinary(string a, string b) { StringBuilder res new StringBuilder(); int carry 0; char[] sa a.ToCharArray(); char[] sb b.ToCharArray(); Array.Reverse(sa); Array.Reverse(sb); int n Math.Max(sa.Length, sb.Length); for (int i 0; i n; i) { int digitA i sa.Length ? sa[i] - 0 : 0; int digitB i sb.Length ? sb[i] - 0 : 0; int total digitA digitB carry; res.Append((char)((total % 2) 0)); carry total / 2; } if (carry 0) { res.Append(1); } char[] resultArray res.ToString().ToCharArray(); Array.Reverse(resultArray); return new string(resultArray); } }Gofunc addBinary(a string, b string) string { res : []byte{} carry : 0 aBytes : []byte(a) bBytes : []byte(b) for i, j : 0, len(aBytes)-1; i j; i, j i1, j-1 { aBytes[i], aBytes[j] aBytes[j], aBytes[i] } for i, j : 0, len(bBytes)-1; i j; i, j i1, j-1 { bBytes[i], bBytes[j] bBytes[j], bBytes[i] } n : len(aBytes) if len(bBytes) n { n len(bBytes) } for i : 0; i n; i { digitA : 0 digitB : 0 if i len(aBytes) { digitA int(aBytes[i] - 0) } if i len(bBytes) { digitB int(bBytes[i] - 0) } total : digitA digitB carry res append(res, byte(total%2)0) carry total / 2 } if carry 0 { res append(res, 1) } for i, j : 0, len(res)-1; i j; i, j i1, j-1 { res[i], res[j] res[j], res[i] } return string(res) }Kotlinclass Solution { fun addBinary(a: String, b: String): String { val res StringBuilder() var carry 0 val sa a.reversed() val sb b.reversed() for (i in 0 until maxOf(sa.length, sb.length)) { val digitA if (i sa.length) sa[i] - 0 else 0 val digitB if (i sb.length) sb[i] - 0 else 0 val total digitA digitB carry res.append((total % 2)) carry total / 2 } if (carry 0) { res.append(1) } return res.reverse().toString() } }Swiftclass Solution { func addBinary(_ a: String, _ b: String) - String { var res var carry 0 let aArr Array(a.reversed()) let bArr Array(b.reversed()) for i in 0..max(aArr.count, bArr.count) { let digitA i aArr.count ? Int(String(aArr[i]))! : 0 let digitB i bArr.count ? Int(String(bArr[i]))! : 0 let total digitA digitB carry res String(total % 2) res carry total / 2 } if carry 0 { res 1 res } return res } }Rustimpl Solution { pub fn add_binary(a: String, b: String) - String { let mut res String::new(); let mut carry 0; let a: Vecu8 a.bytes().rev().collect(); let b: Vecu8 b.bytes().rev().collect(); for i in 0..a.len().max(b.len()) { let digit_a if i a.len() { (a[i] - b0) as i32 } else { 0 }; let digit_b if i b.len() { (b[i] - b0) as i32 } else { 0 }; let total digit_a digit_b carry; res.insert(0, char::from(b0 (total % 2) as u8)); carry total / 2; } if carry 0 { res.insert(0, 1); } res } }复杂度时间复杂度$O(max(m, n))$其中 $m$ 和 $n$ 分别是字符串a和b的长度循环只遍历较长者一次空间复杂度$O(m n)$主要消耗来自两个输入字符串的反转副本以及结果字符串本身的构建。解法二双指针从末尾向前迭代最优直觉解法一虽然直观但需要为两个输入字符串各创建一份反转副本额外占用空间与时间。更优的做法是不做任何反转直接用两个指针i、j分别指向a、b的末尾最低有效位从后向前扫描边扫描边计算结果。循环一直持续到两个指针都越过各自字符串的开头并且进位也归零为止。由于结果是按从低位到高位的顺序构建的最终只需反转一次。仓库中 java/0067-add-binary.java 采用的就是这一思路且它用布尔型carry配合(c1, c2)组合的分支判断来推导当前位与进位是分支式实现的典型示例而 cpp/0067-add-binary.cpp 则用a[a.size() - i - 1]在循环内直接按下标取末位属于不反转、原地反向访问的另一种等价写法同样避免了输入反转开销。算法步骤初始化指针i、j分别指向字符串a和b的最后一个索引初始化carry 0和空的结果列表res当i 0或j 0或carry 0时循环取出a在位置i的数字i 0时视为0取出b在位置j的数字j 0时视为0计算total digitA digitB carry将total % 2追加进结果低位先入更新carry total / 2i、j各自递减反转结果并拼成字符串返回。注意第 3 步的循环条件把carry 0一并纳入这天然处理了处理完所有位后仍残留进位的情况例如1 1 10的最高位进位无需在循环外再单独补1——不过不少实现出于可读性考虑仍会在循环结束后显式检查carry再补位。多语言实现Pythonclass Solution: def addBinary(self, a: str, b: str) - str: res [] carry 0 i, j len(a) - 1, len(b) - 1 while i 0 or j 0 or carry 0: digitA int(a[i]) if i 0 else 0 digitB int(b[j]) if j 0 else 0 total digitA digitB carry res.append(total % 2) carry total // 2 i - 1 j - 1 res.reverse() return .join(map(str, res))Javapublic class Solution { public String addBinary(String a, String b) { StringBuilder res new StringBuilder(); int carry 0; int i a.length() - 1, j b.length() - 1; while (i 0 || j 0 || carry 0) { int digitA i 0 ? a.charAt(i) - 0 : 0; int digitB j 0 ? b.charAt(j) - 0 : 0; int total digitA digitB carry; res.append(total % 2); carry total / 2; i--; j--; } return res.reverse().toString(); } }Cclass Solution { public: string addBinary(string a, string b) { string res ; int carry 0; int i a.size() - 1, j b.size() - 1; while (i 0 || j 0 || carry 0) { int digitA i 0 ? a[i] - 0 : 0; int digitB j 0 ? b[j] - 0 : 0; int total digitA digitB carry; res (total % 2) 0; carry total / 2; i--; j--; } reverse(res.begin(), res.end()); return res; } };JavaScriptclass Solution { /** * param {string} a * param {string} b * return {string} */ addBinary(a, b) { let res []; let carry 0; let i a.length - 1, j b.length - 1; while (i 0 || j 0 || carry 0) { const digitA i 0 ? a[i] - 0 : 0; const digitB j 0 ? b[j] - 0 : 0; const total digitA digitB carry; res.push(total % 2); carry Math.floor(total / 2); i--; j--; } res.reverse(); return res.join(); } }C#public class Solution { public string AddBinary(string a, string b) { StringBuilder res new StringBuilder(); int carry 0; int i a.Length - 1, j b.Length - 1; while (i 0 || j 0 || carry 0) { int digitA i 0 ? a[i] - 0 : 0; int digitB j 0 ? b[j] - 0 : 0; int total digitA digitB carry; res.Append(total % 2); carry total / 2; i--; j--; } char[] resultArray res.ToString().ToCharArray(); Array.Reverse(resultArray); return new string(resultArray); } }Gofunc addBinary(a string, b string) string { res : []byte{} carry : 0 i, j : len(a)-1, len(b)-1 for i 0 || j 0 || carry 0 { digitA : 0 digitB : 0 if i 0 { digitA int(a[i] - 0) } if j 0 { digitB int(b[j] - 0) } total : digitA digitB carry res append(res, byte(total%2)0) carry total / 2 i-- j-- } for l, r : 0, len(res)-1; l r; l, r l1, r-1 { res[l], res[r] res[r], res[l] } return string(res) }Kotlinclass Solution { fun addBinary(a: String, b: String): String { val res StringBuilder() var carry 0 var i a.length - 1 var j b.length - 1 while (i 0 || j 0 || carry 0) { val digitA if (i 0) a[i] - 0 else 0 val digitB if (j 0) b[j] - 0 else 0 val total digitA digitB carry res.append(total % 2) carry total / 2 i-- j-- } return res.reverse().toString() } }Swiftclass Solution { func addBinary(_ a: String, _ b: String) - String { var res [Character]() var carry 0 let aArr Array(a) let bArr Array(b) var i aArr.count - 1 var j bArr.count - 1 while i 0 || j 0 || carry 0 { let digitA i 0 ? Int(String(aArr[i]))! : 0 let digitB j 0 ? Int(String(bArr[j]))! : 0 let total digitA digitB carry res.append(Character(String(total % 2))) carry total / 2 i - 1 j - 1 } return String(res.reversed()) } }Rustimpl Solution { pub fn add_binary(a: String, b: String) - String { let mut res Vec::new(); let mut carry 0; let a a.as_bytes(); let b b.as_bytes(); let mut i a.len() as i32 - 1; let mut j b.len() as i32 - 1; while i 0 || j 0 || carry 0 { let digit_a if i 0 { (a[i as usize] - b0) as i32 } else { 0 }; let digit_b if j 0 { (b[j as usize] - b0) as i32 } else { 0 }; let total digit_a digit_b carry; res.push(b0 (total % 2) as u8); carry total / 2; i - 1; j - 1; } res.reverse(); String::from_utf8(res).unwrap() } }复杂度时间复杂度$O(max(m, n))$其中 $m$ 和 $n$ 分别是字符串a和b的长度空间复杂度$O(max(m, n))$只消耗结果本身的存储不再为输入创建反转副本相比解法一省去了反转输入的开销。以上 $m$ 和 $n$ 均指字符串a和b的长度。常见陷阱陷阱一忘记处理最终进位所有数字位都处理完后仍然可能残留一个进位1必须把它补进结果。漏掉这一步1 1会错误地返回0而不是10。# 错误缺少最终进位检查 return .join(res) # 正确处理剩余进位 if carry: res.append(1) return .join(res)解法二的循环条件while i 0 or j 0 or carry 0已把进位纳入循环天然规避了这个问题而解法一必须在循环结束后显式判断if carry:再补位。陷阱二处理方向错误二进制加法必须从右到左从最低有效位到最高有效位逐位处理。一个常见错误是从字符串开头最高位开始正向迭代这会完全颠倒进位传播的顺序产生完全错误的结果。解法一通过先反转字符串来统一方向解法二则直接用指针从末尾起步殊途同归但都不能省去方向上的处理。陷阱三字符与数字的转换字符串里的0/1是字符不是数值。各语言实现中出现了多种转换手法Python 用ord(a[i]) - ord(0)Java/C/C#/Go/Kotlin 直接做字符减0的算术转换JavaScript 用a[i] - 0隐式转换Swift 则通过Int(String(...))强制解包。无论哪种语言漏掉字符到数值的转换都会让求和结果完全失真。仓库源码对照与延伸阅读本仓库按 LeetCode 题号统一组织多语言题解本题 67 号Add Binary的完整实现分布在python/0067-add-binary.py与解法一完全一致的反转迭代实现cpp/0067-add-binary.cpp未反转、循环内按下标a[a.size() - i - 1]反向取位的变体写法java/0067-add-binary.java双指针 布尔进位 (c1, c2)组合分支推导的实现c/0067-add-binary.c、javascript/0067-add-binary.js、typescript/0067-add-binary.ts、kotlin/0067-add-binary.kt、rust/0067-add-binary.rs 等其余语言版本。其中值得特别对照的是 javascript/0067-add-binary.js它先对较短的字符串用0.repeat(diff)做前导补零使两串等长后再从末尾逐位相加——这是第三种常见工程化写法用对齐长度替代越界补 0逻辑更直白代价是需要额外一次字符串构造。三种思路反转、双指针越界补零、前导补零对齐都可以通过上述源码横向对比学习理解它们在时间与空间上的取舍。对二进制位运算感兴趣的话还可以继续阅读仓库中同属位运算主题的其他文章如 reverse-bits.md、sum-of-two-integers.md 与 counting-bits.md它们与本篇的进位传播思想一脉相承。总结Add Binary 是一道模板级的字符串模拟题核心只有两件事——确定从低位到高位的处理方向以及正确维护进位。解法一反转字符串思路最直白、最适合作为面试中的第一版答案解法二双指针在常数级空间上更优是实际工程与竞赛中的首选。无论选哪种写完后都建议立刻用11 1、1 111、0 0、1 1这四组用例自测分别覆盖长度不等、长度相差悬殊、全零与最终进位四种边界情形即可一次性确认实现正确。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考