题解 | #魔法数字#

题意整理

有n和m两个数字。
并且约定三种操作，其一是将n加一，其二是将n减一，其三是将n变为自己的平方数。
求至少需要操作n多少次，能将其变为m。

方法一（BFS）

1.解题思路

首先进行特殊情况的判断，如果n和m都是1，直接返回0；如果n大于m，只能执行减一操作，直接返回n-m。
然后初始化一个队列和set集合，队列用于存储每一次n的值，和已经所走的步数step，set集合保证不走重复的路。
每一次都判断队首元素的num值是否为m，如果是，则找到了目标路径，返回step，如果不是，则分情况将三种操作对应的分支入队。由于加一操作和平方操作总会使num变大，所以在num小于目标值m时，才执行对应操作。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
        //特殊情况判断
        if(n==1&&m==1) return 0;
        if(n>=m){
            return n-m;
        }
        //初始化队列和set集合
        LinkedList<int[]> queue=new LinkedList<>();
        Set<Integer> set=new HashSet<>();
        queue.offer(new int[]{n,0});
        set.add(n);
        while(!queue.isEmpty()){
            int[] cur=queue.poll();
            int num=cur[0];
            int step=cur[1];
            //如果数字num变为m，则返回对应步数
            if(num==m){
                return step;
            }
            //如果set集合没出现num-1，则将num减一加入队列
            if(!set.contains(num-1)){
                set.add(num-1);
                queue.offer(new int[]{num-1,step+1});
            }
            //如果num小于m并且set集合没出现num+1，则将num加一加入队列
            if(num<m&&!set.contains(num+1)){
                set.add(num+1);
                queue.offer(new int[]{num+1,step+1});
            }
            //如果num小于m并且set集合没出现num*num，则将num*num加入队列
            if(num<m&&!set.contains(num*num)){
                set.add(num*num);
                queue.offer(new int[]{num*num,step+1});
            }
        }
        return -1;
    }
}

3.复杂度分析

时间复杂度：最坏情况下，全部执行加一操作，所以时间复杂度是 $O(m-n)$ 。
空间复杂度：最坏情况下，需要额外大小为m-n的队列和set集合，所以空间复杂度是 $O(m-n)$ 。

方法二（递归）

1.解题思路

递归终止条件：n大于等于m。
递归如何推进：若上一层递归在k（m的平方根）处，第一种选择是全部执行加一操作，第二种选择是先从k处平方到对应位置，再执行对应步数的加一或减一操作。比较两种选择哪个步数小，小的那个作为当前层步数。
每一层返回什么：返回对应层的步数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
        //如果n大于等于m，直接返回n-m
        if(n>=m) return n-m;
        //取当前m的平方根
        int k=(int)Math.sqrt(m);
        //判断平方根下取整和上取整哪一个离m更近，取较近的那一个
        if(m-k*k>(k+1)*(k+1)-m){
            k++;
        }
        /*有两种选择，一种是直接全部执行加一操作，另一种是从k处
        执行平方操作，再执行加一操作、或减一操作到m*/
        int choose1=m-n;
        int choose2=solve(n,k)+Math.abs(m-k*k)+1;
        return Math.min(choose1,choose2);
    }
}

3.复杂度分析

时间复杂度：最坏情况下，全部执行加一操作，所以时间复杂度是 $O(m-n)$ 。
空间复杂度：最坏情况下，需要深度为m-n的递归栈开销，所以空间复杂度是 $O(m-n)$ 。