一.題目

分析:每次可以進行三次操作，求在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;}
}

二.總結

bfs算法求最短路徑問題時，需要記憶化搜搜

原因

1.迷宮:防止后來的路徑覆蓋最短路徑

2.本題:防止重復計算已經計算過的路徑，減少時間復雜度

本題需要大量減枝，因為每次操作變化小，這也是為什么不能用dfs的原因，dfs算法也可以求解，不過時間復雜度很高，遞歸太深入了，比如說1到10000會進行9999次遞歸，時間復雜度是指數級的

3.只有答案需要返回操作步驟數時才需要分層處理，比如求最短路徑就不需要分層處理，只需要返回路徑就可以，如果是需要知道走了幾步，那就需要分層處理記錄

三.錯誤總結

1.時間復雜度過高

沒有減枝,當當前數大于k時，只需要-1操作就行，沒有設置記憶數組，已經遍歷過的結果不需要再次遍歷，使用Hashset是因為它是哈希表結構，查詢快效率高

2.沒有思考清楚什么情況會返回-1

沒有返回-1的情況，題目陷阱

3.返回值錯誤

eg:

在這里如果沒有檢查res就可能會發生錯誤

假如說在第n層res-1的結果等于k，那么res-1就存儲在第85層，如果在這個位置前有一個值+1可以等于k那么返回來sum+1在86層，就導致結果錯誤，所以每次操作都需要立即檢查，沒檢查就會導致多一層搜索