首页 > 试题广场 >

魔法数字

[编程题]魔法数字

热度指数：2411 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。
操作共有三种，如下：
1.在当前数字的基础上加一，如：4转化为5
2.在当前数字的基础上减一，如：4转化为3
3.将当前数字变成它的平方，如：4转化为16

返回最少需要的操作数。

示例1

输入

3,10

输出

备注:

算法知识视频讲解

C/C++

一个好听的名字

用BFS广度优先搜索，设置一个打标签的是否遍历过的数组，下标索引即为当前变化的数值，数组对应索引值为1表示，进入过队列，为0表示没有进入过队列。

对于三种操作，除了约束进入过的不可再进入以外，分别对应增加三个约束条件。当前为1时不再进行减操作，当前大于m时，不再进行加操作。当前大于45时，不再进行平方操作（这个是因为求解 t^2 - 1000 < 1000 - t，这个方程式求解而来，实际上也就是，当大于等于45时，平方之后，比最大界限1000都要大上1000多，这个时候，哪怕是单纯的加法，都比它捡回来要步数少）。

代码如下所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    int solve(int n, int m) {
        // write code here
        //BFS的解法
        queue<int> que;
        int hased[2000];  //打表是不是已经存在了，（超过两千这个数字就已经没有意义了）
        int que_length = 0;
        int temp_num = 0;
        int step = 0;
        memset(hased, 0, sizeof(int)*2000); //全部置零
        que.push(n);
        hased[n] = 1;
        while (!que.empty())
        {
            que_length = que.size();
            for (int i = 0; i < que_length; i++)
            {
                temp_num = que.front();
                que.pop();
                if (temp_num == m)
                    return step;
                if (temp_num > 1 && hased[temp_num - 1] == 0)  //当前数字为1而且没有进入过
                {
                    que.push(temp_num - 1);
                    hased[temp_num - 1] = 1;
                }
                if (temp_num < m && hased[temp_num + 1] == 0) //当前数字小于m，而且没有进入过
                {
                    que.push(temp_num + 1);
                    hased[temp_num + 1] = 1;
                }
                if (temp_num < 45 && hased[temp_num * temp_num] == 0) //当前数字小于45，才有平方的必要性
                {
                    que.push(temp_num * temp_num);
                    hased[temp_num * temp_num] = 1;
                }
            }
            step++;
        }
        return step;
    }
};

发表于 2021-01-21 11:31:50 回复(0)

专业打拆

import java.util.*;


public class Solution {
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
       // 处理特殊情况
        if(n>=m) return n-m;
       // 取与m平方根最近的整数
        int k=(int)Math.sqrt(m);
        if(m-k*k>(k+1)*(k+1)-m) k++;
        // 取m-n与n到k递归步数最小者
        return Math.min(m-n,solve(n,k)+1+Math.abs(m-k*k));
    }

发表于 2021-12-20 23:30:43 回复(0)

我会画小猪佩奇

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型表示牛牛的数字
* @param m int整型表示牛妹的数字
* @return int整型
*/
public int solve (int n, int m) {
// write code here
//牛牛n 牛妹m n转化为m
if(n>m){
return n-m;
}
if(n<m){
int a=nn(n);
int temp =1;
while(a<m){
a=nn(a);
temp++;
}
int[] aa={m-n,temp+a-m,temp-1+m-(int)Math.sqrt(a)};
Arrays.sort(aa);
return aa[0];
}
return 0;
}
int nn(int n){
return n*n;
}
}

发表于 2021-12-17 12:58:55 回复(0)

Java

宛安

import java.util.*;   public class Solution { public static void main(String[] args) {
        Solution solution = new Solution ();  System.out.println ("请输入牛牛的数字，例如：牛牛-3" );  int n = getInt ();  System.out.println ("请输入牛妹的数字，例如：牛妹-10" );  int m = getInt ();  solution.solve ( n,m );  } public static void solve (int n, int m) { // write code here  int sum = 0;  if (n < 2){
            n++;  sum++;  } while (n * n <= m){
            sum ++;  n = n * n;  } if ((n * n + n) / 2 >= m){
            sum = sum + m - n;  }else {
            sum = sum + n * n - m + 1;  }
        System.out.println (sum );  } private static int getInt() {
        Scanner sc = new Scanner(System.in);  return sc.nextInt();  }
}

发表于 2021-08-20 17:18:53 回复(0)

拉嘎布想吃天鹅肉

