1073-负二进制数相加

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给出基数为 -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：

**输入：** arr1 = [1,1,1,1,1], arr2 = [1,0,1]
**输出：** [1,0,0,0,0]
**解释：** arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：

**输入：** arr1 = [0], arr2 = [0]
**输出：** [0]

示例 3：

**输入：** arr1 = [0], arr2 = [1]
**输出：** [1]

提示：

  • 1 <= arr1.length, arr2.length <= 1000
  • arr1[i] 和 arr2[i] 都是 0 或 1
  • arr1 和 arr2 都没有前导0

方法一：模拟

思路与算法

为了叙述方便，记 arr}_1[i] 和 arr}_2[i] 分别是 arr}_1 和 arr}_2 从低到高的第 i 个数位。在加法运算中，我们需要将它们相加。

对于普通的二进制数相加，我们可以从低位到高位进行运算，在运算的过程中维护一个变量 carry 表示进位。当运算到第 i 位时，令 x = \textit{arr}_1[i] + \textit{arr}_2[i] + \textit{carry：

  • 如果 x = 0, 1，第 i 位的结果就是 x，并且将 carry 置 0；

  • 如果 x = 2, 3，第 i 位的结果是 x - 2，需要进位，将 carry 置 1。

而本题中是「负二进制数」，第 i 位对应的是 (-2)^i，而第 i+1 位对应的是 (-2)^{i+1，是第 i 位的 -2 倍。因此，当第 i 位发生进位时，carry 应当置为 -1，而不是 1。

此时，由于 arr}_1[i] 和 arr}_2[i] 的范围都是 {0, 1\，而 carry 的范围从 {0, 1\ 变成了 {-1, 0\，因此 x 的范围从 {0, 1, 2, 3\ 变成了 {-1, 0, 1, 2\。那么：

  • 如果 x = 0, 1，第 i 位的结果就是 x，并且将 carry 置 0；

  • 如果 x = 2，第 i 位的结果是 x - 2，需要进位，将 carry 置 -1；

  • 如果 x = -1，此时第 i 位的结果应该是什么呢？可以发现，由于：

-(-2)^i = (-2)^{i+1} + (-2)^i

等式左侧表示第 i 位为 -1 的值，右侧表示第 i 和 i+1 位为 1 的值。因此，第 i 位的结果应当为 1，同时需要进位，将 carry 置 1（注意这里不是 -1）。最终，carry 的范围为 {-1, 0, 1\，会多出 x=3 的情况，但它与 x=2 的情况是一致的。

细节

在最坏的情况下，当我们计算完 arr}_1 和 arr}_2 的最高位的 x 时，得到的结果为 x=3，此时产生 -1 的进位，而 -1 在之后又会产生 1 的进位，因此，答案的长度最多为 arr}_1 和 arr}_2 中较长的长度加 2。

由于题目描述中 arr}_1[i] 和 arr}_2[i] 表示的是 arr}_1 和 arr}_2 从高到低的第 i 个数位，与题解中的叙述相反。因此，在实际的代码编写中，我们可以使用两个指针从 arr}_1 和 arr}_2 的末尾同时开始进行逆序的遍历，得到逆序的答案，去除前导零，再将答案反转即可得到顺序的最终答案。

代码

[sol1-C++]
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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        int i = arr1.size() - 1, j = arr2.size() - 1;
        int carry = 0;
        vector<int> ans;
        while (i >= 0 || j >= 0 || carry) {
            int x = carry;
            if (i >= 0) {
                x += arr1[i];
            }
            if (j >= 0) {
                x += arr2[j];
            }
            
            if (x >= 2) {
                ans.push_back(x - 2);
                carry = -1;
            }
            else if (x >= 0) {
                ans.push_back(x);
                carry = 0;
            }
            else {
                ans.push_back(1);
                carry = 1;
            }
            --i;
            --j;
        }
        while (ans.size() > 1 && ans.back() == 0) {
            ans.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
[sol1-Java]
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
28
29
30
31
32
33
34
35
36
class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1, j = arr2.length - 1;
        int carry = 0;
        List<Integer> ans = new ArrayList<Integer>();
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = carry;
            if (i >= 0) {
                x += arr1[i];
            }
            if (j >= 0) {
                x += arr2[j];
            }
            if (x >= 2) {
                ans.add(x - 2);
                carry = -1;
            } else if (x >= 0) {
                ans.add(x);
                carry = 0;
            } else {
                ans.add(1);
                carry = 1;
            }
            --i;
            --j;
        }
        while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }
        int[] arr = new int[ans.size()];
        for (i = 0, j = ans.size() - 1; j >= 0; i++, j--) {
            arr[i] = ans.get(j);
        }
        return arr;
    }
}
[sol1-C#]
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
28
29
30
31
32
33
34
35
36
public class Solution {
    public int[] AddNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.Length - 1, j = arr2.Length - 1;
        int carry = 0;
        IList<int> ans = new List<int>();
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = carry;
            if (i >= 0) {
                x += arr1[i];
            }
            if (j >= 0) {
                x += arr2[j];
            }
            if (x >= 2) {
                ans.Add(x - 2);
                carry = -1;
            } else if (x >= 0) {
                ans.Add(x);
                carry = 0;
            } else {
                ans.Add(1);
                carry = 1;
            }
            --i;
            --j;
        }
        while (ans.Count > 1 && ans[ans.Count - 1] == 0) {
            ans.RemoveAt(ans.Count - 1);
        }
        int[] arr = new int[ans.Count];
        for (i = 0, j = ans.Count - 1; j >= 0; i++, j--) {
            arr[i] = ans[j];
        }
        return arr;
    }
}
[sol1-Python3]
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
28
class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        ans = list()

        while i >= 0 or j >= 0 or carry:
            x = carry
            if i >= 0:
                x += arr1[i]
            if j >= 0:
                x += arr2[j]

            if x >= 2:
                ans.append(x - 2)
                carry = -1
            elif x >= 0:
                ans.append(x)
                carry = 0
            else:
                ans.append(1)
                carry = 1
            i -= 1
            j -= 1
        
        while len(ans) > 1 and ans[-1] == 0:
            ans.pop()
        return ans[::-1]
