LeetCode67. Add Binary

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

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

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

Example 2:

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

思路

  • 计算出两个字符串的长度,从每个字符串最后一个元素开始,低位对齐,向前遍历。
  • 开一个字符串ret来保存处理完每一位后的结果。
  • 如果该位有字符,就将字符转化为数字,方法是减字符’0’;如果没有数字就直接取int的0.
  • 每一位的结果,等于,两个字符之和+是否进位的标志,记为sum。再将sum转为2进制,用位运算向右移一位,得到的是进位标志;对sum取模,得到的是该位的结果。最后将该位的结果连接到原来的结果ret前面。
  • 返回的时候,判断进位标志是否为1,如果是的话,在ret前面连接上一个字符串“1”即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string addBinary(string a, string b) { 
string ret="";
int max = a.size()-1, min = b.size()-1;
int numa, numb,sum,carry=0;
while (max>=0 || min>=0 )//1.
{
numa = (max >= 0) ? a[max--] - '0' : 0;//2.
numb = (min >= 0) ? b[min--] - '0': 0;
sum = numa + numb+ carry ;
carry = sum >> 1;//3.
ret = to_string(sum % 2)+ret;//4.
}

return carry==1?"1"+ret:ret;//5.
}

细节

  1. 不能写成while(max||min)因为索引为0的时候也要算。
  2. 将字符转为数字:-‘0’,是单引号。长度不一样不用管,如果数组越界了,就取(int)0。
  3. 进位标志:求商,如果不为1,就不用进位
  4. 不是ret+=,那样写的话,ret在前面了,因为是低位对齐,所以要从后往前,ret应该链接在后面。int转string:to_string(int)
  5. 最后不能直接返ret,如果还要进位,前面补1,连接到字符串前面。

总结

  1. 考察字符串链接,动态规划。
  2. 将字符转为int的方法就是-‘0’。
  3. 二进制运算,进位的用法,定义一个标记代表是否需要进位处理。求商表示进位,求余表示剩下的结果。
Thanks for Support.