凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 67. Add Binary

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


题目

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"
b = "1"
Return "100".

题意

给出两个表示二进制数值的字符串,将其相加,返回一个二进制字符串表示他们的和。

解法

class Solution {
public:
    string addBinary(string a, string b) {
        bool carry = false;
        int a_size = a.size(), b_size = b.size();
        string ret;
        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;
    }
};