题目描述

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

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

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

样例

输入：n = 0
输出：0

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

输入：n = 9
输出：14

输入：n = 333
输出：393

提示：

0 <= n <= 10^9

算法分析

记忆化搜索

少年未知的我还无知地用单向广搜和双向广搜去试探，结果以 133/308 和 152/308 惨败收场，下次遇到 10^9 级别的千万不能广搜hh

先通过个例子进行模拟过程，其中(1)、(2)分别表示 1 和 2 操作

1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 100 -> 101 -> 111 -> 110 -> 10 -> 11 -> 1 -> 0
     (1)     (2)     (1)     (2)     (1)     (2)     (1)     (2)    (1)    (2)    (1)    (2)   (1)   (2)  (1)

状态表示

f[xxxxx]表示xxxxx状态下变成0的最少操作次数，当后缀的状态确定时，比它大的数可以用到后缀的状态

状态转移

对于某个状态的某一个位是 1 时，xxx表示后面是什么数不知道
由上面模拟过程可知

1、11xxx 状态必须先到 11000 才能变成 0 ，因此有 11xxx -> 11000 -> 0 的过程，
   xxx 变成 000 需要 f[xxx] 的操作步数，
   因此f[11xxx] = f[xxx] + f[11000] = f[xxx] + f[1000] + 1，
   其中 1 表示从 11000 转 1000 的操作数

2、10xxx 状态必须先到 11000 才能变成 0 ，因此有 10xxx -> 11000 -> 0 的过程，
   xxx 变成 1000 需要 f[1000] - f[xxx] 操作步数，
   因此f[10xxx] = f[1000] - f[xxx] + f[11000] = f[1000] - f[xxx] + (f[1000] + 1) 
                = 2 * f[1000] - f[xxx] + 1，
   其中 1 表示从 11000 转 1000 的操作数

时间复杂度

不知道

Java 代码

class Solution {
    static HashMap<Integer, Integer> f = new HashMap<Integer, Integer>();
    static int dfs(int n)
    {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(f.containsKey(n)) return f.get(n);

        //找到最高的1的位置
        int k = -1;
        for(int i = 0;i < 32;i ++)
        {
            if(((n >> i) & 1) == 1) k = i;
        }

        int res = 0x3f3f3f3f;
        //观察最高位是1的下一位是0还是1，即判断是10xxx形式还是11xxx形式
        //若是10xxx形式：f[10xxx] = 2 * f[1000] - f[xxx] + 1
        if((n >> (k - 1) & 1) == 0)
        {
            res = 2 * dfs(1 << (k - 1)) - dfs(n - (1 << k)) + 1;
        }
        //若是11xxx形式，f[11xxx] = f[1000] + f[xxx] + 1
        else
        {
            res = dfs(1 << (k - 1)) + dfs(n - (1 << k) - (1 << (k - 1))) + 1;
        }

        f.put(n, res);

        return res;
    }
    public int minimumOneBitOperations(int n) {
        return dfs(n);
    }
}