题目：
一天，牛妹找牛牛做一个游戏，牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。
操作共有三种，如下：
1.在当前数字的基础上加一，如：4转化为5
2.在当前数字的基础上减一，如：4转化为3
3.将当前数字变成它的平方，如：4转化为16
你能帮牛牛解决这个问题吗?
给定n,m,分别表示牛牛和牛妹的数字。
分析：
我自己的解决策略：
使用两个集合分别表示当前元素集和下一次的元素集，然后交叉使用。当元素集中出现m元素时终止计算。
本质上属于穷举策略，并且会进行过多的重复计算，导致时间复杂度不满足题目要求。
code：
1 /** 2 * 解决策略：使用当两个集合 3 * 集合1:存放上一步运算出的元素 4 * 集合2:存放集合1运算出的元素 5 * 两个集合交替使用，当运算出m时终止。 6 * 本质上属于穷举策略，且会进行大量的重复运算。 7 * 8 *v1版本：运行时超时 9 * @param n 10 * @param m 11 * @return 12 */ 13 public static int solve (int n, int m) { 14 // write code here 15 Set<Integer>[] sets = new Set[2]; 16 sets[0] = new HashSet<>(); 17 sets[1] = new HashSet<>(); 18 int count=0; 19 int i,j; 20 sets[0].add(n); 21 boolean flag = false; 22 23 while(!flag) { 24 i = count % 2; 25 j = (count + 1) % 2; 26 Iterator<Integer> iterators = sets[i].iterator(); 27 while (!flag && iterators.hasNext()) { 28 Integer v = iterators.next(); 29 int v1 = v + 1; 30 int v2 = v - 1; 31 int v3 = v * v; 32 if (v1 == m || v1 == m || v3 == m) { 33 flag = true; 34 } else { 35 sets[j].add(v1); 36 sets[j].add(v2); 37 sets[j].add(v3); 38 } 39 } 40 sets[i].clear(); 41 count++; 42 } 43 return count; 44 }
分析的大佬的代码：
使用递归策略，逐步缩小问题。
1、当m<=n，直接结束，返回n-m。
2、当m>n。开始递归。
对m开平方，且自动向下取整获得k。
1.分别获得m与k平方的差值v1和m与k+1的平方的差值v2。
2.比较v1和v2,如果v1>v2则k自增。然后将确定的k作为下一次迭代的m。
code:
/** * 分析的别人的代码： * * 返回最后要输出的答案 * @param n int整型 表示牛牛的数字 * @param m int整型 表示牛妹的数字 * @return int整型 * 策略解读： * 1、m<=n * result = n-m * 2、m>n * m开平方，自动向下取整得到k * 1.计算m与k平方的差值v1 * 2.计算m与k+1平方的差值v2 * 差值采用加或减的策略 * 3、比较v1和v2，确定k的真正取值。将k作为新的m进行迭代运算。 * * */ public static int solve (int n, int m) { // write code here if (m <= n) return n - m; int k = (int) Math.sqrt((double) m); if (m - k * k > (k + 1) * (k + 1) - m) k++;//如果k平方与m的差值大于k+1平方与m的差值，则迭代计算n,k+1的操作数 return Math.min(m - n, solve(n, k) + 1 + Math.abs(m - k * k)); //1表示k的平方操作 }