Medium

题目描述

给定一个整数 n，返回一个表示其在 -2 进制下表示的二进制字符串。

注意返回的字符串不应该有前导零，除非字符串是 “0”。

示例 1：

输入：n = 2
输出："110"
解释：(-2)² + (-2)¹ = 4 + (-2) = 2

示例 2：

输入：n = 3
输出："111"
解释：(-2)² + (-2)¹ + (-2)⁰ = 4 + (-2) + 1 = 3

示例 3：

输入：n = 4
输出："100"
解释：(-2)² = 4

约束条件：

  • 0 <= n <= 10⁹

解题思路

解题思路

这道题要求将十进制数转换为 -2 进制表示。关键在于理解 -2 进制的工作原理。

核心思想

在普通二进制中，我们用除以2取余的方法。在 -2 进制中，我们需要用除以 -2 取余的方法，但需要特别处理余数。

算法步骤

  1. 处理特殊情况：如果 n = 0，直接返回 “0”
  2. 循环转换：当 n > 0 时：
    • 计算 n 除以 -2 的余数
    • 如果余数为负数，需要调整：余数加上基数的绝对值，商减1
    • 将余数添加到结果字符串的前面
    • 更新 n 为新的商

数学原理

对于 -2 进制，每一位的权重是 (-2)^i。当我们做除法时：

  • n = (-2) × 商 + 余数
  • 余数必须在 [0, 1] 范围内

如果普通除法得到负余数，我们需要调整：

  • 余数 = 余数 + 2
  • 商 = 商 - 1

时间复杂度分析

每次循环 n 大约减少一半，所以时间复杂度为 O(log n)。

代码实现

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        
        string result = "";
        while (n > 0) {
            int remainder = n % (-2);
            n /= (-2);
            
            // 如果余数为负，需要调整
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            
            result = to_string(remainder) + result;
        }
        
        return result;
    }
};

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        
        result = ""
        while n > 0:
            remainder = n % (-2)
            n //= (-2)
            
            # 如果余数为负，需要调整
            if remainder < 0:
                remainder += 2
                n += 1
            
            result = str(remainder) + result
        
        return result

public class Solution {
    public string BaseNeg2(int n) {
        if (n == 0) return "0";
        
        string result = "";
        while (n > 0) {
            int remainder = n % (-2);
            n /= (-2);
            
            // 如果余数为负，需要调整
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            
            result = remainder.ToString() + result;
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {string}
 */
var baseNeg2 = function(n) {
    if (n === 0) return "0";
    
    let result = "";
    
    while (n !== 0) {
        if (n % 2 === 0) {
            result = "0" + result;
            n = n / -2;
        } else {
            result = "1" + result;
            n = (n - 1) / -2;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log n)每次循环n大约减少一半
空间复杂度O(log n)结果字符串长度与log n成正比

相关题目