魔法数字

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

方法一

思路分析

    根据题目内容很容易得到当n>m时，只能进行减法操作将n转换为m，下面讨论n<m的情况如何执行最少的操作将n转换为m。
首先明确的是要想得到最少的操作数，n转换为m的操作有两种，一种为加法操作，另一种为平方操作，显然平方操作的执行会让n更靠近m，因此我们可以先计算根号m，得到的数如果大于n，则先将n进行加法操作，如果得到的数如果小于n，则先将n进行减法操作。具体的步骤如下：
  • 计算平方跟：sq_m=sqrt(double(m))
  • 比较m-sq_m*sq_m与abs(m-(sq_m+1)*(sq_m+1))两者的差别，决定是否需要先对sq_m进行加法操作
  • 目前操作数op=一个平方操作+平方后的加法操作或者减法操作
  • 接着递归计算n与sq_m之间需要的操作数
  • 递归结束条件：当n>=m时，只能进行减法操作将n转换为m

图解


核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    int solve(int n, int m) {
        // write code here
        if (n>=m) return n-m; //n大于m,进行减法操作得到最少的操作数
        else{
            int sq_m=sqrt(double(m));
            if(m-sq_m*sq_m>(sq_m+1)*(sq_m+1)-m) sq_m++;
            int s1=m-n;
            int op=1+abs(m-sq_m*sq_m);//一个平方操作+平方后的加法操作或者减法操作
            return min(s1,solve(n,sq_m)+op);
        }
    }
};
复杂度分析
  • 时间复杂度：最坏情况下，时间复杂度为$O(abs(m-n))$
  • 空间复杂度：递归需要使用栈，空间复杂度为$O(abs(m-n))$

方法二

思路分析

本题也可对其进行广度优先搜索，设置队列用于存储n经过操作成为的数，设置数组标记是否访问过，对于一个未访问过的数它可以做的操作为加法、减法、以及平方操作。当操作后的数为m时输出操作数。其中对加法、减法以及平方操作有如下说明：
当n大于m时进行减法操作
当n大于1时只能进行加法操作
当n不大于45时进行平方操作

核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    int solve(int n, int m) {
        // write code here
        if(n>=m) return n-m;
        queue<int> q;
        vector<int> s(2000,0);
        return operation(q,s,n,m);
    }
    
    int operation(queue<int> q,vector<int> s,int n,int m)//广度优先搜索的解法
    {
        int count = 0;//存储操作数
        q.push(n);
        s[n] = 1;
        while (!q.empty())
        {
            int q_length = q.size();
            for (int i = 0; i < q_length; i++)
            {
                int num = q.front();
                q.pop();
                if (num == m)
                    return count;
                if (num > 1 && s[num - 1] == 0)  
                {
                    q.push(num - 1);//当前数字大于1而且没有进入过
                    s[num - 1] = 1;
                }
                if (num < m && s[num + 1] == 0) 
                {
                    q.push(num + 1);//当前数字加一
                    s[num + 1] = 1;//当前数字标记
                }
                if (num < 45 && s[num * num] == 0) 
                {
                    q.push(num * num);//当前数字小于45，平方操作
                    s[num * num] = 1;
                }
            }
            count++;
        }
        return count;
    }
};
复杂度分析
  • 时间复杂度：循环对队列中的数进行操作，最坏情况下时间复杂度为O(abs(m-n))
  • 空间复杂度：设置队列以及标记数组，因此空间复杂度为O(n+m)