题目:
给你一个整数 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 <= 109
Related Topics
思想:
我们可以判断 n 从低位到高位的每一位,如果该位为 1,那么答案的该位为 1,否则为 0。如果该位为 1,那么我们需要将 n 减去 k。接下来我们更新 n=⌊n/2⌋, k=−k。继续判断下一位。
最后,我们将答案反转后返回即可。
时间复杂度 O(logn),其中 n 为给定的整数。忽略答案的空间消耗,空间复杂度 O(1)。
代码:
1 | class Solution: |