67. Add Binary

 

Given two binary strings a and b, return  their sum as a binary string.

 

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

 

Constraints:

  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

 

二进制数相加,并且保存在 string 中,要注意的是如何将 string 和 int 之间互相转换,并且每位相加时,会有进位的可能,会影响之后相加的结果。而且两个输入 string 的长度也可能会不同。这时我们需要新建一个 string,它的长度是两条输入 string 中的较大的那个,并且把较短的那个输入 string 通过在开头加字符 ‘0’ 来补的较大的那个长度。这时候逐个从两个 string 的末尾开始取出字符,然后转为数字,想加,如果大于等于2,则标记进位标志 carry,并且给新 string 加入一个字符 ‘0’。代码如下:

 

解法一:

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int na = a.size(), nb = b.size(), n = max(na, nb), carry = 0;
        if (na > nb) {
            for (int i = 0; i < na - nb; ++i) b.insert(b.begin(), '0');
        } else {
            for (int i = 0; i < nb - na; ++i) a.insert(a.begin(), '0');
        }
        for (int i = n - 1; i >= 0; --i) {
            int sum = (a[i] - '0') + (b[i] - '0') + carry;
            res = to_string(sum % 2) + res;
            carry = sum / 2;
        }
        if (carry) res.insert(res.begin(), '1');
        return res;
    }
};

 

下面这种写法又巧妙又简洁,用了两个指针分别指向a和b的末尾,然后每次取出一个字符,转为数字,若无法取出字符则按0处理,然后定义进位 carry,初始化为0,将三者加起来,对2取余即为当前位的数字,对2取商即为当前进位的值,记得最后还要判断下 carry,如果为1的话,要在结果最前面加上一个1,参见代码如下:

 

解法二:

class Solution {
public:
    string addBinary(string a, string b) {
        string res = "";
        int m = a.size() - 1, n = b.size() - 1, carry = 0;
        while (m >= 0 || n >= 0) {
            int p = m >= 0 ? a[m--] - '0' : 0;
            int q = n >= 0 ? b[n--] - '0' : 0;
            int sum = p + q + carry;
            res = to_string(sum % 2) + res;
            carry = sum / 2;
        }
        return carry == 1 ? "1" + res : res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/67

 

类似题目:

Add Binary

Multiply Strings

Plus One Linked List

Plus One

Add Two Numbers

Add to Array-Form of Integer

 

参考资料:

https://leetcode.com/problems/add-binary/

https://leetcode.com/problems/add-binary/discuss/24475/short-code-by-c

https://leetcode.com/problems/add-binary/discuss/24488/Short-AC-solution-in-Java-with-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation