Leetcode: Add Binary

小鱼儿 2022-08-07 05:37 29阅读 0赞

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

For example,  
a = “11”  
b = “1”  
Return “100”.

分析：  
思路一：刚开始我想的是将a和b转成数字，然后相加，结果在转成二进制字符。这种方法在a和b长度比较小的时候可行，a和b太长的时候，转成数字int或者long类型就装不下了。  
思路二：后来就直接吧a和b弄成一样长度的字符，短的在前面加0，然后从后到前进行遍历，依次计算结果。

思路一C++示例：  
（这个方法在a或者b长度太长的时候不可取，在Leetcode上面提交直接报错了！）

class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            int x = stoi(a, nullptr, 2);
            int y = stoi(b, nullptr, 2);
            int sum = x + y;
            //十进制转二进制
            string result;//结果字符串
            //临时存储计算的二进制结果，计算出来的余数要reverse下
            vector<int> binary;
            int quotient = sum / 2;
            int remainder = sum % 2;
            while (quotient != 0)
            {
                binary.push_back(remainder);
                remainder = quotient % 2;
                quotient /= 2;
            }
            binary.push_back(remainder);
    
            vector<int>::size_type size = binary.size();
            //逆序遍历binary将每个int转为char装入result中
            for (size_t i = size; i != 0; i--)
            {
                result.push_back(binary[i - 1] + '0');
            }
            return result;
        }
    };

思路二C++示例：

class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            int lengthA = a.length();
            int lengthB = b.length();
            int difference = abs(lengthA - lengthB);
            //用于填补的元素都初始化为0
            string supplement(difference, '0');
            string result;
            //下面将a和b的长度填充一样，在短的前面补0
            if (lengthA > lengthB)
            {
                b = supplement + b;
                result.resize(lengthA, '0');
            }
            else
            {
                a = supplement + a;
                result.resize(lengthB, '0');
            }
    
            int length = result.length();
            int current;//记录当前位置两个数字和的最终结果
            int flag = 0;//记录下一位是否要进1
            for (int i = length - 1; i >= 0; i--)
            {
                //这里的异或运算符很好地计算出了两个数字相加以后这个位置上的结果
                current = (a[i] - '0') ^ (b[i] - '0') ^ flag;
                //计算两个数相加以后要不要进1
                if ((a[i] - '0') + (b[i] - '0') + flag > 1)
                {
                    flag = 1;
                }
                else
                {
                    flag = 0;
                }
                //将当前结果记录到result中
                result[i] = current + '0';
            }
            //如果计算到做高位需要进1，则在结果的最前面加1
            if (flag)
            {
                result = '1' + result;
            }
            return result;
        }
    };