2024.4.28力扣每日一题——负二进制转换

2024.4.28

- - 题目来源
  - 我的题解
  - - 方法一进制转换
    - 方法二模拟进位

题目来源

力扣每日一题；题序：1017

我的题解

方法一进制转换

对于以-2为基数的系统，可以这样理解：在-2进制中，每一位的权重是-2的幂。这与传统的二进制表示法不同，后者每一位的权重是2的幂。
要将一个正整数转换为以-2为基数的表示法，可以遵循以下步骤：

初始化：创建一个空的字符串或列表来存储-2进制表示的每一位。
迭代计算：从最高位开始，不断地将整数除以-2，记录每次操作的余数。
反转结果：由于是从最高位开始计算的，最终得到的序列需要反转，以得到正常的-2进制表示。
处理负数：由于除以负数时，除数和被除数的符号会相互影响，需要在每次除法后根据结果调整符号。

时间复杂度：O( $log_{-2}n$ )
空间复杂度：O(1)

public String baseNeg2(int n) {
    if (n == 0) {
        return "0";
    }
    StringBuilder negativeBinary = new StringBuilder();
    while (n != 0) {
        int remainder = n % -2;
        n = n / -2;
        // 如果余数是负数，转换为正数
        if (remainder < 0) {
            remainder += 2;
            n += 1;
        }
        negativeBinary.append(remainder);
    }
    return negativeBinary.reverse().toString();
}

方法二模拟进位

官方题解
比较复杂，没怎么看懂，各位看官请移步官方题解。

时间复杂度：O©。C=32
空间复杂度：O©

public String baseNeg2(int n) {
    if (n == 0) {
        return "0";
    }
    int[] bits = new int[32];
    for (int i = 0; i < 32 && n != 0; i++) {
        if ((n & 1) != 0) {
            bits[i]++;
            if ((i & 1) != 0) {
                bits[i + 1]++;
            }
        }
        n >>= 1;
    }
    int carry = 0;
    for (int i = 0; i < 32; i++) {
        int val = carry + bits[i];
        bits[i] = val & 1;
        carry = (val - bits[i]) / (-2);
    }
    int pos = 31;
    StringBuilder res = new StringBuilder();
    while (pos >= 0 && bits[pos] == 0) {
        pos--;
    }
    while (pos >= 0) {
        res.append(bits[pos]);
        pos--;
    }
    return res.toString();
}