1017. Convert to Base -2

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).

The returned string must have no leading zeroes, unless the string is "0".

Example 1:

Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: "111" Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

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

Note:

  1. 0 <= N <= 10^9

这道题给了一个十进制的非负数N,让转为以负二进制的数。我们对于十进制数转二进制的数字应该比较熟悉,就是每次 N%2 或者 N&1,然后再将N右移一位,即相当于除以2,直到N为0为止。对于转为负二进制的数字,也是同样的做法,唯一不同的是,每次要除以 -2,即将N右移一位之后,要变为相反数,参见代码如下:

解法一:

class Solution {
public:
    string baseNeg2(int N) {
        string res;
        while (N != 0) {
            res = to_string(N & 1) + res;
            N = -(N >> 1);
        }
        return res == "" ? "0" : res;
    }
};

由于转二进制数是要对2取余,则转负二进制就要对 -2 取余,然后N要除以 -2,但是有个问题是,取余操作可能会得到负数,但我们希望只得到0或1,这样就需要做些小调整,使其变为正数,变化方法是,余数加2,N加1,证明方法如下所示:

-1 = (-2) * 0 + (-1)
-1 = (-2) * 0 + (-2) + (-1) - (-2)
-1 = (-2) * (0 + 1) + (-1) - (-2)

先加上一个 -2,再减去一个 -2,合并后就是N加1,余数加2,这样就可以把余数加到结果字符串中了,参见代码如下:

解法二:

class Solution {
public:
    string baseNeg2(int N) {
        string res;
        while (N != 0) {
            int rem = N % (-2);
            N /= -2;
            if (rem < 0) {
                rem += 2;
                N += 1;
            }
            res = to_string(rem) + res;
        }
        return res == "" ? "0" : res;
    }
};

讨论:我们都知道对于一个正数来说,右移一位就相当于除以2,但是对于负数来说,右移一位却不等于除以2。比如 -3 除以2,等于 -1,但是右移一位却不等于 -1,-3 的八位的表示为 11111101,右移一位是 11111110,是 -2。

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1017

类似题目:

Encode Number

参考资料:

https://leetcode.com/problems/convert-to-base-2/

https://leetcode.com/problems/convert-to-base-2/discuss/265544/C%2B%2B-Geeks4Geeks

https://leetcode.com/problems/convert-to-base-2/discuss/265507/JavaC%2B%2BPython-2-lines-Exactly-Same-as-Base-2

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation