Description: 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:
Example 1:
Input: n = 2 Output: "110" Explantion: (-2)2 + (-2)1 = 2
Example 2:
Input: n = 3 Output: "111" Explantion: (-2)2 + (-2)1 + (-2)0 = 3
Example 3:
Input: n = 4 Output: "100" Explantion: (-2)2 = 4
Constraints:
0 <= n <= 10^9
题目描述: 给出数字 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
思路:
模拟 按照 2 进制转换 不过每次都需要变号 时间复杂度为 O(lgn), 空间复杂度为 O(1)
代码: C++:
class Solution
{
public:
string baseNeg2(int n)
{
string result;
while (n)
{
result += to_string(n & 1);
n = -(n >> 1);
}
reverse(result.begin(), result.end());
return result.empty() ? "0" : result;
}
};Java:
class Solution {
public String baseNeg2(int n) {
StringBuilder result = new StringBuilder();
while (n != 0) {
result.append(n & 1);
n = -(n >> 1);
}
return result.isEmpty() ? "0" : result.reverse().toString();
}
}Python:
class Solution:
def baseNeg2(self, n: int) -> str:
result = ''
while n:
n, k = -(n >> 1), n & 1
result += str(k)
return result[::-1] if result else '0'