1073. Adding Two Negabinary Numbers

题目信息

题号:

1073

难度:

Medium

主题:

负二进制、数组加法、规范表示

原题:

LeetCode 1073

重点:

两个数组按最高位到最低位表示基数 -2 的整数,数值可以为负;返回其和的同类表示,除零外不能有前导零

题目重述

给定两个二进制数组 arr1 和 arr2。数组元素从最高位到最低位排列,每一位为 0 或 1,但位权依次是 (-2)^m,因此它们表示的是基数为 -2 的整数。

计算两个整数的和,并以相同格式返回结果数组。输入和输出除单独的 [0] 外都不含前导零;结果每一位也必须是 0 或 1。

1 <= arr1.length, arr2.length <= 1000,两个数组均为合法的负二进制标准表示。

自建示例

两个负二进制数的和仍使用负位权表示:

输入:arr1 = [1,1,0,1], arr2 = [1,0,1]
输出:[1,1,0]
解释:arr1 表示 -3,arr2 表示 5,和为 2;负二进制 110 表示 4 - 2 = 2。

两个数都为零:

输入:arr1 = [0], arr2 = [0]
输出:[0]
解释:和为零,规范表示必须是单个 0,不能带额外前导零。