397. Integer Replacement多种方法比较

又碰到一个很有意思的题目，拿过来纪录一下过程。
首先，我使用了Dynamic Programming的方法：

class Solution {
public:
//此题设置“全局变量”vector<int> result;会导致run code和submit的时候结果不一致
//采用DP递推的方法，当数比较大的时候（百万，千万）会造成内存不够
    int integerReplacement(int n) {
        if( n <= 0) return 0;
        if(n == 2147483647) return 32; 
        vector<int> result(n+1,0);
        result[0] = result[1] = 0;
        result[2] = 1;
        for(int i = 2; i <= n; i++)
        {
            if(i%2 == 0) result[i] = result[i >> 1] + 1;
            else if(i%2 == 1) 
            {
                int a = result[(i-1) >> 1];
                int b = result[(i+1) >> 1];
                result[i] = a < b ? (a+2) : (b+2);
            }
        }
        return result[n];
    }
};

当n达到10000000的时候，会报“Memory Limit Exceeded”错误，也就是爆内存了。当然，数比较小的时候是可以的。

然后，又考虑普通的递归方案：

class Solution {
public:
//此题设置“全局变量”vector<int> result;会导致run code和submit的时候结果不一致
//采用DP递推的方法，当数比较大的时候（百万，千万级别的时候），会造成内存不够：Memory Limit Error
//采用递归的这种方式倒是可以
//考虑最大值2147483647
    int integerReplacement(int n) {
        if( n <= 1) return 0;
        if(n == INT_MAX) return 32;
        if(n%2 == 0) return integerReplacement(n>>1) + 1;
        else return min(integerReplacement(n+1)+1, integerReplacement(n-1)+1);       
  ｝    
};

酱紫，是可以AC的。

然后，看到讨论区的一个答案：

class Solution 
{
    int res = 0;
public:
    int integerReplacement(int n) 
    {
        if (n == 1)
            return res;
        if (n == 3)
        {
            res += 2;
            return res;
        }
        if (n == INT_MAX)
            return 32;
        
        res ++;
        if (n & 1)
            if ((n + 1) % 4 == 0)
                integerReplacement(n + 1);
            else
                integerReplacement(n - 1);
        else
            integerReplacement(n / 2);
            
        return res;
    }
};

然后又稍微思考了一下，这里面的原因，我觉得，从二进制的思路考虑，能够让n尽快的变成1的原因是，让n的二进制尾数中的连续的1尽快的变成0，给出如下方案：

class Solution 
{
    public:
     int integerReplacement(int n) {
        if (n <= 1) {
            return 0;
        } else if (n == INT_MAX) {
            return 32;
        }
        if(n == 3)  return 2; //后期添加即可。
        if (n & 1) {
            return (numTrailingOnes(n) > 1) ? (integerReplacement(n + 1)+1) : (integerReplacement(n - 1)+1);
        }
        else {
            return integerReplacement(n >> 1) + 1;
        }
    }

    int numTrailingOnes(int num) {
        int shift = 0;
        while (((num >> shift) & 1)) {
            shift++;
        }
        cout << shift;
        return shift;
    }
};

哈哈， 居然是Wrong Answer, 原来是忽略了n==3的情况。OK