当前位置：首页 > news >正文

算法leetcode｜67. 二进制求和（rust重拳出击）

news 2025/8/23 21:26:46

文章目录

67. 二进制求和：
- 样例 1：
- 样例 2：
- 提示：
分析：
题解：
- rust：
- go：
- c++：
- python：
- java：

67. 二进制求和：

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

样例 1：

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

样例 2：

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

提示：

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

分析：

面对这道算法题目，二当家的再次陷入了沉思。
直接用API将字符串按照2进制转成整型，相加，然后再按照2进制转成字符串，打完收功，但是这种方式有可能会导致整形溢出。
按照字符的方式逆向逐个处理，模拟我们手算的方式，一位一位的计算，满二进一，余数就是当前位，这种方式代码量比较大，但是不会整形溢出。需要注意的是两个数位遍历完，还要再将最后有可能的进位加进去。由于计算是按位计算，从末位开始，而结果要的是字符串，如果我们每次都将结果拼在后面，这种情况下末位相加的结果会在开头，是反向的，所以最后还需要将结果字符串反转，当然也可以每次都把按位相加的结果放在字符串的头部，这样就不需要最后再反转结果。
另外还可以使用位运算，两个二进制位只有其中一个是 '0' 另外一个是 '1' 的情况下，本位才会是 '1' ，所以可以使用位异或运算得到本位的值。而只有两个位都是 '1' 的情况下才会进位，所以可以使用位与运算得到进位的值，不会无休止的进位，最终也可以得到结果，这样可以不使用加法运算而计算出两数相加的结果。

题解：

rust：

impl Solution {pub fn add_binary(a: String, b: String) -> String {let mut ans = String::new();let mut carry = 0;(0..a.len().max(b.len())).for_each(|i| {if i < a.len() && a.as_bytes()[a.len() - 1 - i] == b'1' {carry += 1;}if i < b.len() && b.as_bytes()[b.len() - 1 - i] == b'1' {carry += 1;}if carry == 1 || carry == 3 {ans.push('1');} else {ans.push('0');}carry /= 2;});if carry > 0 {ans.push('1');}return ans.chars().rev().collect();}
}

go：

func addBinary(a string, b string) string {ans := ""carry := 0lenA, lenB := len(a), len(b)n := lenAif lenB > lenA {n = lenB}for i := 0; i < n; i++ {if i < lenA {carry += int(a[lenA-i-1] - '0')}if i < lenB {carry += int(b[lenB-i-1] - '0')}ans = strconv.Itoa(carry%2) + anscarry /= 2}if carry > 0 {ans = "1" + ans}return ans
}

c++：

class Solution {
public:string addBinary(string a, string b) {string ans;reverse(a.begin(), a.end());reverse(b.begin(), b.end());int n = max(a.size(), b.size()), carry = 0;for (size_t i = 0; i < n; ++i) {carry += i < a.size() ? (a.at(i) == '1') : 0;carry += i < b.size() ? (b.at(i) == '1') : 0;ans.push_back((carry % 2) ? '1' : '0');carry /= 2;}if (carry) {ans.push_back('1');}reverse(ans.begin(), ans.end());return ans;}
};

python：

class Solution:def addBinary(self, a: str, b: str) -> str:x, y = int(a, 2), int(b, 2)while y:answer = x ^ ycarry = (x & y) << 1x, y = answer, carryreturn bin(x)[2:]

java：

class Solution {public String addBinary(String a, String b) {StringBuilder ans = new StringBuilder();int n = Math.max(a.length(), b.length()), carry = 0;for (int i = 0; i < n; ++i) {carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;ans.append((char) (carry % 2 + '0'));carry /= 2;}if (carry > 0) {ans.append('1');}ans.reverse();return ans.toString();}
}