寫在前面

競賽沒做出來，雖然猜到是DP了，卻沒找到什么思路，直接放棄了，回來看看提示一點(diǎn)點(diǎn)找規(guī)律，還是挺有意思的一道題，然而看了大佬寫的格雷碼就5行。。。我人傻了

找規(guī)律

看了提示2讓我先找2^k對應(yīng)的值，于是就有了下面的找規(guī)律：

是不是一眼就能看出來？ dp[2] = dp[1] * 2 + 1、dp[4] = dp[2] * 2 + 1......
在找其他普適的規(guī)律之前，我們不防思考一下為什么會是 乘二加一。
我們以4和2為例，其轉(zhuǎn)化規(guī)律如下：

2和4轉(zhuǎn)化到0

接下來我們就可以找非2^k的數(shù)的規(guī)律了，還是觀察下邊的一串?dāng)?shù)：

4->5 與 4->6的轉(zhuǎn)換過程

• 如果遍歷到的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)];

動態(tài)規(guī)劃

由此，我們就可以得到動態(tài)規(guī)劃的代碼了，雖然看過數(shù)據(jù)規(guī)模就知道會超時，不過用來找思路還是很有用的。

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的數(shù)值
        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);
    }
}

分析：時間復(fù)雜度O(N)，但是10^9的數(shù)據(jù)起碼也需要O(logN)的時間復(fù)雜度，故TLE

使用TreeSet優(yōu)化DP

其實(shí)很容易發(fā)現(xiàn)，我們對于一個數(shù)n，需要解決的只有小于n的最大2的整次冪2^k，以及n % (2 ^ k)，而2^k可以提前計算出來，也就是只需要解決n % (2 ^ k)即可，其他的數(shù)據(jù)都是我們不需要的，所以可以考慮直接遞歸，每次都相當(dāng)于至少會去計算n / 2的值，這樣就可以將時間復(fù)雜度優(yōu)化到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的數(shù)值
        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);
    }
}

使用位運(yùn)算優(yōu)化

這里感謝zhangyixing大佬給出的來自HashMap源碼中的位運(yùn)算方法。
通過這樣的位運(yùn)算，可以找到大于n的最小的那個2^k，然后右移一位就可以得到小于n的最大的2^k。這樣通過位運(yùn)算找目標(biāo)值可以比TreeSet快不少。

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

    public int minimumOneBitOperations(int n) {
        map.put(0, 0);
        int last2Powk = 1;//記錄上一個2^k的數(shù)值
        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原本最高位在內(nèi)的所有位置位1，而不影響更高的位(仍為0)，例如：00001001->00001111
        low++;//得到比n大的最小的(2^k)
        low >>= 1;//比n小的最大的(2^k)
        return helper(low) - helper(n % low);
    }
}

總結(jié)

本人菜雞一枚，也沒找到更加好的簡便的規(guī)律，如果有寫的不對的地方還請指出，感恩相遇~
另外這里附一下大佬的格雷碼代碼，真的想不到啊。。。

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