您的位置:首页 > 新闻 > 会展 > 解开密码锁的最少次数

解开密码锁的最少次数

2024/11/8 15:53:54 来源:https://blog.csdn.net/qq_58023907/article/details/142183487  浏览:    关键词:解开密码锁的最少次数

题目

        一个密码锁由 4 个环形拨轮组成,每个拨轮都有 10 个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0''0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

        锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

        列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

        字符串 target 代表可以解锁的数字,请给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

解题

        第一步,我们不管所有的限制条件,不管 deadends 和 target 的限制,就思考一个问题:如果让你设计一个算法,穷举所有可能的密码组合,你将怎么做?

        总共有4个位置,每个位置可以向上转,也可以向下转,也就是有8种可能。比如,从 '0000' 开始,转一次,可以穷举出 '1000' ,'9000','0100','0900'······共8种密码。然后,再以这8种密码作为基础,对每种密码再转一下,穷举出所有可能······

        仔细想想,这就可以抽象成一幅图,每个节点有8个相邻的节点,求的又是最短距离,这不就是典型的BFS嘛,这时框架就可以派上用场了,先写出一个“简陋”的BFS框架代码:

package BFS;import java.util.LinkedList;
import java.util.Queue;// leetcode 109 打开转盘锁
public class OpenTheTurntable {public String plusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}public String minusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}// BFS框架伪码,打印所有可能的密码public void BFS(String target) {Queue<String> queue = new LinkedList<>();queue.offer("0000");while (!queue.isEmpty()) {int sz = queue.size();// 将当前队列中的所有节点向周围扩散for (int i = 0; i < sz; i++) {String cur = queue.poll();// 判断是否到达终点System.out.println(cur);// 将一个节点的相邻节点加入队列for (int j = 0; j < 4; j++) {String up = plusOne(cur, j);String down = minusOne(cur, j);queue.offer(up);queue.offer(down);}}// 在这里增加步数}return;}}

        注意:这段代码当然有很多问题,但是我们做算法题肯定不是一蹴而就的,而是从简陋到完美的。

        这段BFS代码已经能够穷举所有可能的密码组合了,但是显然不能完成题目,还有如下问题需要解决:

        1.会走回头路。比如,从 '0000' 拨到 '1000',但是等从队列中拿出 '1000'时,还会拨出一个 '0000',这样会产生死循环。

        2.没有终止条件,按照题目要求,找到 target 就应该结束并返回拨动的次数。

        3.没有对 deadends的处理,按道理这些“死亡密码”是不能出现的,也就是说遇到这些密码的时候需要跳过,不能进行任何操作。

        只要按照BFS框架在对应的位置稍微修改即可修复这些问题:

package BFS;import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;// leetcode 109 打开转盘锁
public class OpenTheTurntable {public String plusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}public String minusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}int openLock(String[] deadends, String target) {// 记录需要跳过的死亡密码Set<String> deads = new HashSet<>();for (String s : deadends) {deads.add(s);}// 记录已经穷举过的密码,防止走回头路Set<String> visited = new HashSet<>();Queue<String> queue = new LinkedList<>();// 从起点开始启动广度优先搜索int step = 0;queue.offer("0000");visited.add("0000");while (!queue.isEmpty()) {int sz = queue.size();// 将当前队列中的所有节点向周围扩散for (int i = 0; i < sz; i++) {String cur = queue.poll();// 判断密码是否合法,是否到达终点if (deads.contains(cur)) {continue;}if (cur.equals(target)) {return step;}// 将一个节点的相邻节点加入队列for (int j = 0; j < 4; j++) {String up = plusOne(cur, j);if (!visited.contains(up)) {queue.offer(up);visited.add(up);}String down = minusOne(cur, j);if (!visited.contains(down)) {queue.offer(down);visited.add(down);}}}// 在这里增加步数step += 1;}// 如果穷举完都没有找到目标密码,那就是找不到了return -1;}public static void main(String[] args) {OpenTheTurntable openTheTurntable = new OpenTheTurntable();String[] deadends = {"8888"};int count = openTheTurntable.openLock(deadends, "0008");System.out.println(count);}}

        至此,这道题目就解决了。但优化还没有结束,因为终点在哪里是知道的,所以可以用双向BFS进行优化。这里先留白,以后再补充······

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com