题解 | #魔法数字#

题目链接

魔法数字

题目描述

牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。 操作共有三种，如下：

1. 在当前数字的基础上加一，如：4转化为5

2. 在当前数字的基础上减一，如：4转化为3

3. 将当前数字变成它的平方，如：4转化为16

返回最少需要的操作数。

示例1

输入

3,10

输出

2

示例2

输入

1,10

输出

4

示例3

输入

24,500

输出

19

解题思路

本题实质上是简单递归，但剪枝过程比较复杂，如果不剪枝，一定会超时。

单单对n去判定效率是不够的（毕竟爱情是双向奔赴），所以我们要让m也靠近n。

let m1 = Math.floor(Math.sqrt(m));
let m2 = m1 + 1;
let sub1 = m > n ? m - n : n - m;
let sub2 = m1 > n ? m1 - n : n - m1;
sub2 += m - m1 * m1;
let sub3 = m2 > n ? m2 - n : n - m2;
sub3 += m2 * m2 - m;

这一段的意思，是寻找m的算术平方根，其中m1*m1<m，m2*m2>m，且m1+1=m2。分别对m,m1,m2进行判断，看n能更快地“奔赴”哪一方。

当然，用m1和m2是有代价的——那就是|m-m1^2|（或|m-m2^2|），就是它们的平方与m之间的差距。

这一思想还是很好理解的，将测试数据代入并思考即可理解。

于是，n只会+1或者-1，而m只会取平方根，取平方根取整后再平方的值与m的差距为n的步长。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 表示牛牛的数字
 * @param m int整型 表示牛妹的数字
 * @return int整型
 */
function solve( n ,  m ) {
    // write code here
        if (m <= n)
        return n - m;
    else {
        let min = m - n;
        let find = (n, m, step) => {
            if (step > min)
                return;
            if (n == m) {
                if (step < min) {
                    min = step;
                }
                return;
            }
            let m1 = Math.floor(Math.sqrt(m));
            let m2 = m1 + 1;
            let sub1 = m > n ? m - n : n - m;
            let sub2 = m1 > n ? m1 - n : n - m1;
            sub2 += m - m1 * m1;
            let sub3 = m2 > n ? m2 - n : n - m2;
            sub3 += m2 * m2 - m;
            if (sub2 < sub1 && sub2 < sub3 && n != 1) {
                find(n, m1, step + 1 + m - m1 * m1);
            } else if (sub3 < sub1 && sub3 <= sub2 && n != 1) {
                find(n, m2, step + 1 + m2 * m2 - m);
            } else {
                if (n < m)
                    find(n + 1, m, step + 1);
                else
                    find(n - 1, m, step + 1);
            }
        }
        find(n, m, 0);
        return min;
    }
}
module.exports = {
    solve : solve
};