给定两个-100到100的整数x和y,对x只能进行加1,减1,乘2操作,问最少对x进行几次操作能得到y?
例如:
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); String[] nums = s.split(","); int a = Integer.parseInt(nums[0]); int b = Integer.parseInt(nums[1]); int ans = solution(a,b); System.out.println(ans); } private static int solution(int a, int b){ int ans = 0; // 特殊值 if(a == 0 && b <= 0) return Math.abs(b); if(a == 0 && b > 0) return minOps(1,b) + 1; // a b 同号 if(a * b > 0){ a = Math.abs(a); b = Math.abs(b); if(a >= b) return a - b; // a < b else return minOps(a,b); } // a b 异号 // 如果 a 是负值,将 a 转换为正值 1,则 a * b > 0,调用自身得到结果。 if(a < 0) return ans - a + 1 + solution(1,b); // 如果 b 是负值,将 b 转换为正值 1。 return ans - b + 1 + solution(a,1); } private static int minOps(int a, int b){ if(b >= a && b <= (a << 1)) return Math.min(b - a,(a << 1) - b + 1); if((b & 1) == 1) return Math.min(minOps(a,(b + 1) >> 1), minOps(a,(b - 1) >> 1)) + 2; return minOps(a,b >> 1) + 1; } }
import java.util.Scanner; /** * @Author: coderjjp * @Date: 2020-05-09 18:27 * @Description: * @version: 1.0 */ public class Main { static Scanner sc = new Scanner(System.in); static String s[] = sc.next().split(","); static int x = Integer.valueOf(s[0]); static int y = Integer.valueOf(s[1]); static int min = Math.abs(x - y);//最小值的上界 public static void main(String[] args) { dfs(x, y, 0); System.out.println(min); } private static void dfs(int x, int y, int count) { if (count == min) return; if (x == y){ min = count; return; } dfs(x + 1, y, count + 1); dfs(x - 1, y, count + 1); dfs(x * 2, y, count + 1); } }