LeetCode 67 Add Binary | 二进制数累加

题目来源：LeetCode:67. Add Binary

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

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

思路

  • 类似于大数大数加法操作，逐位进行操作。
  • 每一位字符-‘0’得到的数字，累加后与2比较，来确定进位与否。
  • 最高位的可能位1，或不存在，且只有计算结束时才能确定存在与否，动态分配内存方面应特殊对待。

    C语言实现，一方面逐位操作要考虑周全，另一方面C语言具有的字符串处理弱势，需要较多冗余处理操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
char* addBinary(char* a, char* b) {
    int len_a=0, len_b=0, len_res=0;
    char* p = a;
    while(*p != '\0'){
        len_a++;        
        p++;
    }
    p = b;
    while(*p != '\0'){
        len_b++;        
        p++;
    }

    len_res = len_a > len_b ? (len_a+2) : (len_b+2);
    char* res = (char *)malloc(len_res);
    res[--len_res] = '\0';
    int bit_carry = 0; //进位
    int bit_res = 0;
    while(--len_res){
        bit_res = bit_carry;
        if(len_a>0)
            bit_res += a[--len_a] - '0';

        if(len_b>0)
            bit_res += b[--len_b] - '0';

        if(bit_res>=2){
            bit_carry = 1;
            bit_res -= 2;
        }
        else
            bit_carry = 0;

        res[len_res] = bit_res + '0';
    }

    //len_res == 0
    if(bit_carry){
        res[len_res] = '1';
    }
    else{
        res[len_res] = '0';
        res++;  //This is a tricky way and bug may be triggered in main when call free(res) to release address.
    }
    return res;
}
void main(){
    char *a = "1001";
    char *b = "11";
    printf("a is: %s\n", a);
    printf("b is: %s\n", b);
    char *res = addBinary(a, b);
    printf("Result is: %s\n", res);
}

补充: 在C语言中对字符串的处理功能是比较弱和相对笨拙的，但思路与语言无关。

对于内存空间开辟多少字节的判断上，最初是无法判断结果是n还是n+1的。
上述代码中采用了一种Tricky的方式：当首位为0时，res++，再返回res。这样当主函数调用free释放内存时，这是不安全的。
优化方式: 开始时仅开辟n个字节，最后如果首位为1的情况，重新开辟n+1个字节，strcpy内存空间，释放原来n个字节, 返回新的n+1个字节的地址。
虽然优化方式饶了远，但可以完美解决内存分配的问题。若采用Java、Python、C++等高级语言就不会面临这种手动分配内存的苦恼了。

结果

294 / 294 test cases passed.

Status: Accepted

Runtime: 0 ms

Submitted: 0 minutes ago