题目

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

翻转 n 的二进制表示中最右侧位（第 0 位）。

如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：输入：n = 0 输出：0

示例 2：输入：n = 3 输出：2

解释：3 的二进制表示为 "11"

"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。

"01" -> "00" ，执行的是第 1 种操作。

示例 3：输入：n = 6 输出：4

解释：6 的二进制表示为 "110".

"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。

"010" -> "011" ，执行的是第 1 种操作。

"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。

"001" -> "000" ，执行的是第 1 种操作。

示例 4：输入：n = 9 输出：14

示例 5：输入：n = 333 输出：393

提示：0 <= n <= 109

解题思路分析

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

func minimumOneBitOperations(n int) int {
   // 依次将高位的1翻转为0
   // 操作2：00..110000..00 => 00..010000..00
   // 操作2+操作1：00..010000..00 => 00..011000..00
   // 操作2：00..011000..00 => 00..001000..00
   res := 0
   if n == 0 {
      return 0
   }
   for i := 0; (1 << i) <= n; i++ {
      if (1< 0 { // 第i位>0
         total := 1<<(1+i) - 1 // 把(1+i)位数变为100..00的次数
         res = total - res     // 交替加减
      }
   }
   return res
}

2、格雷码；时间复杂度O(log(n))，空间复杂度O(1)

func minimumOneBitOperations(n int) int {
   // 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同
   // 则称这种编码为格雷码（Gray Code）
   res := 0
   for n > 0 {
      res = res ^ n
      n = n / 2
   }
   return res
}

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

func minimumOneBitOperations(n int) int {
   // 依次将高位的1翻转为0
   // 操作2：00..110000..00 => 00..010000..00
   // 操作2+操作1：00..010000..00 => 00..011000..00
   // 操作2：00..011000..00 => 00..001000..00
   res := 0
   if n == 0 {
      return 0
   }
   length := bits.Len(uint(n))
   flag := 1
   for i := 0; (1 << i) <= n; i++ {
      if (1<<(length-1-i))&n > 0 { // 第length-1-i位>0{
         total := 1<<(length-i) - 1
         res = res + total*flag
         flag = -1 * flag
      }
   }
   return res
}

总结

Hard题目，分析问题找到规律，使用贪心思想，依次处理最高位的1变为0；