397. Integer Replacement

描述:

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

这道题要求我们寻找一种最快的将给定数字变成1的路径，转换规则题中已经给出，感觉就是在观察中得出一条规律，即:

1.如果某个数的末尾是01，则-1会比较快

2.如果某个数末尾是11，则+1会比较快，但这里有一个特例，即3,3虽然以11结尾，但是却发现它如果+1反而会比较慢，所以我们将其作为特例考虑。

3.其余情况全部直接右移一位

为什么会得出这样的规律呢？因为要想最快的将一个数通过除以2的方式变成1，就要让其含有尽可能多的0，所以以01结尾的应该-1，以11结尾的应该+1(造成连续进位)。

还有一个边界条件，当给出的数为INT_MAX时，也就是二进制表示为32个1的那个数，此时如果判断其以11结尾之后，必然会+1，那么就会造成溢出，所以我们在最开始添加一个if判断进行过滤。 (个人感觉这是这道题唯一考察思维严密性的地方)

我主观上认为这道题没什么意思，或许是数学水平还不够吧，代码如下：

class Solution {
public:
    int integerReplacement(int n) {
        int count=0;
        if(n==INT_MAX)
            return 32;
        while(n!=1){
            if((n&1)==0)
                n=n>>1;
            else if(n==3||((n>>1)&1)==0)
                n--;
            else
                n++;
            count++;
        }
        return count;
    }
};