写在前面

竞赛没做出来，虽然猜到是DP了，却没找到什么思路，直接放弃了，回来看看提示一点点找规律，还是挺有意思的一道题，然而看了大佬写的格雷码就5行。。。我人傻了

找规律

看了提示2让我先找2^k对应的值，于是就有了下面的找规律：

是不是一眼就能看出来？ dp[2] = dp[1] * 2 + 1、dp[4] = dp[2] * 2 + 1......
在找其他普适的规律之前，我们不防思考一下为什么会是 乘二加一。
我们以4和2为例，其转化规律如下：

2和4转化到0

通过观察上图两种不同颜色的转换流程，当4转换为2时，后续过程就与2转换到0一致了，而从4转换到2的过程，只看后两位恰好相当于从0转换到2，在多一步转换最高位的1，所以对应的dp[4] = dp[0->2] + dp[2->0] + 1也就是上述的递推公式了。

接下来我们就可以找非2^k的数的规律了，还是观察下边的一串数：

为什么我还要将2^k对应的数据标识出来呢？其实可以看到，1、2、4、8、16均是相同位数之中数最大的。再参考上述4转换的过程，4会依次转换为5、7、6，然后变为2。也就是说，如果能计算出从4->5或者4->6的转换步数，那么每个位置的步数也就迎刃而解了。

4->5 与 4->6的转换过程

只看后两位的话可以发现，4->5的转换过程就是0->1的转换过程；4->6的转换过程就是0->2的转换过程。也就是dp[5] = dp[4] - dp[5 % 4]; dp[6] = dp[4] - dp[6 % 4];
那么总的规律也就找到了：

• 如果遍历到的i是2的k次幂 2^k，那么dp[i] = dp[2^(k-1)] * 2 + 1;
• 如果遍历到的i不是2的k次幂，且小于他的最大的2的整次幂为2^k，那么dp[i] = dp[2^k] - dp[i %(2^k)];

动态规划

由此，我们就可以得到动态规划的代码了，虽然看过数据规模就知道会超时，不过用来找思路还是很有用的。

class Solution {
    public int minimumOneBitOperations(int n) {
        if(n == 0) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1,1);
        int last2Powk = 1;//记录上一个2^k的数值
        for(int i = 2; i <= n; i++){
            if(i == last2Powk * 2){
                map.put(i, map.get(last2Powk) * 2 + 1);
                last2Powk = i;
            }else{
                map.put(i, map.get(last2Powk) - map.get(i % last2Powk));
            }
        }
        return map.get(n);
    }
}

分析：时间复杂度O(N)，但是10^9的数据起码也需要O(logN)的时间复杂度，故TLE

使用TreeSet优化DP

其实很容易发现，我们对于一个数n，需要解决的只有小于n的最大2的整次幂2^k，以及n % (2 ^ k)，而2^k可以提前计算出来，也就是只需要解决n % (2 ^ k)即可，其他的数据都是我们不需要的，所以可以考虑直接递归，每次都相当于至少会去计算n / 2的值，这样就可以将时间复杂度优化到O(logN)了。

class Solution {
    
    HashMap<Integer, Integer> map = new HashMap<>();
    TreeSet<Integer> set = new TreeSet<>();

    public int minimumOneBitOperations(int n) {
        map.put(0, 0);
        int last2Powk = 1;//记录上一个2^k的数值
        while(last2Powk <= n){
            map.put(last2Powk, map.get(last2Powk / 2) * 2 + 1);
            set.add(last2Powk);
            last2Powk *= 2;
        }
        return helper(n);
    }

    public int helper(int n){
        if(map.containsKey(n)) return map.get(n);

        int low = set.floor(n);//找到小于n的最大的(2^k)
        return helper(low) - helper(n % low);
    }
}

使用位运算优化

这里感谢zhangyixing大佬给出的来自HashMap源码中的位运算方法。
通过这样的位运算，可以找到大于n的最小的那个2^k，然后右移一位就可以得到小于n的最大的2^k。这样通过位运算找目标值可以比TreeSet快不少。

class Solution {
    
    HashMap<Integer, Integer> map = new HashMap<>();

    public int minimumOneBitOperations(int n) {
        map.put(0, 0);
        int last2Powk = 1;//记录上一个2^k的数值
        while(last2Powk <= n){
            map.put(last2Powk, map.get(last2Powk / 2) * 2 + 1);
            last2Powk *= 2;
        }
        return helper(n);
    }

    public int helper(int n){
        if(map.containsKey(n)) return map.get(n);

        int low = n;//找到小于n的最大的2的整次幂
        low |= low >> 1;
        low |= low >> 2;
        low |= low >> 4;
        low |= low >> 8;
        low |= low >> 16;//这5步将n原本最高位在内的所有位置位1，而不影响更高的位(仍为0)，例如：00001001->00001111
        low++;//得到比n大的最小的(2^k)
        low >>= 1;//比n小的最大的(2^k)
        return helper(low) - helper(n % low);
    }
}

总结

本人菜鸡一枚，也没找到更加好的简便的规律，如果有写的不对的地方还请指出，感恩相遇~
另外这里附一下大佬的格雷码代码，真的想不到啊。。。

class Solution {
    public int minimumOneBitOperations(int n) {
        int res = 0;
        while(n != 0){
            res ^= n;
            n >>= 1;
        }
        return res;
    }
}