LeetCode 1073. 负二进制数相加

[yinxin630]

题目

https://leetcode-cn.com/contest/weekly-contest-139/problems/adding-two-negabinary-numbers/

思路

1. 为了方便计算, 首先将数组逆序, 并填充到相同长度
2. 逐位计算, 但是进位规则和正二进制有些区别:
   a. 如果当前位结果大于1, 则进位为-1, 结果 -= 2
   b. 如果当前位结果等于-1, 则进位为1, 结果为1
   c. 如果是其他情况, 则进位为0, 结果不变
3. 将结果逆序回来, 并去掉前导0, 注意结果为全0的情况

代码

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var addNegabinary = function(arr1, arr2) {
    arr1.reverse();
    arr2.reverse();
    if (arr1.length < arr2.length) {
        arr1.push(...new Array(arr2.length - arr1.length).fill(0));
    } else {
        arr2.push(...new Array(arr1.length - arr2.length).fill(0));
    }

    let result = [];
    let carry = 0;
    for (let i = 0; i < arr1.length || carry !== 0; i++) {
        let n = (arr1[i] || 0) + (arr2[i] || 0) + carry;
        if (n > 1) {
            carry = -1;
            n -= 2;
        } else if (n === -1) {
            carry = 1;
            n = 1;
        } else {
            carry = 0;
        }
        result.push(n);
    }

    result.reverse();

    if (result.length > 1 && result[0] === 0) {
        if (result.every(x => x === 0)) {
            result.length = 1;
        } else {
            let count = 0;
            for (let i = 0; result[i] === 0; i++) {
                count++;
            }
            result = result.slice(count);
        }
    }

    return result;
};