【负二进制】个人练习-Leetcode-1073. Adding Two Negabinary Numbers
题目链接:https://leetcode.cn/problems/adding-two-negabinary-numbers/description/
题目大意:给两个负二进制的数组arr1[], arr2[]
,从前往后是高位到低位。求两个数组的和,格式与前相同。
思路:重要的点是考虑进位是如何做的,因为是负二进制,那么当上一位的和是大于等于2的时候,先%2,然后进位的时候应该进的是-1;而当上一位的和是-1时(考虑两位是0,进位为-1的情况),应该把本位置1,再进位1。剩下的情况就是正常的0和1,直接写入就好。
因为不能有前导0,所以最后需要循环判断一下去掉前导0.
完整代码
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> res;
while (i >= 0 || j >= 0 || carry != 0) {
int tmp = carry + (i >= 0 ? arr1[i] : 0) + (j >= 0 ? arr2[j] : 0);
if (tmp >= 2) {
res.push_back(tmp % 2);
carry = -1;
}
else if (tmp == -1) {
res.push_back(1);
carry = 1;
}
else {
res.push_back(tmp);
carry = 0;
}
i--;
j--;
}
while (res.size() > 1 && res.back() == 0)
res.pop_back();
reverse(res.begin(), res.end());
return res;
}
};