二进制求和
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
初步分析
这个题和上一个题加一有着异曲同工之妙，加一是逢十进一，二进制得话则是逢二进一。只不过这个比十进制稍微要难一点。
比如
十进制999进行加一：
- 最后一位9+1=10。置0进1
- 倒数第二位9+1=10。置0进1
- 倒数最三位9+1=10。置0进1
这个题每次都是加1，也就是临界值最大为10，逢10进1即可。
二进制11+11
- 最后一位1+1。置0进1
- 倒数第二位1+1+1(进1)=3。大于2。
看，很明显这个要比十进制加一要难，首先要进位，还要考虑留下得数字是几。其实也很简单。和为3，对3取余，那么余数自然就是留下来的数。
所以按照上边那个题加一来做的解法是这样的
class Solution { public static String addBinary(String a, String b) { int maxLength = a.length()>b.length()?a.length():b.length(); int aLen = a.length(); int bLen = b.length(); Integer[] result = new Integer[maxLength]; while (aLen > 0 && bLen > 0) { result[maxLength - 1] = result[maxLength - 1] == null ? 0 : result[maxLength - 1]; Integer count = (a.charAt(aLen-1)=='0'?0:1) + (b.charAt(bLen - 1)=='0'?0:1) + result[maxLength - 1]; if (count >= 2 && !(aLen == 1 && bLen == 1)) { result[maxLength - 1] = count % 2; result[maxLength - 2] = 1; } else if(count >= 2 && (aLen == 1 && bLen == 1)){ Integer[] newResult = new Integer[result.length + 1]; newResult[0] = 1; newResult[1] = count % 2; for (int i = 2; i < newResult.length; i++) { newResult[i] = result[i - 1]; } result = newResult; } else { result[maxLength - 1] = count; } maxLength--; aLen--; bLen--; } while (aLen > 0) { result[maxLength - 1] = result[maxLength - 1] == null ? 0 : result[maxLength - 1]; Integer count = (a.charAt(maxLength-1)=='0'?0:1) + result[maxLength - 1]; if (count >= 2 && maxLength != 1) { result[maxLength - 1] = count % 2; result[maxLength - 2] = 1; } else if(count >= 2 && aLen == 1){ Integer[] newResult = new Integer[result.length + 1]; newResult[0] = 1; newResult[1] = count % 2; for (int i = 2; i < newResult.length; i++) { newResult[i] = result[i - 1]; } result = newResult; } else { result[maxLength - 1] = count; } maxLength--; aLen -- ; } while (bLen > 0) { result[maxLength - 1] = result[maxLength - 1] == null ? 0 : result[maxLength - 1]; Integer count = (b.charAt(maxLength - 1)=='0'?0:1) + result[maxLength - 1]; if (count >= 2 && bLen != 1) { result[maxLength - 1] = count % 2; result[maxLength - 2] = 1; } else if(count >= 2 && bLen == 1){ Integer[] newResult = new Integer[result.length + 1]; newResult[0] = 1; newResult[1] = count % 2; for (int i = 2; i < newResult.length; i++) { newResult[i] = result[i - 1]; } result = newResult; } else { result[maxLength - 1] = count; } bLen--; maxLength--; } StringBuffer data = new StringBuffer(); for (int i = 0; i < result.length; i++) { data.append(result[i]); } return data.toString(); } }
由最后把数组拼接成字符串可以看出，我是被上一个题影响了。因为两个题着实太像了。还有一点不同的是，上个题是在数组里，而这个题是两个字符串，最后的结果也是字符串，所以很明显上述的解法必不是一个好的解法。
继续分析
上个解法被上一个题深深影响，所以也是借用了数组，那么不用数组怎么解呢？
我们可以直接把二进制转换成十进制进行计算，然后转回二进制字符串即可。也就是我们上个题不能干的事，这个题是可以干的。
public static String addBinary(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a,2)+Integer.parseInt(b,2));
}简简单单，直接解决。但是如果字符串太长的话，就会导致解析失败，所以这虽然看着可行，但并不是一个健壮良好的程序，还需要继续改进。
不能直接转为整数计算，那么还是得回到我们最初的想法上去，逢二进一，我们摒弃之前的数组的方式再来优化一下整个算法。
答案
class Solution {
public static String addBinary(String a, String b) {
int aLen = a.length();
int bLen = b.length();
int count = 0;
StringBuffer data = new StringBuffer();
while (aLen > 0 && bLen > 0) {
int newCount = a.charAt(aLen - 1) - '0' + b.charAt(bLen - 1) - '0' + count;
data.append((char) (newCount % 2 + '0'));
count = newCount/2;
aLen--;
bLen--;
}
while (aLen > 0) {
int newCount = a.charAt(aLen - 1) - '0' + count;
data.append((char) (newCount % 2 + '0'));
count = newCount/2;
aLen--;
}
while (bLen > 0) {
int newCount = b.charAt(bLen - 1) - '0' + count;
data.append((char) (newCount % 2 + '0'));
count = newCount/2;
bLen--;
}
if (count > 0) {
data.append(count);
}
return data.reverse().toString();
}
}复杂度
- 时间复杂度：O(n)，会把a和b遍历完，也就是会遍历最长字符串的个数。
- 空间复杂度：O(1),我们只需要几个变量记录我们的数据，每次要进位的数字，以及最后返回的字符。
总结
刚才我们提到，在java中字符串太长，会导致Integer.parseInt()解析失败，那么怎么回事呢？
- 字符串超过 33 位，不能转化为 Integer
- 字符串超过 65 位，不能转化为 Long
- 字符串超过 500000001 位，不能转化为 BigIntege
所以以后使用的时候，也一定要注意哦。
再一个我们很容易收到之前的一些影响，这就是固化思维。所以解决问题还是要深度思考以下的。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
