题目

给出数字 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

解题思路分析

1、遍历；时间复杂度O(log(n))，空间复杂度O(log(n))

func baseNeg2(n int) string {
   res := ""
   if n == 0 {
      return "0"
   }
   for n != 0 {
      if n%2 == 0 { // 偶数
         res = "0" + res
         n = n / -2
      } else { // 奇数
         res = "1" + res
         n = (n - 1) / -2
      }
   }
   return res
}

2、遍历；时间复杂度O(log(n))，空间复杂度O(log(n))

func baseNeg2(n int) string {
   res := ""
   if n == 0 {
      return "0"
   }
   for n != 0 {
      if n%2 == 0 { // 偶数
         res = "0" + res
      } else { // 奇数
         res = "1" + res
      }
      // 3 = 111
      // -2做法：-1 / -2 = 0
      // 位做法：-(-1 >> 1) = 1
      n = -(n >> 1) // 除以-2
   }
   return res
}

总结

Medium题目，数学类题目，注意找到规律