369，整数替换

题目：

给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。

2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。

n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:

8

输出:

3

解释:

8 -> 4 -> 2 -> 1

示例 2:

输入:

7

输出:

4

解释:

7 -> 8 -> 4 -> 2 -> 1

或

7 -> 6 -> 3 -> 2 -> 1

01

答案

 1public int integerReplacement(int n) {
 2    if (n == Integer.MAX_VALUE)
 3        return 32;
 4    if (n <= 3)
 5        return n - 1;
 6    if (n % 2 == 0)
 7        return integerReplacement(n / 2) + 1;
 8    else
 9        return Math.min(integerReplacement(n - 1), integerReplacement(n + 1)) + 1;
10}

解析：

使用递归的方式很容易理解，当n是偶数的时候非常简单，我们只需要让n/2代替n即可。当n是奇数的时候，我们取n-1，和n+1计算次数的最小值即可。

其实这道题我们还可以换种思路。当n是奇数的时候，比如n=2k+1；无论是加1还是减1，结果都会是偶数，这个偶数有可能是4的倍数，有可能只是2的倍数(比如6,10等)。我们为了减少计算次数要尽可能多的往4的倍数上靠。所以当n%4=3的时候我们让n加1，当n%4=1的时候我们让n减1。当n等于3的时候是个例外，因为

3→2→1要比3→4→2→1替换次数少。所以我们计算的时候要把n=3的情况单独处理，我们来看下代码

02

另一种思路的递归写法

 1public int integerReplacement(int n) {
 2    if (n == Integer.MAX_VALUE)
 3        return 32;
 4    if (n <= 3)
 5        return n - 1;
 6    if (n % 2 == 0)
 7        return integerReplacement(n / 2) + 1;
 8    else
 9        return (n & 2) == 0 ? integerReplacement(n - 1) + 1 : integerReplacement(n + 1) + 1;
10}

03

另一种思路的非递归写法

 1public int integerReplacement(int n) {
 2    int count = 0;
 3    while (n > 1) {
 4        if ((n & 1) == 0) {//是偶数
 5            n /= 2;
 6        } else {//是奇数
 7            if (((n + 1) & 3) == 0 && n != 3) {//对3求余为0
 8                n = n / 2 + 1;
 9                count++;
10            } else {
11                n--;
12            }
13        }
14        count++;
15    }
16    return count;
17}

上面的3种实现方式其实都很简单，我们看到在判断n%4=3的时候有多种实现方式，我们还可以来列举一下（下面的n首先是奇数，判断才没问题），如果判断结果为true，那么n对4求余的结果就是3。

1，n%4==3;

2，(n+1)&3==0;

3，(n&2)!=0;

4，Integer.bitCount(n + 1) <= Integer.bitCount(n - 1)（Integer.bitCount是判断二进制中1的个数，也可以参照前面讲的364，位1的个数系列（一））

5，((n >>1) & 1) != 0