leetcode-67.二进制求和

Points

  • 数组
  • 数学

题意

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

示例 3:(自己加的)

输入: a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101",
　　  b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

输出: "110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"(这个用例过了，大概就行了。^_^)

算法

用时：4ms

复杂度：O(n)

  1. 计算两个字符串长度，求出最短长度，确定长字符串，短字符串；
  2. 反向遍历短字符串，逐位与长字符串对应位相加，若长字符串求和后值大于 2，更新本位，且对前一位做＋1处理。（注意达到首段特殊处理）
  3. 遍历完成后，若长字符串索引未到达头，再从该索引开始反向逐位判断值是否大于 2，若是，更新本位与前一位。
  4. 长字符串处理完成后，返回该长字符串。

code

 1 class Solution {
 2 public:
 3     string addBinary(string a, string b) {
 4         int shortLen, dvalue;
 5         string ans, addStr;
 6         int thisBit, nextBit, t;
 7         if(a.length() >= b.length())
 8         {
 9             shortLen = b.length();
10             ans = a;
11             addStr = b;
12             dvalue = a.length() - b.length();
13         }
14         else
15         {
16             shortLen = a.length();
17             ans = b;
18             addStr = a;
19             dvalue = b.length() - a.length();
20         }
21         for(int i=shortLen-1; i>=0; i--)
22         {
23             t = i + dvalue;
24             ans[t] += (addStr[i]-'0');
25             thisBit = (ans[t]-'0')%2;
26             nextBit = (ans[t]-'0')/2;
27             if((ans[t] - '0') >= 2)
28             {
29                 ans[t] = (thisBit + '0');
30                 if(t == 0)
31                 {
32                     ans.insert(0, 1, (nextBit+'0'));
33                     break;
34                 }
35                 else
36                 {
37                      ans[t-1] += nextBit;          
38                 }
39             }
40         }
41         t--;
42         if(t >= 0)
43         {
44             while((ans[t] - '0') >= 2 && (t >= 0))
45             {
46                 thisBit = (ans[t]-'0')%2;
47                 nextBit = (ans[t]-'0')/2;
48                 ans[t] = (thisBit + '0');
49                 if(t == 0)
50                 {
51                     ans.insert(0, 1, (nextBit+'0'));
52                     break;
53                 }
54                 else
55                 {
56                     ans[t-1] += nextBit;
57                     t--;
58                 }
59             }
60         }
61         return ans;
62     }
63 };