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
给定一正整数n，对其进行如下操作：
1. 若n为偶数，则用n/2代替
2. 若n为奇数，则用n+1或者n-1代替
请问经过最少多少次操作才能使得n变为1？
思路
注意给定的n的范围，提交的结果表明n不超过INT_MAX，则可直接使用int类型处理
class Solution {
public:
int intReplace(int n,int k){
if(n==1) return k;
if(n%2){
int res1=intReplace(((n-1)>>1)+1,k+2);
int res2=intReplace(n-1,k+1);
return res1<res2?res1:res2;
}
else{
return intReplace(n>>1,k+1);
}
}
int integerReplacement(int n) {
return intReplace(n,0);
}
};
