二进制求和

LeetCode第67题

题目描述：

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

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

示例 1:

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

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

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

思路

用一个数组tmp将求和的结果存起来，再返回该数组。
先分别求得较长和较短的字符串，赋值给char指针。对于两字符串等长的低位部分，从后往前遍历，取出其中的字符求和并加上进位，判断进位并保存在tmp对应位置。
当较短的字符串遍历完，接着处理较长字符串的高位，同样采用加进位的方式，存到tmp对应位置。
最后，如果最高位还有进位，就申请一个比tmp长度大1的数组result，在0的位置放‘1’，并把tmp中从前往后一次复制到result中。返回result。
如果最高位没有进位，就无需申请数组了。返回tmp。
注意，在数组末尾需要添上‘\0’，作为字符串结束标志。

源代码

char * addBinary(char * a, char * b){
    //创建数组，存储和
    //ASCII码：0是48,1是49
    int lenA = strlen(a);
    int lenB = strlen(b);
    int len = (lenA > lenB) ? lenA : lenB;
    char * tmp = (char *)malloc(sizeof(char) * (len + 1));
    char * longer = (lenA >= lenB) ? a : b;
    char * shorter = (lenA >= lenB) ? b : a;
    int carray = 0;     //保存进位
    int i,j;
    for(i = strlen(longer) - 1,j = strlen(shorter) - 1;j >= 0;--i,--j){
        tmp[i] = longer[i] + shorter[j] + carray;
        if(tmp[i] == 96){        
            tmp[i] = '0';
            carray = 0;
        }
        else if(tmp[i] == 97){   
            tmp[i] = '1';
            carray = 0;
        }
        else if(tmp[i] == 98){                      
            tmp[i] = '0';
            carray = 1;
        }
        else{
            tmp[i] = '1';
            carray = 1;
        }
    }
    for(j = i; j >=0;--j){
        tmp[j] = longer[j] + carray;
        if(tmp[j] == 50){
            tmp[j] = '0';
            carray = 1;
        }
        else{
            carray = 0;
        }
    }
    if(carray == 1){                //和的最高位还有进位
        char * result = malloc(sizeof(char) * (len + 2));
        result[0] = '1';
        for(i = 1;i <= len;++i){
            result[i] = tmp[i - 1];
        }
        result[i] = '\0';
        return result;
    }

    else{
        tmp[len] = '\0';
        return tmp;        
    }

}

分析

时间复杂度和空间复杂度均为线性级别。
注意，对于以char *形式定义的字符串中的字符，不能直接赋值。