【LeetCode刷题记录】简单篇-67-二进制求和

【题目描述】

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

【测试用例】

示例1：

        输入：a = "11"，b = "1"

        输出："100"

示例2：

        输入：a = "1010"，b = "1011"

        输出："10101"

【思路分析】

最开始我想的是两个字符串从后往前遍历，对应位置相加，模拟正常的二进制加法计算，有进位的将进位1保存在jinWei变量中，无进位的正常相加。但是这样的做法在代码逻辑上有点复杂，因为相加的结果要存入结果字符串res的对应位置，这个索引不好控制（涉及到相加后会比原来的最长字符串的长度多一位的情况）。

所以为了便于理解，最开始就直接将两个字符串逆置，然后从前往后遍历，对应位相加，同时存储到res中的位置也相同，这样就可以用一个遍历i来表示所有的位置，最后再将res逆置回来。

【参考代码】

C实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//easy-67-二进制求和
void reverse(char* s);
char* addBinary(char* a, char* b);

int main(){
	char* a = "11";
	char* b = "1";
	char* res = addBinary(a, b);
	int i;
	for(i=0;i<strlen(res);++i){
		printf("%c",res[i]);	
	}
	return 0;
} 

void reverse(char* s){
	int i;
	int len = strlen(s);
	for(i=0;i<len/2;++i){
		char tmp = s[i];
		s[i] = s[len-i-1];
		s[len-i-1] = tmp;
	}
} 

char* addBinary(char* a, char* b) {
	reverse(a);
	reverse(b);
	int i;
	int jinWei=0;
    int len1 = strlen(a);
    int len2 = strlen(b);
    int len = len1>len2 ? len1 : len2;
    char* res = (char*)malloc(sizeof(char)*(len+2));
    for(i=0;i<len;++i){
    	if(i<len1 && i<len2){
    		int tmp = (a[i]-'0') + (b[i]-'0') + jinWei;
    		res[i] = (tmp % 2) + '0';
    		jinWei = tmp / 2;
		}else if(i<len1 && i>=len2){
			int tmp = (a[i]-'0') + jinWei;
    		res[i] = (tmp % 2) + '0';
    		jinWei = tmp / 2;
		}else if(i>=len1 && i<len2){
			int tmp = (b[i]-'0') + jinWei;
    		res[i] = (tmp % 2) + '0';
    		jinWei = tmp / 2;
		}
	}
    if(jinWei){
        res[len++]='1';
    }
    res[len] = '\0';
	reverse(res);
    return res;
}

C++实现

#include <iostream>
#include <string>
using namespace std;

//easy-67-二进制求和
class Solution {
public:
	string reverse(string s);
    string addBinary(string a, string b);
};

string Solution::reverse(string s){
	int i;
	int len = s.size();
	for(i=0;i<len/2;i++){
		char tmp = s[i];
		s[i] = s[len-i-1];
		s[len-i-1] = tmp;
	}
	return s;
}

string Solution::addBinary(string a, string b){
	a = reverse(a);
	b = reverse(b);
	int i;
	int len1 = a.size();
	int len2 = b.size();
	int len = len1>len2 ? len1 : len2;
	int jinWei = 0;
	string res;
	for(i=0;i<len;i++){
		if(i<len1 && i<len2){
			int tmp = (a[i]-'0') + (b[i]-'0') + jinWei;
			res += (tmp % 2) + '0';
			jinWei = tmp / 2;
		}else if(i<len1 && i>=len2){
			int tmp = (a[i]-'0') + jinWei;
			res += (tmp % 2) + '0';
			jinWei = tmp / 2;
		}else if(i>=len1 && i<len2){
			int tmp = (b[i]-'0') + jinWei;
			res += (tmp % 2) + '0';
			jinWei = tmp / 2;
		}
	}
	if(jinWei){
		res += '1';
	}
	res = reverse(res);
	return res;
}

int main(){
	string a = "0";
	string b = "0";
	Solution sol;
	string res = sol.addBinary(a, b);
	int i;
	for(i=0;i<res.size();++i){
		cout<<res[i];
	}
	return 0;
}