C语言 | Leetcode C语言题解之第397题整数替换
题目：
题解：
//第一种动态规划:超时
// class Solution {
// public:
// int integerReplacement(int n) {
// vector<int>dp(n+1,0);
// dp[1]=0;
// for(int i=2;i<=n;i++){
// if(i%2==0){
// dp[i]=dp[i/2]+1;
// }
// else{
// dp[i]=min(dp[i-1],dp[(i+1)/2]+1)+1;
// }
// }
// return dp[n];
// }
// };
//第二种:递归。这里需要注意一下就是int数据溢出的问题。
class Solution{
public:
long Solve(long num){
if(num==1){
return 0;
}
if(num%2==0){
return Solve(num/2)+1;
}
else{
return (long)min(Solve(num-1),Solve(num+1))+1;
}
}
int integerReplacement(int n){
long num=n;
return Solve(num);
}
};