博文中会简要介绍Leetcode P0067题目分析及解题思路。
“Add Binary”是一道比较简单的题目。
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
这道题的思路很直接明了，就是从右往左扫一遍，注意进位即可。
以下是Java的题解代码实现。
class Solution {
public String addBinary(String a, String b) {
int len = Math.max(a.length(), b.length());
char[] chars = new char[len+1];
int ptra = a.length()-1, ptrb = b.length()-1, increment = 0, count = len;
while (ptra >= 0 || ptrb >= 0) {
int digitA = (ptra >= 0)? a.charAt(ptra)-'0': 0;
int digitB = (ptrb >= 0)? b.charAt(ptrb)-'0': 0;
int res = (digitA+digitB+increment)%2;
increment = (digitA+digitB+increment)/2;
chars[count] = (char) (res+'0');
--count;
--ptra;
--ptrb;
}
if (increment == 1) {
chars[0] = '1';
return String.valueOf(chars);
}
return String.valueOf(chars).substring(1);
}
}
以下是C++的题解代码实现。
class Solution {
public:
string addBinary(string a, string b) {
int len = max(a.length(), b.length());
string ret(len+1, '0');
int ptra = a.length()-1, ptrb = b.length()-1, increment = 0, count = len;
while (ptra >= 0 || ptrb >= 0) {
int digitA = (ptra >= 0)? a[ptra]-'0': 0;
int digitB = (ptrb >= 0)? b[ptrb]-'0': 0;
int res = (digitA+digitB+increment)%2;
increment = (digitA+digitB+increment)/2;
ret[count] = res+'0';
--count;
--ptra;
--ptrb;
}
if (increment == 1) {
ret[0] = '1';
return ret;
}
return ret.substr(1);
}
};