LeetCode 每日一题 ---- 【1017.负二进制转换】

1017.负二进制转换

方法一：模拟进制转换

我们平常做进制转换最常用的方法就是辗转相除法，下面的图示分别给出了普通的10进制转2进制的过程，和10进制转 -2进制的过程

这里我们来推导一下右边的计算过程的合规性。
我们设 被除数为a，除数为b，余数为c
则有 a = (-2) * b + c，当余数c等于 -1 时，那么我们就不好表示了，我们就可以在这里变形：

a = (-2) * b + c
a - (-2) * b = c
a - (-2) * b + 2 = c + 2
a - (-2) * (b + 1) = c + 2

当c == -1时，我们可以加2，转换为1，然后将辗转相除得到的b的值加1，然后继续做辗转相除的运算操作。

class Solution {
    public String baseNeg2(int n) {
        if (n == 0 || n == 1) return String.valueOf(n);
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            int mod = n % (-2);
            n /= -2;
            if (mod == -1) {
                sb.append(1);
                n ++ ;
            } else {
                sb.append(mod);
            }
        }
        return sb.reverse().toString();
    }
}

推广：任意进制转换

依据上面的逻辑，这个解题逻辑是可以推广到任意进制的，我们设进制为k，则我们我们辗转相除的时候，如果余数小于0，则余数- k(此时k是负数)，商 + 1即可。

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) {
            return "0";
        }
        int k = -2;
        int x = n;
        StringBuilder sb = new StringBuilder();
        while (x != 0) {
            int mod = x % k;
            x /= k;
            if (mod < 0) {
                // 修正一下
                sb.append(mod - k);
                ++x;
            } else {
                sb.append(mod);
            } 
        }
        return sb.reverse().toString();
    }
}

时间复杂度：
O(logn)

空间复杂度：
O(1)