javascript 解法, 执行用时: 51 ms, 内存消耗: 49.2 MB, 提交时间: 2024-04-28 09:32:46

/**
 * @param {number} n
 * @return {string}
 */
var baseNeg2 = function(n) {
    if (n === 0 || n === 1) {
        return '' + n;
    }
    let res = '';
    while (n !== 0) {
        const remainder = n & 1;
        res += remainder;
        n -= remainder;
        n /= -2;
    }
    return res.split('').reverse().join('');
};

golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-04-28 09:32:33

// 进制转换
func baseNeg2(n int) string {
    if n == 0 || n == 1 {
        return strconv.Itoa(n)
    }
    res := []byte{}
    for n != 0 {
        remainder := n & 1
        res = append(res, '0'+byte(remainder))
        n -= remainder
        n /= -2
    }
    for i, n := 0, len(res); i < n/2; i++ {
        res[i], res[n-1-i] = res[n-1-i], res[i]
    }
    return string(res)
}

// 数学计算
func baseNeg2_2(n int) string {
    val := 0x55555555 ^ (0x55555555 - n)
    if val == 0 {
        return "0"
    }
    res := []byte{}
    for val > 0 {
        res = append(res, '0'+byte(val&1))
        val >>= 1
    }
    for i, n := 0, len(res); i < n/2; i++ {
        res[i], res[n-1-i] = res[n-1-i], res[i]
    }
    return string(res)
}

java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2022-12-08 11:44:53

class Solution {
    public String baseNeg2(int N) {

        if(N == 0)
            return "0";
        
        String result = "";

        int n = N;
        while(n != 0) {
            if (n % 2 == 0) {
                result = "0" + result;
                n = n / (-2);
            } else {
                result = "1" + result;
                n = (n - 1) / (-2);
            }
        }

        return result;
    }
    
}

java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2022-12-08 11:43:01

class Solution {
    public String baseNeg2(int N) {
        StringBuilder res = new StringBuilder();
        while (N != 0) {
            res.append(N & 1);
            N = -(N >> 1);
        }
        return res.length() > 0 ? res.reverse().toString() : "0";
    }
}

python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-12-08 11:42:32

class Solution:
    def baseNeg2(self, n: int) -> str:
        if not n: return '0'
        def dfs(cur):
            if cur == 0: return ''
            if cur & 1: # 是奇数的情况
                return dfs((cur - 1) // -2) + '1'
            else:
                return dfs(cur // -2) + '0'
        
        return dfs(n)

python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-08 11:41:34

class Solution:
    # 通过数学推导可以得到+K/-K进制的通用转化法
    def baseK(self, N, K):
        alphabet = "0123456789ABCDEF"
        if N == 0:
            return ["0"]
        res = []
        while N != 0:
            temp = ((N % K) + abs(K)) % abs(K)
            res.append(alphabet[temp])
            N -= temp
            N //= K
        return res[::-1]
    
    def baseNeg2(self, N: int) -> str:
        nums = self.baseK(N, -2)
        return "".join(nums)

cpp 解法, 执行用时: 0 ms, 内存消耗: 5.9 MB, 提交时间: 2022-12-08 11:41:01

class Solution {
public:
    // 无论K是正数还是负数都支持（只支持-10～10进制，因为更高进制需要引入字母）
    vector<int> baseK(int N, int K) {
        if (N == 0) return {0};
        vector<int> res;
        while (N != 0) {
            int r = ((N % K) + abs(K)) % abs(K); // 此处为关键
            res.push_back(r);
            N -= r;
            N /= K;
        }
        reverse(res.begin(), res.end());
        return res;
    }
    string baseNeg2(int N) {
        vector<int> nums = baseK(N, -2);
        string res;
        for (auto x : nums) res += to_string(x);
        return res;
    }
};