整数替换-c语言bfs算法
整数替换-c语言bfs算法
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。
示例 1：
输入：n = 8 输出：3 解释：8 -> 4 -> 2 -> 1
示例 2：
输入：n = 7 输出：4 解释：7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1
示例 3：
输入：n = 4 输出：2
算法实现如下：
int bfs(long long n,int *r,int num){
if(n==1){
printf("%d ",num);
return num;
}
if(n!=1){
if(n%2==0){
return bfs(n/2,r,num+1);
}
else{
long long a=bfs(n+1,r,num+1);
long long b=bfs(n-1,r,num+1);
if(a>b) return b;
else return a;
}
}
return 0;
}
int integerReplacement(int n){
int num=0;
int *r=(int *)malloc(sizeof(int));
int min;
min=bfs(n,r,num);
return min;
}
上一篇：
IDEA上Java项目控制台中文乱码