题目大意：
负二进制数相加
给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 的数字也同样不含前导零：以 arr 为例，这意味着要么 arr == [0]，要么 arr[0] == 1。
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
示例：
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
提示：
1 <= arr1.length <= 1000
1 <= arr2.length <= 1000
arr1 和 arr2 都不含前导零
arr1[i] 为 0 或 1
arr2[i] 为 0 或 1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1073
解题思路分析：
这是一道2进制的题目。很少接触这类问题，由于在此方面并不精通，因此只能概述一下解题过程。如有错误望路过大神指教。
本题给了2个2进制数（用数组表示），需要求和。对于普通的2进制数，每一位上的1都相当于十进制中的2的n次方（n为当前位）。例如：
1 // 2的0次方 相当于10进制的1 10 // 2的1次方 相当于10进制的2 100 // 2的2次方 相当于10进制的4 111 // 111 = 1 + 10 + 100 = 1 + 2 + 4 = 7;
在二进制加法中，0+1或者1+0都为1，0+0为0，1+1为10，即当前位为0，进位(carry)1。
不过本题有些特殊，这个2进制数的每一位代表的并不是2的n次方，而是-2的n次方，这时在进位(carry)的处理上就发生了变化，因为相邻位的符号相反，所以进位应该变为-1。在两数相加时，二进制的数字只会存在0和1，但carry会出现1，0，-1三种情况，因此相加之后的和会有：-1，0，1，2，3几种情况。对于这几种情况的进位处理如下：
sum = 0 // 当位0，进位0 sum = 1 // 当位1，进位0 sum = 2 // 当位0，进位-1 sum = 3 // 当位1，进位-1 sum = -1 // 当位1，进位1
明白了如何进位，这道题就迎刃而解了。
完整代码：
public int[] addNegabinary(int[] arr1, int[] arr2) {
// 定义返回结果。考虑到进位，数组最大长度为arr1与arr2最大长度加2
int[] res = new int[Math.max(arr1.length, arr2.length)+2];
int index1 = arr1.length-1, // 数组1起始index（最低位）
index2 = arr2.length-1, // 数组2起始index（最低位）
carry=0, // 进位
resIndex = res.length-1; // 返回结果起始index（最低位）
// 当数组1未达到最高位，或数组2未达到最高位，或存在进位的情况下保持循环
while(index1>=0 || index2>=0 || carry !=0){
// 当前位求和。
int sum = (index1>=0 ?arr1[index1--] : 0)
+ (index2>= 0? arr2[index2--] : 0) + carry;
if(sum==-1){ // 当前位和为-1时，当位为1，进位为1。
res[resIndex--]=1;
carry=1;
}else{ // 当前位和大于等于0时，当位为与2的余数，进位为与2的商。
res[resIndex--]=sum%2;
carry = sum>=2 ? -1 : 0;
}
}
if(res[0]==0){ // 如果返回数组以0开头，需删除高位0
int zeroCount=0;
for(int n : res){
if(n==1) break;
zeroCount++;
}
// 如果数组全部为0，返回数组[0]。arr1=[0],arr2=[0]的情况
if(res.length==zeroCount){
return new int[]{0};
}
// 截取开头的0
res = Arrays.copyOfRange(res, zeroCount, res.length);
}
return res;
} 本解法执行时间1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Adding Two Negabinary Numbers.
Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Adding Two Negabinary Numbers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1073-adding-two-negabinary-numbers-解题思路分析/
View Comments (0)