Easy

题目描述

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

示例 1：

输入：a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

提示：

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

解题思路

解题思路

这道题要求我们模拟二进制加法的过程。主要思路是从两个字符串的末尾开始，逐位相加，并处理进位。

方法一：逐位相加模拟

  • 使用两个指针分别指向两个字符串的末尾
  • 维护一个进位变量 carry
  • 从右到左逐位相加，每次计算当前位的和：sum = digit1 + digit2 + carry
  • 当前位的结果是 sum % 2，新的进位是 sum / 2
  • 将结果添加到答案字符串的前面，或者先添加到末尾最后反转

方法二：内置函数转换 虽然可以使用语言内置的进制转换函数，但这种方法可能存在整数溢出的风险，且不是本题的考查重点。

推荐解法：方法一，因为它完全模拟了二进制加法的过程，时间复杂度最优，且不会有溢出问题。

实现时有个小技巧：可以先将结果存储到数组或字符串中，最后再反转，这样避免了频繁的字符串前插操作。

代码实现

class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            
            result = char(sum % 2 + '0') + result;
            carry = sum / 2;
        }
        
        return result;
    }
};

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        
        while i >= 0 or j >= 0 or carry:
            total = carry
            if i >= 0:
                total += int(a[i])
                i -= 1
            if j >= 0:
                total += int(b[j])
                j -= 1
            
            result.append(str(total % 2))
            carry = total // 2
        
        return ''.join(reversed(result))

public class Solution {
    public string AddBinary(string a, string b) {
        StringBuilder result = new StringBuilder();
        int i = a.Length - 1;
        int j = b.Length - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            
            result.Insert(0, sum % 2);
            carry = sum / 2;
        }
        
        return result.ToString();
    }
}

var addBinary = function(a, b) {
    let result = [];
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    
    while (i >= 0 || j >= 0 || carry > 0) {
        let sum = carry;
        if (i >= 0) {
            sum += parseInt(a[i]);
            i--;
        }
        if (j >= 0) {
            sum += parseInt(b[j]);
            j--;
        }
        
        result.unshift(sum % 2);
        carry = Math.floor(sum / 2);
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(max(m, n))m 和 n 分别是字符串 a 和 b 的长度，需要遍历较长字符串的所有位
空间复杂度O(max(m, n))结果字符串的长度最多为 max(m, n) + 1

相关题目