C ++中的整数替换
假设我们有一个正整数n，我们可以按照以下步骤进行这些操作-
如果n为偶数，则将n替换为n/2。
如果n为奇数，则可以将n替换为n+1或n-1。
我们必须找到n变为1所需的最小替换数？
因此，如果数字为7，则答案将为4，例如7→8→4→2→1或7→6→3→2→1
为了解决这个问题，我们将遵循以下步骤-
ret：=0，n：=x
当n>1时
如果n为3或n/2为偶数，则将n减1，否则将n加1
如果n是偶数，则c：=n/2
否则当n为偶数时
增加ret1
返回ret。
范例（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int bitCount(int x){
int ret = 0;
while(x){
ret++;
x >>= 1;
}
return ret;
}
int integerReplacement(int x) {
int ret = 0;
lli n = x;
while(n > 1){
if(n % 2 == 0){
n >>= 1;
}
else if(n & 1){
if(n == 3 || (((n >> 1) & 1 )== 0)){
n--;
} else {
n++;
}
}
ret++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.integerReplacement(7));
}输入值
7
输出结果
4