打开轮盘锁问题（LeetCode）的分析总结及进一步提问

打开轮盘锁问题分析总结，及进一步提问：请给出一组最小步数下的号码序列组合

题目描述

     你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
     锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
     列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
     字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

进一步提问：请给出一组最小旋转次数下的号码序列组合

题目示例

示例1:

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。

示例2:

输入: deadends = [“8888”], target = “0009”
输出：1
解释：把最后一位反向旋转一次即可 “0000” -> “0009”。

示例3:

输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出：-1
解释：无法旋转到目标数字且不被锁定。

---

---

求解

     解决这个问题的一个常用方法是使用广度优先搜索（BFS）。广度优先搜索适合用于寻找最短路径的问题。在这种情况下，我们可以将每个可能的状态视为图中的一个节点，相邻状态视为图中的边。通过 BFS，我们可以找到从初始状态 “0000” 到目标状态的最短路径，同时避免所有的死亡数字状态。

     要找出最少步数的密码状态组合，可以在广度优先搜索（BFS）过程中记录路径。在找到目标状态时，我们可以回溯路径来确定最少步数的密码状态组合。

详细步骤

1.初始化：

• 使用一个队列来进行 BFS，初始状态为 “0000”。
• 使用一个集合存储死亡数字，以便快速查找。
• 使用一个集合存储已访问的状态，以避免重复访问。
• 使用一个 Map 记录每个状态的前驱状态，以便在找到目标状态时回溯路径。

2.BFS 过程：

• 每次从队列中取出一个状态，检查它是否是目标状态。
• 对于当前状态的每一个位置，可以尝试增加或减少一位数字，生成新的状态。
• 如果生成的状态不是死亡数字且未被访问过，将其加入队列、已访问集合，并记录前驱状态。
• 继续这个过程，直到找到目标状态或者队列为空。

3.路径回溯：

• 当找到目标状态时，从目标状态开始，通过 Map 回溯到初始状态，生成路径。

代码实现

/*** 根据记录的密码序列父子关系，回溯所有密码序列* @param deadends 一组死亡数字* @param target 最末端的密码序列* @return 正序的密码序列数据（包括“0000”根节点）。* 			当列表size不为0时，size-1 即为最小步数；* 			当列表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();}//队列，实现BFS广度优先遍历Queue<String> queue = new LinkedList<>();//记录当前密码序列的上一个密码序列，即：记录父节点关系，便于回溯所有密码序列。Map<String, String> parent = new HashMap<>();//记录已经设置过的密码序列，防止重复判断陷入无限循环。Set<String> visited = new HashSet<>();queue.offer("0000");visited.add("0000");parent.put("0000", null);//根节点的父节点设置为空int steps = 0;while (!queue.isEmpty()) {int size = queue.size();//遍历每一层节点for (int i = 0; i < size; i++) {String current = queue.poll();if (current.equals(target)) {//最小步数产生，即最短路径或最小深度，回溯路径return constructPath(parent, target);}//根据当前密码序列，计算产生新的密码序列for (String next : getNextStates(current)) {if (!visited.contains(next) && !deadSet.contains(next)) {queue.offer(next);visited.add(next);parent.put(next, current);//记录父节点}}}steps++; //记录步数}return Collections.emptyList();
}/*** 根据记录的密码序列父子关系，回溯所有密码序列* @param parent 父子序列关系Map* @param target 最末端的密码序列* @return 正序的密码序列数据（包括“0000”根节点）*/
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;
}/*** 获取当前密码序列的下一个状态的所有序列数据* @param current 当前密码序列* @return 所有的下一个状态序列*/
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));// 回复原来的号码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);}}