918
[LeetCode]67.Add Binary
【題目】
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
【題意】
給定兩個二進製字符串，返回它們的和（也是一個二進製字符串）。
【分析】
類似大數加法
【代碼】
/*********************************
* 日期：2014-02-05
* 作者：SJF0115
* 題號: 67.Add Binary
* 網址：https://oj.leetcode.com/problems/add-binary/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
class Solution {
public:
string addBinary(string a, string b) {
int lenA = a.length();
int lenB = b.length();
if(lenA == 0){
return b;
}
else if(lenB == 0){
return a;
}
int max = lenA > lenB ? (lenA + 2) : (lenB + 2);
char* result = new char[max];
int index = 0;
int i = lenA-1,j = lenB-1;
int numA,numB,c = 0,sum = 0;
//加法
while(i >= 0 || j >= 0){
numA = i >= 0 ? (a[i] - '0') : 0;
numB = j >= 0 ? (b[j] - '0') : 0;
sum = numA + numB + c;
c = sum / 2;
result[index++] = sum % 2 + '0';
i--;
j--;
}
//最後一個進位
if(c > 0){
result[index++] = c + '0';
}
result[index] = '\0';
//反轉
for(i = 0,j = index - 1;i < j;i++,j--){
char temp = result[i];
result[i] = result[j];
result[j] = temp;
}
return string(result);
}
};
int main() {
Solution solution;
string a = "1010";
string b = "1011";
string str = solution.addBinary(a,b);
cout<<str<<endl;
return 0;
}
【代碼2】
class Solution {
public:
string addBinary(string a, string b) {
int lenA = a.length();
int lenB = b.length();
if(lenA == 0){
return b;
}
else if(lenB == 0){
return a;
}
string result;
int index = 0;
int i = lenA-1,j = lenB-1;
int numA,numB,c = 0,sum = 0;
//加法
while(i >= 0 || j >= 0 || c > 0){
numA = i >= 0 ? (a[i] - '0') : 0;
numB = j >= 0 ? (b[j] - '0') : 0;
sum = numA + numB + c;
c = sum / 2;
result.insert(result.begin(),sum % 2 + '0');
i--;
j--;
}
return result;
}
};
【代碼3】
class Solution {
public:
string addBinary(string a, string b) {
int lenA = a.length();
int lenB = b.length();
string result;
int index = 0;
int i = lenA-1,j = lenB-1;
int sum = 0;
//加法
while(i >= 0 || j >= 0){
sum += i >= 0 ? (a[i] - '0') : 0;
sum += j >= 0 ? (b[j] - '0') : 0;
result = ((sum & 1) ? "1" : "0") + result;
sum >>= 1;
i--;
j--;
}
return sum ? "1" + result : result;
}
};
最後更新：2017-04-03 12:54:57