C++ 解法, 执行用时: 2ms, 内存消耗: 512KB, 提交时间: 2021-11-13

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        string res;
        int m = max(A.length(), B.length()), carry = 0;
        reverse(A.begin(), A.end());
        reverse(B.begin(), B.end());
        //遍历最长序列一次，结果长度最多只会增加一位
        for(int i = 0; i < m; i++){//this carry = (ai + bi + last carry)/2
            carry += i < A.size() ? (A.at(i) == '1') : 0;
            carry += i < B.size() ? (B.at(i) == '1') : 0;
            res.push_back((carry % 2) ? '1' : '0'); //这一位的值，注意此时添加的顺序是反的
            carry = carry/2; //new carry
        }
        if(carry) res.push_back('1');
        reverse(res.begin(), res.end());//反过来才是答案
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-04-05

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        int lenA = A.size();
        int lenB = B.size();
        int maxLen = (lenA >= lenB) ? lenA : lenB;
        string result(maxLen + 1, ' ');
        int carry = 0;
        int pos = maxLen;
        
        
        for (int i = lenA - 1, j = lenB - 1;
             i >= 0 || j >= 0;) {
            int v1 = (i >= 0) ? (A[i] - '0') : 0;
            int v2 = (j >= 0) ? (B[j] - '0') : 0;
            int sum = v1 + v2 + carry;
            carry = sum / 2;
            result[pos--] = '0' + (sum % 2);
            if (i >= 0) {
                --i;
            }
            
            if (j >= 0) {
                --j;
            }
        }
        
        if (carry != 0) {
            result[pos--] = '0' + carry;
        }
        
        return result.substr(pos + 1);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-02-06

class Solution {
public:
    /*
    方法一：模拟
    
    思路和算法
    我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
    
    1. 具体的，我们可以取 n = max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。
    2. 我们使用一个变量 carry 表示上一个位置的进位，初始值为 0。
       记当前位置对其的两个位为 a_i​ 和 b_i，则每一位的答案为 (carry + a_i + b_i) % 2，
       下一位的进位为 (carry + a_i + b_i) / 2
    3. 重复上述步骤，直到数字 a 和 b 的每一位计算完毕。
    4. 最后如果 carry 的最高位不为 0，则将最高位添加到计算结果的末尾。
    
    注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。
    当然你也可以直接把 a 和 b 中短的那一个补 0 直到和长的那个一样长，然后从高位向低位遍历，
    对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。
    
    复杂度分析
    时间复杂度：O(n)，这里的时间复杂度来源于顺序遍历 a 和 b。假设 n = max{∣a∣,∣b∣}。
    空间复杂度：O(1)，除去答案所占用的空间，这里使用了常数个临时变量。
    */
    string binaryAdd(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;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-07-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        string res;
        int n = A.size();
        int m = B.size();
        int count = 0;
        int i = n - 1, j = m - 1;
        while(i >= 0 && j >= 0) {
            int tmp = A[i] - '0' + B[j]- '0' + count;
            res += '0' + tmp % 2;
            count = tmp / 2;
            i--;
            j--;
        }
        while(i >= 0) {
            int tmp = A[i] - '0' + count;
            res += '0' + tmp % 2;
            count = tmp / 2;
            i--;
        }
    
        while(j >= 0) {
            int tmp = B[j] - '0' + count;
            res += '0' + tmp % 2;
            count = tmp / 2;
            j--;
        }
        if(count) {
            res += '1';
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2021-12-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        int Alen=A.length(),Blen=B.length();
        if(Alen==0||Blen==0) return A+B;
        if(A[0]=='0') return B;
        if(B[0]=='0') return A;
        if(Alen<Blen) {
            swap(A,B);
            swap(Alen,Blen);
        }
        int k=0,tmp,i=Blen-1,j=Alen-1;
        while((A[j]=='0'||B[i]=='0')&&i>=0) {
            A[j]=(A[j]=='0'&&B[i]=='0')?'0':'1';
            --i,--j;
        }
        if(i<0) return A;
        for(;i>=0;--i,--j) {
            tmp=A[j]-'0'+B[i]-'0'+k;
            A[j]=(tmp)%2+'0';
            k=tmp/2;
        }
//        if(i==j&&k) return "1"+A;
        while(j>=0&&k) {
            tmp=A[j]-'0'+k;
            A[j]=tmp%2+'0';
            k=tmp/2;
            --j;
        }
        if(j<0&&k) return "1"+A;
        return A;
    }
};