1017-负二进制转换(Convert to Base -2)

原文链接: https://leetcode-cn.com/problems/convert-to-base-2

英文原文

Given an integer n, return a binary string representing its representation in base -2.

Note that the returned string should not have leading zeros unless the string is "0".

Example 1:

Input: n = 2
Output: "110"
Explantion: (-2)² + (-2)¹ = 2

Example 2:

Input: n = 3
Output: "111"
Explantion: (-2)² + (-2)¹ + (-2)⁰ = 3

Example 3:

Input: n = 4
Output: "100"
Explantion: (-2)² = 4

Constraints:

0 <= n <= 10⁹

中文题目

给出数字 N，返回由若干 "0" 和 "1"组成的字符串，该字符串为 N 的负二进制（base -2）表示。

除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

示例 1：

输入：2
输出："110"
解释：(-2) ^ 2 + (-2) ^ 1 = 2

示例 2：

输入：3
输出："111"
解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

示例 3：

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

提示：

0 <= N <= 10^9

通过代码

高赞题解

通过数学推导可以得到+K/-K进制的通用转化法

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;
    }
};