服务器之家

服务器之家 > 正文

C++实现LeetCode(67.二进制数相加)

时间:2021-11-29 15:14     来源/作者:Grandyang

[LeetCode] 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'。代码如下:

解法一:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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,参见代码如下:

解法二:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
};

到此这篇关于C++实现LeetCode(67.二进制数相加)的文章就介绍到这了,更多相关C++实现二进制数相加内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://www.cnblogs.com/grandyang/p/4084971.html

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部