LeetCode1073-负二进制相加

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/adding-two-negabinary-numbers/

中文链接：https://leetcode-cn.com/problems/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 组成的数组。

示例：

1
2
3
输入：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

题目详解

大数加法的通用步骤如下：

  1. 从低位到高位模拟竖式加法。
  2. 相加后取模并处理进位。
  3. 去除前导零。
  4. 翻转结果。

再结合 LeetCode1017-负二进制转换 中进制转换的知识，解答本题就很容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LeetCode_01073 {

    public int[] addNegabinary(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        int carry = 0;
        for (int i = arr1.length - 1, j = arr2.length - 1; i >= 0 || j >= 0 || carry != 0; --i, --j) {
            carry += (i >= 0 ? arr1[i] : 0) + (j >= 0 ? arr2[j] : 0);
            int r = carry % -2;
            carry /= -2;
            if (r < 0) {
                r += 2;
                ++carry;
            }
            list.add(r);
        }
        // 去除前导 0
        while (list.size() > 1 && list.get(list.size() - 1) == 0) {
            list.remove(list.size() - 1);
        }
        int n = list.size();
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            res[i] = list.get(n - 1 - i);
        }
        return res;
    }
}
  • 同样，也可以运用位运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_01073 {

    public int[] addNegabinary(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        int carry = 0;
        for (int i = arr1.length - 1, j = arr2.length - 1; i >= 0 || j >= 0 || carry != 0; --i, --j) {
            carry += (i >= 0 ? arr1[i] : 0) + (j >= 0 ? arr2[j] : 0);
            list.add(carry & 1);
            carry = -(carry >> 1);
        }
        // 去除前导 0
        while (list.size() > 1 && list.get(list.size() - 1) == 0) {
            list.remove(list.size() - 1);
        }
        Collections.reverse(list);
        return list.stream().mapToInt(x -> x).toArray();
    }
}