[sol1-C]
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void reverse(int *arr, int left, int right) {
    while (left < right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

int* addNegabinary(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){
    int i = arr1Size - 1, j = arr2Size - 1;
    int carry = 0;
    int *ans = (int *)calloc(arr1Size + arr2Size + 1, sizeof(int));
    int pos = 0;
    while (i >= 0 || j >= 0 || carry) {
        int x = carry;
        if (i >= 0) {
            x += arr1[i];
        }
        if (j >= 0) {
            x += arr2[j];
        }
        
        if (x >= 2) {
            ans[pos++] = x - 2;
            carry = -1;
        }
        else if (x >= 0) {
            ans[pos++] = x;
            carry = 0;
        }
        else {
            ans[pos++] = 1;
            carry = 1;
        }
        --i;
        --j;
    }
    while (pos > 1 && ans[pos - 1] == 0) {
        pos--;
    }
    *returnSize = pos;
    reverse(ans, 0, pos - 1);
    return ans;
}
[sol1-JavaScript]
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
28
29
30
31
32
33
34
var addNegabinary = function(arr1, arr2) {
    let i = arr1.length - 1, j = arr2.length - 1;
    let carry = 0;
    const ans = [];
    while (i >= 0 || j >= 0 || carry !== 0) {
        let x = carry;
        if (i >= 0) {
            x += arr1[i];
        }
        if (j >= 0) {
            x += arr2[j];
        }
        if (x >= 2) {
            ans.push(x - 2);
            carry = -1;
        } else if (x >= 0) {
            ans.push(x);
            carry = 0;
        } else {
            ans.push(1);
            carry = 1;
        }
        --i;
        --j;
    }
    while (ans.length > 1 && ans[ans.length - 1] === 0) {
        ans.splice(ans.length - 1, 1);
    }
    const arr = new Array(ans.length);
    for (i = 0, j = ans.length - 1; j >= 0; i++, j--) {
        arr[i] = ans[j];
    }
    return arr;
};
[sol1-Golang]
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
28
29
30
31
32
33
34
func addNegabinary(arr1 []int, arr2 []int) (ans []int) {
    i := len(arr1) - 1
    j := len(arr2) - 1
    carry := 0
    for i >= 0 || j >= 0 || carry != 0 {
        x := carry
        if i >= 0 {
            x += arr1[i]
        }
        if j >= 0 {
            x += arr2[j]
        }

        if x >= 2 {
            ans = append(ans, x-2)
            carry = -1
        } else if x >= 0 {
            ans = append(ans, x)
            carry = 0
        } else {
            ans = append(ans, 1)
            carry = 1
        }
        i--
        j--
    }
    for len(ans) > 1 && ans[len(ans)-1] == 0 {
        ans = ans[:len(ans)-1]
    }
    for i, n := 0, len(ans); i < n/2; i++ {
        ans[i], ans[n-1-i] = ans[n-1-i], ans[i]
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(m + n)，其中 m 和 n 分别是数组 arr}_1 和 arr}_2 的长度。

  • 空间复杂度：O(1) 或 O(m + n)。注意这里不包括返回值占用的空间。在最后将答案反转时，如果直接在原数组上进行反转，那么使用的空间为 O(1)；如果使用语言的 API 构造新数组进行反转（例如 Python 中的切片 [::-1] 操作），使用的空间为 O(m + n)。

 Comments
On this page
1073-负二进制数相加