数据结构
网络
关系型数据库管理系统
操作系统
Java
微软 Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究用 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
while n > 1
如果 n 为偶数，则 c := n / 2
否则当 n 为偶数时
如果 n 为 3 或 n/2 为偶数，则将 n 减 1，否则将 n 加 1
将 ret 加 1
返回 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
更新于： 2020 年 5 月 2 日
581 次浏览
广告