题解 | #魔法数字#
魔法数字
http://www.nowcoder.com/practice/a0e34486102948a7b5e8b7b6d76cee96
魔法数字
描述：牛妹给牛牛写了一个数字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)
