397. Integer Replacement --------M ！！！！~~~~~~

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

A:

思路很直接，就是 普通的  DP ， 然后每次看前面的计算了没有，做一下memorization.

然而，下面这个算法是错误的。   --------- 修改在后面

class Solution {
public:
    int integerReplacement(int n) {
        vector<int> V(n+1,-1);
        V[1] = 0;
        return helper(V, n);
    }
private:
    int helper(vector<int> & V, int n){
        if(n>=V.size())
            return (int)INT_MAX;
        if(V[n] >= 0)
            return V[n];
        else{
            if(n % 2 ==0){
                V[n] = 1 + helper(V, n/2);
            }else{
                V[n] = 1 + min(helper(V, n-1), helper(V, n+1));
            }
            return V[n];
        }
    }
};

--------------------错误的原因在于，我们不允许查看n后面的数字了。例如n+1

class Solution {
public:
    int integerReplacement(int n) {
        vector<int> V(n+2,-1);
        V[1] = 0;
        return helper(V, n);
    }
private:
    int helper(vector<int> & V, int n){
        if(n>=V.size())
            return (int)INT_MAX;
        if(V[n] >= 0)
            return V[n];
        else{
            if(n % 2 ==0){
                V[n] = 1 + helper(V, n/2);
            }else{
                V[n] = 1 + min(helper(V, n-1), helper(V, n+1));
            }
            return V[n];
        }
    }
};

然而  LTE

选择用bit manipulation

每次查看最后几个bit.  

class Solution {
public:
    int integerReplacement(int n) {
        int res = 0;
        while(n>1){
            if( n&1){
                // n+1,--> 相当于进位，同时消掉最后的几个1， 如果进位后，就多出了一位。 那就是额外成本。所以3是不进位
                // 否则，当最后最少3个1的时候，0b111 加一变成1000，总共变到1 ，需要4步。如果是>3, 则之前还有，所以总共
                if(n==3){
                    res+=1;
                    n = 1;
                }else if(n&2){ // n == xxxx11
                    n = n+1;
                }else{
                    n = n-1;
                }
                
            }else{
                n = n>>1;
            }
            ++res;
        }
        return res;
    }
};

然后， n == 2147483647  时，n+1 会 overflow.  最终改成了 long类型

class Solution {
public:
    int integerReplacement(int n) {
        int res = 0;
        long m = n;
        while(m>1){
            if( m&1){
                // n+1,--> 相当于进位，同时消掉最后的几个1， 如果进位后，就多出了一位。 那就是额外成本。所以3是不进位
                // 否则，当最后最少3个1的时候，0b111 加一变成1000，总共变到1 ，需要4步。如果是>3, 则之前还有，所以总共
                if(m==3){
                    res+=1;
                    m = 1;
                }else if( m & 2){ // m == xxxx11
                    m = m+1;
                }else{
                    m = m-1;
                }
                
            }else{
                m = m>>1;
            }
            ++res;
        }
        return res;
    }
};