题目链接
Leetcode.1017 负二进制转换 Rating : 1698
题目描述
给你一个整数 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 < = 1 0 9 0 <= n <= 10^9 0<=n<=109
解法:模拟除法
以 9 为例,模拟这个过程:
时间复杂度: O ( l o g n ) O(logn) O(logn)
C++代码:
class Solution {
public:
string baseNeg2(int n) {
if(n == 0) return "0";
if(n == 1) return "1";
if(n & 1) return baseNeg2((n - 1)/-2) + "1";
else return baseNeg2(n/-2) + "0";
}
};