[LeetCode]Convert to Base -2

题目描述:

LeetCode 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转换为-2进制

解题思路:

位运算

Python代码 (版本1):

class Solution(object):
    def baseNeg2(self, N):
        """
        :type N: int
        :rtype: str
        """
        pow = 1
        ans = ''
        while N:
            if N & abs(pow):
                ans += '1'
                N -= pow
            else:
                ans += '0'
            pow *= -2
        return ans[::-1] or "0"

Python代码 (版本2):

class Solution(object):
    def baseNeg2(self, N):
        """
        :type N: int
        :rtype: str
        """
        ans = ''
        while N:
            ans += str(N & 1)
            N = -(N >> 1)
        return ans[::-1] or "0"

附录 (进制转换对照):

  1 2 3 4 5 6 7 8
Base2 00001 00010 00011 00100 00101 00110 00111 01000
Base-2 00001 00110 00111 00100 00101 11010 11011 11000

 

本文链接:http://bookshadow.com/weblog/2019/03/31/leetcode-convert-to-base-2/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论