蓝桥杯—最少操作数

2026/4/25 20:52:16 来源：https://blog.csdn.net/Vaclee/article/details/146506219 浏览: 次关键词：蓝桥杯—最少操作数

一.题目

分析:每次可以进行三次操作，求在n步操作后可以达到目标数的最小n，和最短路径问题相似，分层遍历加记忆化搜索防止时间复杂度过高，还需要减枝操作

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Scanner;public class Text10 {public static int sum = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);long x = scan.nextLong();int k = scan.nextInt();Long n = x;System.out.println(bfs(n,k));scan.close();}public static int bfs(Long n,int k){Queue<Long> queue = new LinkedList<>();Set<Long> visted = new HashSet<>();//记录数组queue.add(n);//存入初始值Long res,tmp;while(!queue.isEmpty()){int cnt = queue.size();for(int i = 0;i<cnt;i++)//分层处理{res = queue.poll();if(res==k)return sum;if(res>k){queue.add(res - 1);if(res-1==k)    return sum + 1;continue;}Long[] arr = {res + 1,res - 1,res * 2};for(Long x:arr){if(x==k) return sum + 1;if(k>0&&!visted.contains(x)){queue.add(x);visted.add(x);}}}sum++;//每一层sum+1}return -1;}
}