描述

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

For example,

a = "11"

b = "1"

Return "100".

分析

这道题没做出来。。

逛了评论区才写出来的，代码写得很简洁

https://discuss.leetcode.com/topic/8981/short-code-by-c

我之前的思路是对两个string的每一位都做处理，比如，如果两个都是1，carry就为1，tmp（当前位的值）就为0；如果只有一个1，carry就为0，tmp为1；如果全为0，carry和tmp就都为0.

然后发现来自低位的进位要先初始化一次，于是就对最低位单独处理，得到carry的初始值。这样写的话太麻烦了，于是转而求助讨论区。

我参照的代码只用一个变量carry来同时处理进位和当前位。由于string只包含0和1，因此每次都将两个string的当前位变为整型加到carry变量。

比较有趣的地方是while循环的第三个条件，这个条件只有在两个string都遍历结束时才会用到（也就是判断最高位是否有进位），如果有进位，那么carry的值是为1，条件成立，直接把这个1加到最后。

由于整个操作都是直接往待返回的string的末尾加，因此要调用reverse函数逆置。

代码如下：

class Solution {

public:

    string addBinary(string a, string b) {

        string ret;

        int i = a.size() - 1;

        int j = b.size() - 1;

        int carry = 0;

        while(i >= 0 || j >= 0

                || carry > 0){  //仅用来处理最高位有进位的情况

            if(i >= 0){

                carry += a[i] - '0';

                --i;

            }

            if(j >= 0){

                carry += b[j] - '0';

                --j;

            }

            ret += (carry % 2) + '0';

            carry /= 2;

        }

        reverse(ret.begin(),ret.end());

        return ret;

    }

};

巴特西

leetcode解题报告（26）：Add Binary

描述

分析

最新文章

热门文章