好长时间没更了,最近想练一下算法,这是个开端:
描述
给定两个二进制字符串,返回他们的和(用二进制表示)。
样例
a =11
b =1
返回100
我的理解:
对于这道题,我想到的应该是我这类平常人普遍想到的就是按照逻辑一步一步走。下面简单说一下我的思路:
- 拿到两个字符串相加,我的第一反应就是将字符串分离为单个字符来进行运算
- 因为要考虑进位问题,于是我就定义了另外一个数
temp
,产生进位是时为1,不产生时为0,每个单个字符的运算都是a + b + temp
,然后为 temp 重新赋值。
3.考虑运算的结果,考虑结果为result
放入不同的值
if (a == null && b == null) return null;
if (a.equals("0") && b.equals("0")) return "0";
String targetA, targetB;
//运算由小位开始,所以翻转一下字符串
if (a.length() >= b.length()) {
targetA = new StringBuffer(a).reverse().toString();
targetB = new StringBuffer(b).reverse().toString();
} else {
targetA = new StringBuffer(b).reverse().toString();
targetB = new StringBuffer(a).reverse().toString();
}
int currentA, currentB, temp = 0;
String result = "";
for (int i = 0; i < targetA.length(); i++){
currentA = Integer.parseInt(targetA.split("")[i]);
if (targetB.length() > i){
currentB = Integer.parseInt(targetB.split("")[i]);
}else {
//这是只有targetA中有数据,而targetB已经全部相加完毕
if (temp == 0){
result += targetA.split("")[i];
temp = 0;
} else {
int index = Integer.parseInt(targetA.split("")[i]);
//最后一个temp来决定结果,这里是for循环最后执行的代码
if (index + temp == 1){
result += "1";
temp = 0;
}else if (index + temp == 2){
result += "0";
temp = 1;
}
if (i + 1 == targetA.length() && temp == 1){
result += "1";
temp = 0;
}
}
continue;
}
//根据temp来决定result的下一个
if (currentA + currentB == 0){
if (temp == 0){
result += "0";
}else{
result += "1";
}
temp = 0;
}else if (currentA + currentB == 1){
if (temp == 0){
result += "1";
temp = 0;
}else{
result += "0";
temp = 1;
}
} else if (currentA + currentB == 2){
if (temp == 0){
result += "0";
temp = 1;
}else{
result += "1";
temp = 0;
}
}
}
return new StringBuffer(result).reverse().toString();
}
但是不知道为什么Linkcode报了这个错
Exception in thread "main" java.lang.NumberFormatException:
For input string: "" at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
at java.lang.Integer.parseInt(Integer.java:504)
at java.lang.Integer.parseInt(Integer.java:527)
at Solution.addBinary(Solution.java:22)
at Main.main(Main.java:26)
我并没有能解决,但是思路就是这个思路。下面是在网上看到的更好的实现方式:
public String addBinary(String a, String b) {
String result = "";
int aLen = a.length() - 1;
int bLen = b.length() - 1;
int sum = 0;
while (aLen >= 0 || bLen >= 0) {
if (aLen >= 0) {
sum += Integer.parseInt(a.substring(aLen, aLen + 1));
aLen--;
}
if (bLen >= 0) {
sum += Integer.parseInt(b.substring(bLen, bLen + 1));
bLen--;
}
if (sum == 3) {
result = "1" + result;
sum = 1;
} else if (sum == 2) {
result = "0" + result;
sum = 1;
} else if (sum == 0 || sum == 1) {
result = sum + "" + result;
sum = 0;
}
}
if (sum == 1){
result = "1" + result;
}
return result;
}