给定一个正整数 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
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的情况单独处理,我们来看下代码
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}
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
联系客服