又碰到一个很有意思的题目，拿过来纪录一下过程。
首先，我使用了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
