1073.负二进制数相加

链接：1073.负二进制数相加
难度：Medium
标签：数组、数学
简介：给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

题解 1 - cpp

• 编辑时间：2023-05-18
• 执行用时：8ms
• 内存消耗：19.1MB
• 编程语言：cpp
• 解法介绍：统一两个数组，如果都1，那可以抵消下一位的1，如果该位需要增加1，可以在该位加1，且下一位加1。

class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        for (int i = 0; i < max(arr1.size(), arr2.size()); i++) {
            if (i == arr1.size()) arr1.push_back(0);
            if (i == arr2.size()) arr2.push_back(0);
        }
        vector<int> res;
        for (int i = 0, add = 0; i < arr1.size(); i++) {
            switch (arr1[i] + arr2[i] + add) {
                case -1: res.push_back(1); add = 1; break;
                case 0: res.push_back(0); add = 0; break;
                case 1: res.push_back(1); add = 0; break;
                case 2: res.push_back(0); add = -1; break;
                case 3: res.push_back(1); add = -1; break;
            }
            if (i == arr1.size() - 1 && add != 0) arr1.push_back(0), arr2.push_back(0);
        }
        while (res.size() > 1 && res.back() == 0) res.pop_back();
        reverse(res.begin(), res.end());
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-05-18
• 执行用时：48ms
• 内存消耗：16.3MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr1.reverse()
        arr2.reverse()
        print(arr1, arr2)
        for i in range(max(len(arr1), len(arr2))):
            if i == len(arr1):
                arr1.append(0)
            if i == len(arr2):
                arr2.append(0)
        res = []
        i = add = 0
        while i < len(arr1):
            match arr1[i] + arr2[i] + add:
                case -1:
                    res.append(1)
                    add = 1
                case 0:
                    res.append(0)
                    add = 0
                case 1:
                    res.append(1)
                    add = 0
                case 2:
                    res.append(0)
                    add = -1
                case 3:
                    res.append(1)
                    add = -1
            if i == len(arr1) - 1 and add != 0:
                arr1.append(0)
                arr2.append(0)
            i += 1
        while len(res) > 1 and res[-1] == 0:
            res.pop()
        res.reverse()
        return res

题解 3 - rust

• 编辑时间：2023-05-18
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn add_negabinary(mut arr1: Vec<i32>, mut arr2: Vec<i32>) -> Vec<i32> {
        arr1.reverse();
        arr2.reverse();
        for i in 0..arr1.len().max(arr2.len()) {
            if i == arr1.len() {
                arr1.push(0);
            }
            if i == arr2.len() {
                arr2.push(0);
            }
        }
        let mut res = vec![];
        let (mut i, mut add) = (0, 0);
        while i < arr1.len() {
            match arr1[i] + arr2[i] + add {
                -1 => {
                    res.push(1);
                    add = 1;
                }
                0 => {
                    res.push(0);
                    add = 0;
                }
                1 => {
                    res.push(1);
                    add = 0;
                }
                2 => {
                    res.push(0);
                    add = -1;
                }
                3 => {
                    res.push(1);
                    add = -1;
                }
                _ => {}
            }
            if i == arr1.len() - 1 && add != 0 {
                arr1.push(0);
                arr2.push(0);
            }
            i += 1;
        }
        while res.len() > 1 && *res.last().unwrap() == 0 {
            res.pop();
        }
        res.reverse();
        res
    }
}