LeetCode-Go 题解1073 Adding Two Negabinary Numbers 负二进制加法——绕过十进制的直接进位模拟【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 1073 题 Adding Two Negabinary Numbers负二进制数相加展开完整解析LeetCode-Go仓库中该题目的官方 Go 实现先说明为什么先转十进制再相加的思路会在长数据上溢出失败再给出直接在 -2 进制上从低位向高位模拟进位的 O(n) 解法并逐一证明进位三种情形的数学正确性。读完本文你将掌握负进制加法的进位本质进位值为 -1 而非 1、前导零的处理技巧以及仓库中配套的测试用例是如何覆盖边界与超长数据的。题目以数组形式给出的 -2 进制数给定两个基数base为-2的数arr1和arr2返回它们相加的结果。每个数以数组格式给出数组由若干0和1组成按**最高有效位MSB到最低有效位LSB**的顺序排列。例如arr [1,1,0,1]表示数字(-2)^3 (-2)^2 (-2)^0 -8 4 0 1 -3数组格式的数是不含前导零的要么arr [0]要么arr[0] 1。要求返回的结果同样为不含前导零、由0和1组成的数组。官方示例Input: arr1 [1,1,1,1,1], arr2 [1,0,1] Output: [1,0,0,0,0]解释arr1表示 11arr2表示 5两者之和为 16其 -2 进制表示为[1,0,0,0,0]即(-2)^4 16。题目约束1 arr1.length 10001 arr2.length 1000arr1和arr2都没有前导零arr1[i]为0或1arr2[i]为0或1也就是说两个操作数的长度最长可达 1000 位这正是决定算法选型的关键约束详见下文。为什么先转十进制的思路行不通面对进制转换类题目最直观的直觉是先把两个 -2 进制数转成十进制做加法再把结果表示回 -2 进制。这个思路完全正确但在本题的数据范围下会失败——因为数组长度最长 1000其代表的十进制数值可以轻易超过int64最大约 9.2×10^18的表示范围。仓库源码中保留了这一错误示范作为对照见 解法二的实现 及其注释// 解法二 标准的模拟但是这个方法不能 AC因为测试数据超过了 64 位普通数据类型无法存储 func addNegabinary1(arr1 []int, arr2 []int) []int { return intToNegabinary(negabinaryToInt(arr1) negabinaryToInt(arr2)) }从源码注释可以确认这道题在第 257 / 267 组测试数据处会出现 WAWrong Answer正是由于十进制中间结果溢出int64即便改用big.Int等大数类型也徒增实现复杂度。因此正确方向是直接进行 -2 进制的加法完全绕开十进制。核心思路直接在 -2 进制上模拟低位进位加法天然从低位到高位逐位累加遇到进位再从低往高推进。所以从两个数组的末尾LSB往前扫描模拟低位相加的过程即可。关键在于进位规则。假设从 k-1 位向高位 k 产生了一次进位而 k-1 位是两个 1 相加即1 1 carry的情形那么 k 位上的两个数字存在三种组合逐一分析如下原文档给出的完整数学证明情形一k 位上是 0 和 0 → 最终 k 位为 1证明由于进位是由 k-1 位进过来的所以 k-1 位是 2 个 1现在 k 位是 2 个 0加起来的和是2 * (-2)^(k-1)。当 k 为奇数时2 * (-2)^(k-1) (-1)^(k-1) * 2 * 2^(k-1) 2^k当 k 为偶数时2 * (-2)^(k-1) (-1)^(k-1) * 2 * 2^(k-1) -2^k综合起来就是(-2)^k所以最终 k 位上有一个 1。情形二k 位上是 0 和 1 → 最终 k 位为 0证明由于进位是由 k-1 位进过来的所以 k-1 位是 2 个 1现在 k 位是 1 个 0 和 1 个 1加起来的和是(-2)^k 2 * (-2)^(k-1)。当 k 为奇数时(-2)^k 2 * (-2)^(k-1) -2^k 2^k 0当 k 为偶数时(-2)^k 2 * (-2)^(k-1) 2^k - 2^k 0综合起来就是 0所以最终 k 位上有一个 0。情形三k 位上是 1 和 1 → 最终 k 位为 1证明由于进位是由 k-1 位进过来的所以 k-1 位是 2 个 1现在 k 位是 2 个 1加起来的和是2 * (-2)^k 2 * (-2)^(k-1)。当 k 为奇数时2 * (-2)^k 2 * (-2)^(k-1) -2^(k1) 2^k 2^k * (1 - 2) -2^k当 k 为偶数时2 * (-2)^k 2 * (-2)^(k-1) 2^(k1) - 2^k 2^k * (2 - 1) 2^k综合起来就是(-2)^k所以最终 k 位上有一个 1。结论负进制的进位是 -1综上所述-2 进制的进位原理与 2 进制完全一致唯一的差别是2 进制的进位是 1而 -2 进制的进位是 -1。更直白地说低位一旦产生进位k-1 位两个 1 相加无论高位两位如何取值都可以用当前位结果 向更高位产生一个值为 -1 的进位来统一表达。这就是下面源码中那两行核心公式的由来。源码实现逐行解析O(n) 直接进位模拟仓库中的 解法一实现 将上述推导浓缩为极简代码// 解法一 模拟进位 func addNegabinary(arr1 []int, arr2 []int) []int { carry, ans : 0, []int{} for i, j : len(arr1)-1, len(arr2)-1; i 0 || j 0 || carry ! 0; { if i 0 { carry arr1[i] i-- } if j 0 { carry arr2[j] j-- } ans append([]int{carry 1}, ans...) carry -(carry 1) } for idx, num : range ans { // 去掉前导 0 if num ! 0 { return ans[idx:] } } return []int{0} }循环条件i 0 || j 0 || carry ! 0三个子条件缺一不可i 0arr1尚未扫完j 0arr2尚未扫完carry ! 0两个数组都扫完后可能仍残留向更高位的进位必须继续吐出。由于负进制进位可能为负-1carry的取值在单轮内可能为-1、0、1、2等因此用carry ! 0而非carry 0判断这是负进制与正进制实现上最容易被忽略的差异点。核心公式一ans append([]int{carry 1}, ans...)carry累加了本位两个数字与低位传来的进位carry 1取出其最低位作为当前位结果。使用 1而非% 2是因为 Go 中负数取模结果仍为负如-1 % 2 -1而按位与 1对-1同样得到1-1 的二进制补码最低位为 1恰好符合负进制的位值约定。每次把结果头插到ans前面保证最终数组仍是 MSB 在前的顺序。核心公式二carry -(carry 1)这是整个算法最精妙的一行把累加值右移一位相当于除以 2 并向下取整再取相反数作为向更高一位传递的进位。它的正确性正是前述三种情形证明的直接编码低位两个 1连同可能传来的进位产生进位时carry 1得到向 k 位的权值 1取负后即为-1对应负进制的进位是 -1这一结论当carry为负数例如前一轮留下的 -1 与本位数字相加时 1与取负的组合依然把2 的权值正确地换算成(-2)的权值保证数学推导与位运算严格一致。去除前导零负进位可能产生多余的 0由于进位可能为 -1模拟过程中可能在结果最高位之前产生多余的0因此最后需要扫描一次结果数组把前导零全部去掉for idx, num : range ans { // 去掉前导 0 if num ! 0 { return ans[idx:] } } return []int{0}如果整条结果全为 0例如0 0循环结束后返回[]int{0}符合题目不含前导零的格式约定arr [0]是允许的。在 测试文件 中{0} {0}的期望输出正是[0]。备选方案十进制往返实现仅供对照不可 AC除正式解法外仓库还保留了十进制往返的完整实现addNegabinary1由两个辅助函数组成它们本身是负进制与十进制互转的标准写法很有参考价值。负进制转十进制negabinaryToIntfunc negabinaryToInt(arr []int) int { if len(arr) 0 { return 0 } res : 0 for i : 0; i len(arr)-1; i { if res 0 { res (-2) * arr[i] } else { res res * (-2) res (-2) * arr[i] } } return res 1*arr[len(arr)-1] }其本质是霍纳法则Horners rule的负基数版本从最高位开始每读入一位数字就把当前结果乘(-2)再加上该位的贡献最后一位LSB权重为(-2)^0 1。空切片分支返回 0 的边界处理在 测试文件 中有专门覆盖。十进制转负进制intToNegabinaryfunc intToNegabinary(num int) []int { if num 0 { return []int{0} } res : []int{} for num ! 0 { remainder : num % (-2) num num / (-2) if remainder 0 { remainder 2 num } res append([]int{remainder}, res...) } return res }负数基数的整除取余有个陷阱Go 中num % (-2)可能得到负余数此时需要修正——余数加 2、商加 1以保证余数落在合法的{0, 1}范围内。这是负进制与正进制转换唯一需要特判的地方。需要再次强调该方案仅用于对照与学习在本题 1000 位长度的数据下会溢出int64导致 WA正式提交必须使用解法一。测试用例与验证方式仓库为本题编写了完整的 单元测试Test_Problem1073覆盖了超长数据组两个长度约 600 位、1000 位量级的随机二进制数组用于验证解法一在大数场景下不溢出、结果正确这正是十进制往返方案会 WA 的那类用例源码注释中提到的第 257 / 267 组测试即属此类题目示例[1,1,1,1,1] [1,0,1] [1,0,0,0,0]11 5 16边界用例{0} {0} - [0]、{0} {1,1} - [1,1]、{0} {1,0,0,1} - [1,0,0,1]、{0} {1,0} - [1,0]验证含 0 操作数与结果即另一操作数的情况覆盖率补丁negabinaryToInt([]int{})的空切片分支对应源码len(arr) 0的防御逻辑。若本机已安装 Go 工具链可在仓库根目录按 gotest.sh 的方式运行全量测试并统计覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...单独验证本题时可直接进入对应目录执行go test -v -run Test_Problem1073 ./leetcode/1073.Adding-Two-Negabinary-Numbers/复杂度分析时间复杂度O(n)其中 n 为两个数组中较长的长度。一次从低位到高位的扫描即完成全部加法进位处理是常数时间最后的去前导零扫描同样是 O(n)。空间复杂度O(n)结果数组ans的长度与输入规模同阶。总结LeetCode 1073 题的核心收获有三点进制转换并非必须经过十进制当数据规模超出原生整数范围时直接在当前进制内模拟进位往往比中转十进制更简洁、更可靠负进制的进位是 -1carry -(carry 1)一行同时处理了正负进位配合carry 1取位是负进制加法最优雅的编码方式格式细节决定成败负进位会带来多余的高位 0必须扫描并去除前导零0 0时结果须为[0]以符合题目格式约定。完整的题目说明、三种进位情形的数学证明与对照实现均收录于 本题 README可直接运行验证的源码与测试见 实现文件 与 测试文件。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
