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,此时是一种特殊情况,需要单独讨论:文章来源:https://www.toymoban.com/news/detail-451579.html
当 ans[i] = -1 时,需要将其进行转换。又注意到:
(-2)i+1 + (-2)i = - (-2)i,所以将 ans[i] 赋为 -1 和将 ans[i] 和 ans[i+1] 都加 1 的效果是一样的,因此更新 carry = 1,ans[i] = 1。文章来源地址https://www.toymoban.com/news/detail-451579.html
// 官方解法
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;
}
};
到了这里,关于【LeetCode - 每日一题】1073. 负二进制数相加 (2023.05.18)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!