LeetCode 1073. 负二进制数相加

Categories:

题目描述
思路分析
1. 解法一：进位模拟（推荐）
相似题目

题目描述

✅ 1073. 负二进制数相加

思路分析

解法一：进位模拟（推荐）

核心思路：

负二进制进位规则不同，设当前和为 sum，当前位为 sum & 1。

进位可由 carry = -(sum - bit) / 2 得到。

从低位向高位累加，最后去掉前导零。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于保存结果。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int carry = 0;

        List<Integer> res = new ArrayList<>();

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += arr1[i--];
            }
            if (j >= 0) {
                sum += arr2[j--];
            }

            int bit = sum & 1;
            res.add(bit);
            carry = -(sum - bit) / 2;
        }

        while (res.size() > 1 && res.get(res.size() - 1) == 0) {
            res.remove(res.size() - 1);
        }

        int[] ans = new int[res.size()];
        for (int k = 0; k < res.size(); k++) {
            ans[k] = res.get(res.size() - 1 - k);
        }

        return ans;
    }
}

func addNegabinary(arr1 []int, arr2 []int) []int {
	i := len(arr1) - 1
	j := len(arr2) - 1
	carry := 0

	res := make([]int, 0)

	for i >= 0 || j >= 0 || carry != 0 {
		sum := carry
		if i >= 0 {
			sum += arr1[i]
			i--
		}
		if j >= 0 {
			sum += arr2[j]
			j--
		}

		bit := sum & 1
		res = append(res, bit)
		carry = -(sum - bit) / 2
	}

	for len(res) > 1 && res[len(res)-1] == 0 {
		res = res[:len(res)-1]
	}

	for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
		res[l], res[r] = res[r], res[l]
	}

	return res
}

相似题目

题目	难度	考察点
1073. 负二进制数相加	中等	进位模拟
2. 两数相加	中等	进位
66. 加一	简单	进位
415. 字符串相加	简单	大数模拟
989. 数组形式的整数加法	简单	进位

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/46603774