2023-05-18每日一题

一、题目编号

1073. 负二进制数相加

二、题目链接

点击跳转到题目位置

三、题目描述

给出基数为 -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 组成的数组。

四、解题代码

class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {int i = 0;int n = arr1.size();int m = arr2.size();vector<int> res;int carry = 0;while(i < n && i < m){int num = 0;num = arr1[n - 1 - i] + arr2[m - 1 - i];if(carry == 1 && num == 0){res.push_back(1);carry = -1;++i;continue;}num -= carry;if(num == 2){res.push_back(0);carry = 1;++i;continue;} else if(num == 3){res.push_back(1);carry = 1;++i;continue;}carry = 0;res.push_back(num);++i;}while(i < n){int num = arr1[n - 1 - i];if(carry == 1 && num == 0){res.push_back(1);carry = -1;++i;continue;}num -= carry;if(num == 2){carry = 1;res.push_back(0);++i;continue;}carry = 0;res.push_back(num);++i;}while(i < m){int num = 0;num = arr2[m - 1 - i];if(carry == 1 && num == 0){res.push_back(1);carry = -1;++i;continue;} num -= carry;if(num == 2){carry = 1;res.push_back(0);++i;continue;}carry = 0;res.push_back(num);++i;}if(carry == 1){res.push_back(1);res.push_back(1);}int len = res.size();for(int i = 0; i < len - 1; ++i){if(res[len - 1 - i] == 0){res.pop_back();} else{break;}}reverse(res.begin(), res.end());return res;}
};

五、解题思路

(1) 与这道题目类似的题目很多，最基础的就是二进制加法，本道题目一定不要思考先将两个加数算出来再进行二进制转换，思路上虽然可行，但实际上会溢出，所以这道题目实际上还是考虑的是模拟。

(2) 设置进位位是carry，现在考虑进位怎么进行计算，如果进位为1，那么相当于在这道题目上要下一位-1，这原因举个例子便知晓。如果第一位两个数字相加得2，那么相当于加数为2，如果第二位（-2）¹有一位，那么直接减去即可。所以我们得到最终的每一位的数字是arr1[i] + arr2[i] - carry，又因为我们是低位开始运算，所以arr1[i] 实际上是arr1[n - 1 - i]，arr[i] 实际上是arr2[m - 1 - i]。

(3) 现在还有一个特殊情况，就是如果存在进位，但是更高一位并没有可以减去的，即两个加数在该位置都为0，这个时候则最终结果在该位置为1，进位carry = 1即可。

(4) 按照上述规则进行模拟即可。

(5) 最后其实推荐大家可以阅读该篇文章，也是关于负二进制数的2023-04-06 LeetCode每日一题（负二进制数转换）