Add Binary

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

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

题目翻译: 对于给定的两个二进制数字所表达的字符串，我们求其相加所得到的结果， 根据上例便可得到答案.

题目分析: 我认为这道题所要注意的地方涵盖以下几个方面:

  1. 对字符串的操作.
  2. 对于加法，我们应该建立一个进位单位，保存进位数值.
  3. 我们还要考虑两个字符串如果不同长度会怎样.
  4. int 类型和char类型的相互转换.

时间复杂度:其实这就是针对两个字符串加起来跑一遍，O(n) n代表长的那串字符串长度.

代码如下:

  1. class Solution {
  2. public:
  3.     string addBinary(string a, string b) {
  4.         int len1 = a.size();
  5.         int len2 = b.size();
  6.         if(len1 == 0)
  7.             return b;
  8.         if(len2 == 0)
  9.             return a;
  11.         string ret;
  12.         int carry = 0;
  13.         int index1 = len1-1;
  14.         int index2 = len2-1;
  16.         while(index1 >=0 && index2 >= 0)
  17.         {
  18.             int num = (a[index1]-'0')+(b[index2]-'0')+carry;
  19.             carry = num/2;
  20.             num = num%2;
  21.             index1--;
  22.             index2--;
  23.             ret.insert(ret.begin(),num+'0');
  24.         }
  26.         if(index1 < 0&& index2 < 0)
  27.         {
  28.             if(carry == 1)
  29.             {
  30.                 ret.insert(ret.begin(),carry+'0');
  31.                 return ret;
  32.             }
  33.         }
  35.         while(index1 >= 0)
  36.         {
  37.             int num = (a[index1]-'0')+carry;
  38.             carry = num/2;
  39.             num = num%2;
  40.             index1--;
  41.             ret.insert(ret.begin(),num+'0');
  42.         }
  43.         while(index2 >= 0)
  44.         {
  45.             int num = (b[index2]-'0')+carry;
  46.             carry = num/2;
  47.             num = num%2;
  48.             index2--;
  49.             ret.insert(ret.begin(),num+'0');
  50.         }
  51.         if(carry == 1)
  52.             ret.insert(ret.begin(),carry+'0');
  53.         return ret;
  54.     }
  55. };