NC588 题解 | #魔法数字#

题意分析

• 将一个数字n，通过三种操作得到数字m，操作如下
  • 在当前数字的基础上加一，如：4转化为5
  • 在当前数字的基础上减一，如：4转化为3
  • 将当前数字变成它的平方，如：4转化为16

问最小的操作次数

思路分析

• 我们首先进行分析，如果过程中给出的$n>mn>m$n>m，那么我们就一定必须要执行减的操作才是最优的，没有必要执行加的操作和加倍的操作了。

解法一 BFS

• 这是一个很明显的$BFSBFS$BFS的题目.初始的状态是$(n,0)(n,0)$(n,0)，表示初始的位置和当前走的步数，然后我们每次可以进行扩展，如果当前的数字大于m，那么只能执行减的操作，如果小于m，那么可以执行平方和加1的操作，继续进行扩展即可。第一次到达m的状态就是最优的。

• 代码如下

  • 由n走到m，最多可能走$abs(n-m)abs(n-m)$abs(n−m)步，时间复杂度为$O\left(abs\right(n-m\left)\right)O(abs(n-m))$O(abs(n−m))
  • 过程中利用了队列和pair以及一个unordered_map进行处理，空间复杂度为$O\left(abs\right(n-m\left)\right)O(abs(n-m))$O(abs(n−m))

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    bool judge(int x){
        if(x<0||x>=2000) return false;
        return true;
    }
    int bfs(int x,int y){
        queue<pair<int,int> > q;
        // 先将初始的值放入队列里面进行拓展
        q.push(make_pair(x,0));
        // 标记这个数字是否被访问过
        unordered_map<int,bool> mp;
        mp[x]=true;
        while(!q.empty()){
        	// 取出队首的元素
            pair<int,int> p=q.front();
            q.pop();
            if(p.first==y){
                return p.second;
            }
            if(p.first<y){
                // 加1
                if(mp[p.first+1]==false&&judge(p.first+1)){
                    q.push(make_pair(p.first+1,p.second+1));
                    mp[p.first+1]=true;
                }
                // 平方
                if(mp[p.first*p.first]==false&&judge(p.first*p.first)){
                    q.push(make_pair(p.first*p.first,p.second+1));
                    mp[p.first*p.first]=true;
                }
            }
            // 减1操作
            if(mp[p.first-1]==false){
                q.push(make_pair(p.first-1,p.second+1));
                mp[p.first-1]=true;
            }
            
        }
        
        return 0;
    }
    int solve(int n, int m) {
        // write code here
        return bfs(n,m);
    }
};

解法二 递归写法

• 其实，如果我们直接利用递归的写法进行求解的话，那么大概率会爆栈，所以我们看能不能进行优化处理，我们观察到，如果进行平方之后还是少于目标位置，那么直接平方是最优的，如果当前的位置大于目标值，那么一直执行减1的操作。所以，我们递归的时候传递两个参数，一个是n，表示我们的初始值，另一个是m，表示我们的目标值。如果n>=m,那么直接返回n-m,否则,然后比较最接近目标值的平方数，将这一段作为新的状态继续进行递归，目标值到这个平方数的距离一定是只能一步一步走过去的。这样就减少了没必要的操作。

• 结合下图进行理解

• 代码如下
  • 每次都是开根号进行递归的，时间复杂度为$O\left(log\right(\mid n-m\mid )O(log(|n-m|)$O(log(∣n−m∣)
  • 过程中只用了少数几个变量，空间复杂度为$O\left(1\right)O(1)$O(1)

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;
        // 如果起点在终点的后面
        int k=sqrt(m);
        int tmp1=abs(k*k-m),tmp2=abs((k+1)*(k+1)-m);
        if(tmp1>tmp2){
            // 优先跳到k+1,然后跳到k+1的平方，然后再进行一步一步走
            return min(m-n,tmp2+solve(n,k+1)+1);
        }else{
            // 优先跳到k,然后跳到k的平方，然后再进行一步一步走
            return min(m-n,tmp1+solve(n,k)+1);
        }
    }
};