做 在线观看免费网站有哪些,网站界面设计应该遵循的原则,天元建设集团电话,百度指数下载app题目 一个密码锁由 4 个环形拨轮组成#xff0c;每个拨轮都有 10 个数字#xff1a; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 。每个拨轮可以自由旋转#xff1a;例如把 9 变为 0#xff0c;0 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 0000 #xff0c;一个…题目 一个密码锁由 4 个环形拨轮组成每个拨轮都有 10 个数字 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 。每个拨轮可以自由旋转例如把 9 变为 00 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 0000 一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字一旦拨轮的数字和列表里的任何一个元素相同这个锁将会被永久锁定无法再被旋转。 字符串 target 代表可以解锁的数字请给出解锁需要的最小旋转次数如果无论如何不能解锁返回 -1 。
解题 第一步我们不管所有的限制条件不管 deadends 和 target 的限制就思考一个问题如果让你设计一个算法穷举所有可能的密码组合你将怎么做 总共有4个位置每个位置可以向上转也可以向下转也就是有8种可能。比如从 0000 开始转一次可以穷举出 1000 900001000900······共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) {QueueString 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) {// 记录需要跳过的死亡密码SetString deads new HashSet();for (String s : deadends) {deads.add(s);}// 记录已经穷举过的密码防止走回头路SetString visited new HashSet();QueueString 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进行优化。这里先留白以后再补充······
