牛妹给牛牛写了一个数字n,然后又给自己写了一个数字m,她希望牛牛能执行最少的操作将他的数字转化成自己的。
操作共有三种,如下:
1.在当前数字的基础上加一,如:4转化为5
2.在当前数字的基础上减一,如:4转化为3
3.将当前数字变成它的平方,如:4转化为16
返回最少需要的操作数。
import java.util.*; public class Solution { public static void main(String[] args) { Solution solution = new Solution (); System.out.println ("请输入牛牛的数字,例如:牛牛-3" ); int n = getInt (); System.out.println ("请输入牛妹的数字,例如:牛妹-10" ); int m = getInt (); solution.solve ( n,m ); } public static void solve (int n, int m) { // write code here int sum = 0; if (n < 2){ n++; sum++; } while (n * n <= m){ sum ++; n = n * n; } if ((n * n + n) / 2 >= m){ sum = sum + m - n; }else { sum = sum + n * n - m + 1; } System.out.println (sum ); } private static int getInt() { Scanner sc = new Scanner(System.in); return sc.nextInt(); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 表示牛牛的数字 * @param m int整型 表示牛妹的数字 * @return int整型 */ public int solve (int n, int m) { // write code here int x=0; if(n==1 && m!=1){ n++; x++; } List<Integer>l1=new ArrayList<>(); List<Integer>l2=new ArrayList<>(); Set<Integer>set=new HashSet<>(); l1.add(n); while(!l1.contains(m)){ for(int i=0;i<l1.size();i++){ if(l1.get(i)>m){ l2.add(l1.get(i)-1); } else if(l1.get(i)>44){ if(!set.contains(l1.get(i)+1)){ l2.add(l1.get(i)+1); set.add(l1.get(i)+1); } if(!set.contains(l1.get(i)-1)){ l2.add(l1.get(i)-1); set.add(l1.get(i)-1); } } else{ if(!set.contains(l1.get(i)+1)){ l2.add(l1.get(i)+1); set.add(l1.get(i)+1); } if(!set.contains(l1.get(i)-1)){ l2.add(l1.get(i)-1); set.add(l1.get(i)-1); } if(!set.contains(l1.get(i)*l1.get(i))){ l2.add(l1.get(i)*l1.get(i)); set.add(l1.get(i)*l1.get(i)); } } } x++; l1.clear(); l1.addAll(l2); l2.clear(); } return x; } }
//count计数 public int count=0; public int solve (int n, int m) { if(n==1&&n==m) return count-1; if(n>=m) return n-m+count; int sq=(int)Math.sqrt(m); int a=m-sq*sq; //排除掉两数相近的情况 if(Math.abs(m-sq*sq)>Math.abs(m-n)) return count+m-n; //判断加一好还是减一好 if(sq==1||Math.abs(m-(sq+1)*(sq+1))>=Math.abs(m-sq*sq)) { count = count + a + 1; return solve(n, sq); } else { count=count+(sq+1)*(sq+1)-m+1; return solve(n,sq+1); } }