负二进制转换
给你一个整数 n
,以二进制字符串的形式返回该整数的 负二进制(base -2
)表示。
注意,除非字符串就是 "0"
,否则返回的字符串中不能含有前导零。
示例 1:
输入:n = 2 输出:"110" 解释:(-2)2 + (-2)1 = 2
示例 2:
输入:n = 3 输出:"111" 解释:(-2)2 + (-2)1 + (-2)0 = 3
示例 3:
输入:n = 4 输出:"100" 解释:(-2)2 = 4
提示:
0 <= n <= 109
思路:将一个十进制的数 n 转化为任意 x 进制都可以使用这样的思路。
第一步:先得到转化为进制结果的最后一位 t :n % x (但如果得到的最后一位是负数的话,需要根据语言特性将其转化为正数),然后将最后一位添加到目标字符串中,然后将这个最后一位 t 在 n 中减去。
第二步:将这个十进制数按 x 进制的规则右移一位:n /= x,然后重复得到最后一位并添加的操作,最终可以得到一个字符串。
第三步:因为每次得到的都是理论上的最后一位,所以最后需要将字符串逆置,就得到了最终答案!
力扣代码:
class Solution {
public:string baseNeg2(int n) {if(n == 0) return "0";int x = -2;string s;while (n) {if (n % x == 0) // 最后一位数是 0s += "0";else {// 将最后一位减去, 因为 x 进制的最后一位在权重上和十进制是一样n -= 1; s += "1";}n /= x; // 将 n 右移一位}reverse(s.begin(), s.end()); // 逆序字符串return s;}
};