打開輪盤鎖問題分析總結(jié)，及進一步提問：請給出一組最小步數(shù)下的號碼序列組合

題目描述

???? 你有一個帶有四個圓形撥輪的轉(zhuǎn)盤鎖。每個撥輪都有10個數(shù)字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每個撥輪可以自由旋轉(zhuǎn)：例如把 ‘9’ 變?yōu)?‘0’，‘0’ 變?yōu)?‘9’ 。每次旋轉(zhuǎn)都只能旋轉(zhuǎn)一個撥輪的一位數(shù)字。
???? 鎖的初始數(shù)字為 ‘0000’ ，一個代表四個撥輪的數(shù)字的字符串。
???? 列表 deadends 包含了一組死亡數(shù)字，一旦撥輪的數(shù)字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉(zhuǎn)。
???? 字符串 target 代表可以解鎖的數(shù)字，你需要給出解鎖需要的最小旋轉(zhuǎn)次數(shù)，如果無論如何不能解鎖，返回 -1 。

進一步提問：請給出一組最小旋轉(zhuǎn)次數(shù)下的號碼序列組合

題目示例

示例1:

輸入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
輸出：6
解釋：
可能的移動序列為 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 這樣的序列是不能解鎖的，
因為當(dāng)撥動到 “0102” 時這個鎖就會被鎖定。

示例2:

輸入: deadends = [“8888”], target = “0009”
輸出：1
解釋：把最后一位反向旋轉(zhuǎn)一次即可 “0000” -> “0009”。

示例3:

輸入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
輸出：-1
解釋：無法旋轉(zhuǎn)到目標(biāo)數(shù)字且不被鎖定。

---

---

求解

???? 解決這個問題的一個常用方法是使用廣度優(yōu)先搜索（BFS）。廣度優(yōu)先搜索適合用于尋找最短路徑的問題。在這種情況下，我們可以將每個可能的狀態(tài)視為圖中的一個節(jié)點，相鄰狀態(tài)視為圖中的邊。通過 BFS，我們可以找到從初始狀態(tài) “0000” 到目標(biāo)狀態(tài)的最短路徑，同時避免所有的死亡數(shù)字狀態(tài)。

???? 要找出最少步數(shù)的密碼狀態(tài)組合，可以在廣度優(yōu)先搜索（BFS）過程中記錄路徑。在找到目標(biāo)狀態(tài)時，我們可以回溯路徑來確定最少步數(shù)的密碼狀態(tài)組合。

詳細步驟

1.初始化：

• 使用一個隊列來進行 BFS，初始狀態(tài)為 “0000”。
• 使用一個集合存儲死亡數(shù)字，以便快速查找。
• 使用一個集合存儲已訪問的狀態(tài)，以避免重復(fù)訪問。
• 使用一個 Map 記錄每個狀態(tài)的前驅(qū)狀態(tài)，以便在找到目標(biāo)狀態(tài)時回溯路徑。

2.BFS 過程：

• 每次從隊列中取出一個狀態(tài)，檢查它是否是目標(biāo)狀態(tài)。
• 對于當(dāng)前狀態(tài)的每一個位置，可以嘗試增加或減少一位數(shù)字，生成新的狀態(tài)。
• 如果生成的狀態(tài)不是死亡數(shù)字且未被訪問過，將其加入隊列、已訪問集合，并記錄前驅(qū)狀態(tài)。
• 繼續(xù)這個過程，直到找到目標(biāo)狀態(tài)或者隊列為空。

3.路徑回溯：

• 當(dāng)找到目標(biāo)狀態(tài)時，從目標(biāo)狀態(tài)開始，通過 Map 回溯到初始狀態(tài)，生成路徑。

代碼實現(xiàn)

/*** 根據(jù)記錄的密碼序列父子關(guān)系，回溯所有密碼序列* @param deadends 一組死亡數(shù)字* @param target 最末端的密碼序列* @return 正序的密碼序列數(shù)據(jù)（包括“0000”根節(jié)點）。* 			當(dāng)列表size不為0時，size-1 即為最小步數(shù)；* 			當(dāng)列表size為0時，表示：無論如何不能解鎖。*/
public List<String> openLock(String[] deadends, String target) {Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));if (deadSet.contains("0000")) {return Collections.emptyList();}//隊列，實現(xiàn)BFS廣度優(yōu)先遍歷Queue<String> queue = new LinkedList<>();//記錄當(dāng)前密碼序列的上一個密碼序列，即：記錄父節(jié)點關(guān)系，便于回溯所有密碼序列。Map<String, String> parent = new HashMap<>();//記錄已經(jīng)設(shè)置過的密碼序列，防止重復(fù)判斷陷入無限循環(huán)。Set<String> visited = new HashSet<>();queue.offer("0000");visited.add("0000");parent.put("0000", null);//根節(jié)點的父節(jié)點設(shè)置為空int steps = 0;while (!queue.isEmpty()) {int size = queue.size();//遍歷每一層節(jié)點for (int i = 0; i < size; i++) {String current = queue.poll();if (current.equals(target)) {//最小步數(shù)產(chǎn)生，即最短路徑或最小深度，回溯路徑return constructPath(parent, target);}//根據(jù)當(dāng)前密碼序列，計算產(chǎn)生新的密碼序列for (String next : getNextStates(current)) {if (!visited.contains(next) && !deadSet.contains(next)) {queue.offer(next);visited.add(next);parent.put(next, current);//記錄父節(jié)點}}}steps++; //記錄步數(shù)}return Collections.emptyList();
}/*** 根據(jù)記錄的密碼序列父子關(guān)系，回溯所有密碼序列* @param parent 父子序列關(guān)系Map* @param target 最末端的密碼序列* @return 正序的密碼序列數(shù)據(jù)（包括“0000”根節(jié)點）*/
private List<String> constructPath(Map<String, String> parent, String target) {List<String> path = new LinkedList<>();for (String at = target; at != null; at = parent.get(at)) {path.add(at);}Collections.reverse(path);return path;
}/*** 獲取當(dāng)前密碼序列的下一個狀態(tài)的所有序列數(shù)據(jù)* @param current 當(dāng)前密碼序列* @return 所有的下一個狀態(tài)序列*/
private List<String> getNextStates(String current) {List<String> nextStates = new ArrayList<>();char[] chars = current.toCharArray();for (int i = 0; i < 4; i++) {char original = chars[i];// 向前撥動密碼輪盤chars[i] = original == '9' ? '0' : (char) (original + 1);nextStates.add(new String(chars));// 向后撥動密碼輪盤chars[i] = original == '0' ? '9' : (char) (original - 1);nextStates.add(new String(chars));// 回復(fù)原來的號碼chars[i] = original;}return nextStates;
}

測試代碼

    String[] deadends = {"0201", "0101", "0102", "1212", "2002"};String target = "0202";
//    String[] deadends = {"8887", "8889", "8878", "8898", "8788", "8988","7888","9888"};
//    String target = "8888";
//    String[] deadends = {"8888"};
//    String target = "0009";List<String> path = openLock(deadends, target);if (path.isEmpty()) {System.out.println("無論如何不能解鎖！");} else {System.out.println("解鎖序列:");for (String state : path) {System.out.println(state);}}