leetcode [1017] 负二进制转换

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给出数字 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

解法1，来自题解, 对奇偶数进行区分：

class Solution:
    def baseNeg2(self, N: int) -> str:
        if N == 0:
            return '0'
        ans = ''
        while N != 0:
            if N % 2 == 0:
                ans = '0' + ans
                N = N // (-2)
            else:
                ans = "1" + ans
                N = (N - 1) // (-2)
        return ans

解法2，来自题解:

class Solution:
    def baseNeg2(self, N: int) -> str:
        if N == 0:
            return '0'
        ans = ''
        K = -2
        while N != 0:
            r = ((N % K) + abs(K)) % abs(K) # 此处为关键
            ans = str(r) + ans
            N -= r
            N //= K
        
        return ans