Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 1073. 负二进制数相加 #14

Open
yinxin630 opened this issue Jun 4, 2019 · 0 comments
Open

LeetCode 1073. 负二进制数相加 #14

yinxin630 opened this issue Jun 4, 2019 · 0 comments
Labels

Comments

@yinxin630
Copy link
Owner

题目

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;
};
@yinxin630 yinxin630 changed the title LeetCode 5078. 负二进制数相加 LeetCode 1073. 负二进制数相加 Jul 5, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant