1073. 負二進制數(shù)相加

題意

• 基數(shù)為 -2 。
• 實現(xiàn)兩個 0/1 數(shù)組串的加法。

解法

這是一道模擬題。

設(shè) arr1[i] 和 arr2[i] 是數(shù)組 arr1 和 arr2 從低到高的第 i 位數(shù)。

首先回顧普通的二進制數(shù)的相加，從低位開始計算，在計算的同時維護用一個變量 carry 維護進位信息，因此，對于第 i 位的結(jié)果 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。

類比到基數(shù)為 -2 的二進數(shù)相加上，從低位開始計算，在計算的同時用一個變量 carry 維護進位信息，同樣地，對于第 i 為的結(jié)果 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 時，需要將其進行轉(zhuǎn)換。又注意到：
(-2)ⁱ⁺¹ + (-2)ⁱ = - (-2)ⁱ，所以將 ans[i] 賦為 -1 和將 ans[i] 和 ans[i+1] 都加 1 的效果是一樣的，因此更新 carry = 1，ans[i] = 1。文章來源地址http://www.zghlxwxcb.cn/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 循環(huán)條件里
        {
            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;
    }
};

到了這里，關(guān)于【LeetCode - 每日一題】1073. 負二進制數(shù)相加 （2023.05.18）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！