LEETCODE 1073. Adding Two Negabinary Numbers 解题思路分析

题目大意：

负二进制数相加

给出基数为 -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-解题思路分析/