LeetCode-Go 题解精读1017. Convert to Base -2 —— 用 Go 短除法实现负二进制转换【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 1017 题Convert to Base -2十进制转负二进制展开完整讲解题目约束、负基数base -2与普通二进制的本质差异并结合 LeetCode-Go 仓库中leetcode/1017.Convert-to-Base-2目录下的 Go 实现与测试用例逐行剖析短除法 余数修正的通用套路。读完本文你将掌握如何把任意十进制非负整数转换为负基数表示并能独立迁移这套方法到其它负基数如 base -3问题中。题目描述给定一个十进制数N返回一个由若干0和1组成的字符串该字符串表示N在**负二进制base -2**下的值。返回的字符串不允许含有前导零除非字符串本身就是0。三个官方示例示例 1 Input: 2 Output: 110 解释: (-2)^2 (-2)^1 4 - 2 2 示例 2 Input: 3 Output: 111 解释: (-2)^2 (-2)^1 (-2)^0 4 - 2 1 3 示例 3 Input: 4 Output: 100 解释: (-2)^2 4约束条件0 N 10^9题目大意给出十进制数N需要将其转换为负二进制base -2字符串。负二进制的每一位权重是(-2)^i且允许的位取值只有0和1。除0本身外输出不能带前导零。这是本项目 README.md 中数论分类下Base conversion进制转换算法的典型题目。解题思路负基数的短除法常规十进制转二进制的思路是不断用2去除目标数记录每次的余数最后把余数逆序拼接。本题是同一思路的变体——把除数从 2 换成 -2即短除法。但这里藏着一个关键陷阱在负基数下余数可能为负数。以N 3为例若直接模仿普通二进制3 / (-2) -1 余 1 -1 / (-2) 0 余 -1 ← 余数为负非法-1不能作为二进制位写入结果。因此需要在余数为负时做进位修正给余数加 2同时让商加 1。其数学依据是被除数 除数 × 商 余数 N (-2) × q r 当 r 0 时改写为 N (-2) × (q 1) (r 2)因为r 2 0r 最小为 -1 时得到 1且r 2 2修正后的余数必然落在合法的{0, 1}区间内从而保证每一位都是合法的0/1位。以N 3验证完整流程步骤除法余数是否修正修正后余数修正后商输出位13 ÷ (-2)1否1-112-1 ÷ (-2)-1是2商111131 ÷ (-2)1否101逆序拼接得到111与示例 2 一致。仓库源码实现解析本仓库在 1017. Convert to Base -2.go 中给出了极简实现完整代码如下package leetcode import strconv func baseNeg2(N int) string { if N 0 { return 0 } res : for N ! 0 { remainder : N % (-2) N N / (-2) if remainder 0 { remainder 2 N } res strconv.Itoa(remainder) res } return res }逐段拆解零值特判N 0直接返回0同时满足无前导零的约束——如果不提前返回循环一次都不会执行结果会是空字符串。循环终止条件for N ! 0每次迭代取当前值对-2的余数作为一位商作为下一轮被除数直到商归零。负余数修正if remainder 0 { remainder 2; N }正是前文推导的进位修正保证每个输出位只可能是0或1。字符串拼接strconv.Itoa(remainder) res采用前插法新位放在最前面短除法先算出来的是低位天然完成逆序无需额外反转。用N 4验证一次完整的迭代过程对应官方示例 3轮次除法余数修正商结果串14 ÷ (-2)0否-202-2 ÷ (-2)0否10031 ÷ (-2)1否0100最终输出100与题目示例一致(-2)^2 4。测试用例与验证仓库配套的 1017. Convert to Base -2_test.go 以表格驱动的方式覆盖了题目给出的核心输入输入 N期望输出211031114110打印展示值非断言00需要注意一个细节该测试文件的para1017/ans1017结构承载了参数-期望的表格定义但Test_Problem1017主体仅通过fmt.Printf打印【input】:... 【output】:...来人工核对结果并未使用t.Errorf或if做自动断言。从源码事实看baseNeg2(4)实际输出是100即题目的正确答案而测试数据表中写的是110由于缺少断言逻辑这不会导致测试失败读者自行阅读时应以题目官方示例与函数实际输出为准。如果你想在本地复现进入对应目录后执行go test -v -run Test_Problem1017 .若希望整仓验证可参考仓库根目录的 gotest.sh它对./leetcode/...全部包统一执行带覆盖率收集的测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...复杂度分析时间复杂度O(log₂N)。每轮迭代将N的绝对值近似减半迭代次数与最终负二进制串长度同阶即约log₂(N1)位。空间复杂度O(log₂N)。需要存储与位数等长的结果字符串。在题目约束0 N 10^9下结果串最长约 30 位int类型完全够用不存在溢出风险本项目 go.mod 声明为 Go 1.19 模块代码遵循标准库strconv完成数字到字符串的转换。小结与延伸负二进制转换的核心就一句话沿用短除法但每次除法后必须把负余数修正为非负的0/1。掌握这个余数修正模板后你可以轻松扩展到任意负基数如 base -3、base -4只需相应调整除数与余数区间的上界。本仓库在 README.md 的 Number theory数论分类中把Base conversion列为专项算法同一思想也可对照复习 1009. Complement of Base-10 Integer按位取反、1689. Partitioning Into Minimum Number Of Deci-Binary Numbers十进制按位拆分等进制类题目形成体系化记忆。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考