【负二进制】个人练习-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;
    }
};