【LeetCode - 每日一题】1073. 负二进制数相加 （2023.05.18）

1073. 负二进制数相加

题意

• 基数为 -2 。
• 实现两个 0/1 数组串的加法。

解法

这是一道模拟题。

设 arr1[i] 和 arr2[i] 是数组 arr1 和 arr2 从低到高的第 i 位数。

首先回顾普通的二进制数的相加，从低位开始计算，在计算的同时维护用一个变量 carry 维护进位信息，因此，对于第 i 位的结果 ans[i] = arr1[i] + arr2[i] + carry。若 ans[i] = 0, 1，则更新 carry = 0，ans[i] = 0, 1；若 ans[i] = 2, 3，则更新 carry = 1，ans[i] = ans[i] - 2。

类比到基数为 -2 的二进数相加上，从低位开始计算，在计算的同时用一个变量 carry 维护进位信息，同样地，对于第 i 为的结果 ans[i] = arr1[i] + arr2[i] + carry。则此时的 carry 的范围变成了 [-1, 0]，ans[i] 的范围变成了 [-1, 0, 1, 2]。若 ans[i] = 0, 1，则更新 carry = 0，ans[i] = 0, 1；若 ans[i] = 2，则更新 carry = -1（因为相邻位的正负号是反的，所以进位一定是 -1 ），ans[i] = ans[i] - 2；若 ans[i] = -1，此时是一种特殊情况，需要单独讨论：

当 ans[i] = -1 时，需要将其进行转换。又注意到：
(-2)ⁱ⁺¹ + (-2)ⁱ = - (-2)ⁱ，所以将 ans[i] 赋为 -1 和将 ans[i] 和 ans[i+1] 都加 1 的效果是一样的，因此更新 carry = 1，ans[i] = 1。

// 官方解法
class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {vector<int> ans;int idx1 = arr1.size() - 1, idx2 = arr2.size() - 1;int carry = 0;while(idx1 >= 0 || idx2 >= 0 || carry) 	// carry 要放在 while 循环条件里{int x = carry;if(idx1 >= 0){x += arr1[idx1];}if(idx2 >= 0){x += arr2[idx2];}idx1 --;idx2 --;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;}}// 删去前置 0 while(ans.size() > 1 && ans.back() == 0){ans.pop_back();}reverse(ans.begin(), ans.end());return ans;}
};

---