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

文章目录

67. 二进制求和：

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

样例 1：

输入:

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

    "100"

样例 2：

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

提示：

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

分析：

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

题解：

rust：

implSolution{pubfnadd_binary(a:String, b:String)->String{letmut ans =String::new();letmut 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：

funcaddBinary(a string, b string)string{
    ans :=""
    carry :=0
    lenA, lenB :=len(a),len(b)
    n := lenA
    if 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)+ ans
        carry /=2}if carry >0{
        ans ="1"+ ans
    }return ans
}

c++：

classSolution{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：

classSolution:defaddBinary(self, a:str, b:str)->str:
        x, y =int(a,2),int(b,2)while y:
            answer = x ^ y
            carry =(x & y)<<1
            x, y = answer, carry
        returnbin(x)[2:]

java：

classSolution{publicStringaddBinary(String a,String b){StringBuilder ans =newStringBuilder();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();}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~