class Solution:
def solve(self , n , m ):
# write code here
def sqr(a):
for i in range(1,32):
if i**2<=a and (i+1)**2>a:
return i,a-i**2,(i+1)**2-a
break
def sol(n,m):
if n==1:
return 1+sol(2,m)
elif n>=m:
return n-m
elif m>n:
i,left,right=sqr(m)
sol1=m-n
sol2=sol(n,i)+left+1
sol3=sol(n,i+1)+right+1
return min(sol1,sol2,sol3)
return sol(n,m)

发表于 2021-08-05 22:11:56 回复(0)

Java

牛客857822105号

java学的不久，纯属瞎做居然通过了，最笨的方法了吧

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
        // write code here
        int x=0;
        if(n==1 && m!=1){
            n++;
            x++;
        }
        List<Integer>l1=new ArrayList<>();
        List<Integer>l2=new ArrayList<>();
        Set<Integer>set=new HashSet<>();
        l1.add(n);
        while(!l1.contains(m)){
            for(int i=0;i<l1.size();i++){
                if(l1.get(i)>m){
                    l2.add(l1.get(i)-1);
                }
                else if(l1.get(i)>44){
                    if(!set.contains(l1.get(i)+1)){
                        l2.add(l1.get(i)+1);
                        set.add(l1.get(i)+1);
                    }
                    if(!set.contains(l1.get(i)-1)){
                        l2.add(l1.get(i)-1);
                        set.add(l1.get(i)-1);
                    }
                }
                else{
                     if(!set.contains(l1.get(i)+1)){
                        l2.add(l1.get(i)+1);
                        set.add(l1.get(i)+1);
                    }
                    if(!set.contains(l1.get(i)-1)){
                        l2.add(l1.get(i)-1);
                        set.add(l1.get(i)-1);
                    }
                    if(!set.contains(l1.get(i)*l1.get(i))){
                        l2.add(l1.get(i)*l1.get(i));
                        set.add(l1.get(i)*l1.get(i));
                    }
                }
            }
            x++;
            l1.clear();
            l1.addAll(l2);
            l2.clear();
        }
        return x;
    }
}

发表于 2021-05-31 18:03:15 回复(0)

摘得星辰满袖行~

巨简洁的思路，

从n到m，要么直接（m-n）步

要么乘方到刚好小于m的地方，然后补上不够的

要么乘方到刚好大于m的地方，然后补上不够的

import math

class Solution:
def solve(self , n , m ):
def f(n,m):
if n==1 and m==2:
return 1
if n==1 and m==3:
return 2
if m<=n:
return n-m
sqm = math.floor(math.sqrt(m))
re1 = float('inf')
re2 = float('inf')
re =(m-sqm*sqm+1)
re1 = f(n,sqm) + re
re =((sqm+1)**2-m+1)
re2 = f(n,sqm+1)+re
return min(re1,re2,m-n)
return f(n,m)

发表于 2021-04-17 18:09:55 回复(0)

Python

spongebob7

import math
class Solution:
def solve(self , n , m ):
# write code here
step=0
if n==1:
n+=1
step+=1
if n>=m:
step += n-m
n=m
while abs(n-m)>abs(n-int(round(math.sqrt(m)))) and m>3:
step+=abs(m-pow(int(round(math.sqrt(m))),2))+1
m = int(round(math.sqrt(m)))
while n!=m:
if n>=m:
step += n-m
n=m
else:
if n*n<m:
n*=n
step+=1
else:
if n*n-m>=m-n:
step+=m-n
n = m
else:
step+=(n*n-m)+1
n=m
return step

发表于 2021-03-17 20:38:33 回复(0)

起名困难户啊啊

安卓讨论一下

发表于 2021-01-15 16:31:15 回复(0)

就是这么随意

发表于 2021-01-15 16:30:31 回复(0)

Java

一级**人

相对大佬的代码来说，我的代码十分笨拙。

我的想法是这样：从m开始，一直取他的平方根，然后一直补差数。

代码可能有很多累赘的地方，希望大家帮忙改正和补全。

    //count计数  public int count=0;
    public int solve (int n, int m) {
        if(n==1&&n==m) return count-1;
        if(n>=m) return n-m+count;
        int sq=(int)Math.sqrt(m);
        int a=m-sq*sq;
               //排除掉两数相近的情况
        if(Math.abs(m-sq*sq)>Math.abs(m-n))  return count+m-n;
               //判断加一好还是减一好
        if(sq==1||Math.abs(m-(sq+1)*(sq+1))>=Math.abs(m-sq*sq)) {
            count = count + a + 1;
            return solve(n, sq);
        }
        else {
            count=count+(sq+1)*(sq+1)-m+1;
            return solve(n,sq+1);
        }
    }

发表于 2020-08-14 17:03:25 回复(0)