X

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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)