凌云的博客

LeetCode 算法题 67. 二进制求和

分类：algorithm| 发布时间：2017-03-21 09:03:00

---

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

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

示例 2:

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

解法

class Solution {
public:
    string addBinary(string a, string b) {
        bool carry = false;
        int a_size = a.size(), b_size = b.size();
        string ret;
        ret.reserve(max(a_size, b_size) + 1);
        char aChar, bChar;
        for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; --i, --j) {
            aChar = i >= 0 ? a[i] : '0';
            bChar = j >= 0 ? b[j] : '0';
            if (aChar == '1' && bChar == '1') {
                if (carry) {
                    ret = "1" + ret;
                } else {
                    ret = "0" + ret;
                }

                carry = true;
            } else if (aChar == '1' || bChar == '1') {
                if (carry) {
                    ret = "0" + ret;
                    carry = true;
                } else {
                    ret = "1" + ret;
                    carry = false;
                }
            } else {
                if (carry) {
                    ret = "1" + ret;
                } else {
                    ret = "0" + ret;
                }

                carry = false;
            }
        }

        if (carry) {
            ret = "1" + ret;
        }

        return ret;
    }
};