C++ 中的整数替换
c++server side programmingprogramming更新于 2025/6/27 2:52:17
假设我们有一个正整数 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 为偶数，则 c := n / 2
否则，当 n 为偶数时
如果 n 为 3 或 n/2 为偶数，则将 n 减 1，否则将 n 加 1
将 ret 加 1
return 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
