深圳入户申请网站官网,学勇建站,河南网站建设yijuce,photoshop电脑版怎么下载打开轮盘锁问题分析总结#xff0c;及进一步提问#xff1a;请给出一组最小步数下的号码序列组合
题目描述 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字#xff1a; ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由…打开轮盘锁问题分析总结及进一步提问请给出一组最小步数下的号码序列组合
题目描述 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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 ListString openLock(String[] deadends, String target) {SetString deadSet new HashSet(Arrays.asList(deadends));if (deadSet.contains(0000)) {return Collections.emptyList();}//队列实现BFS广度优先遍历QueueString queue new LinkedList();//记录当前密码序列的上一个密码序列即记录父节点关系便于回溯所有密码序列。MapString, String parent new HashMap();//记录已经设置过的密码序列防止重复判断陷入无限循环。SetString 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 ListString constructPath(MapString, String parent, String target) {ListString 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 ListString getNextStates(String current) {ListString 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;ListString path openLock(deadends, target);if (path.isEmpty()) {System.out.println(无论如何不能解锁);} else {System.out.println(解锁序列:);for (String state : path) {System.out.println(state);}}
