Question

1017. 负二进制转换

English Version

题目描述

给你一个整数 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

解法

方法一：模拟

我们可以判断 $n$ 从低位到高位的每一位，如果该位为 $1$，那么答案的该位为 $1$，否则为 $0$。如果该位为 $1$，那么我们需要将 $n$ 减去 $k$。接下来我们更新 $n = \lfloor n / 2 \rfloor$, $k = -k$。继续判断下一位。

最后，我们将答案反转后返回即可。

时间复杂度 $O(\log n)$，其中 $n$ 为给定的整数。忽略答案的空间消耗，空间复杂度 $O(1)$。

相似题目：

• 1073. 负二进制数相加

class Solution:
  def baseNeg2(self, n: int) -> str:
    k = 1
    ans = []
    while n:
      if n % 2:
        ans.append('1')
        n -= k
      else:
        ans.append('0')
      n //= 2
      k *= -1
    return ''.join(ans[::-1]) or '0'

class Solution {
  public String baseNeg2(int n) {
    if (n == 0) {
      return "0";
    }
    int k = 1;
    StringBuilder ans = new StringBuilder();
    while (n != 0) {
      if (n % 2 != 0) {
        ans.append(1);
        n -= k;
      } else {
        ans.append(0);
      }
      k *= -1;
      n /= 2;
    }
    return ans.reverse().toString();
  }
}

class Solution {
public:
  string baseNeg2(int n) {
    if (n == 0) {
      return "0";
    }
    int k = 1;
    string ans;
    while (n) {
      if (n % 2) {
        ans.push_back('1');
        n -= k;
      } else {
        ans.push_back('0');
      }
      k *= -1;
      n /= 2;
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

func baseNeg2(n int) string {
  if n == 0 {
    return "0"
  }
  ans := []byte{}
  k := 1
  for n != 0 {
    if n%2 != 0 {
      ans = append(ans, '1')
      n -= k
    } else {
      ans = append(ans, '0')
    }
    k *= -1
    n /= 2
  }
  for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  return string(ans)
}

function baseNeg2(n: number): string {
  if (n === 0) {
    return '0';
  }
  let k = 1;
  const ans: string[] = [];
  while (n) {
    if (n % 2) {
      ans.push('1');
      n -= k;
    } else {
      ans.push('0');
    }
    k *= -1;
    n /= 2;
  }
  return ans.reverse().join('');
}