e网站的图标怎么做,电脑编程培训,湘潭做网站 i磐石网络,网页点击量统计双向BFS算法学习
推荐练习题 力扣“127”题#xff1a;单词接龙 “752”题#xff1a;打开轮盘锁 这里推荐一篇力扣题解 双向BFS 这里使用打开轮盘锁的题干进行举例#xff1a;
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字#xff1a; ‘0’, ‘1’, ‘2’,…双向BFS算法学习
推荐练习题 力扣“127”题单词接龙 “752”题打开轮盘锁 这里推荐一篇力扣题解 双向BFS 这里使用打开轮盘锁的题干进行举例
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字 ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转例如把 ‘9’ 变为 ‘0’‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ 一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字一旦拨轮的数字和列表里的任何一个元素相同这个锁将会被永久锁定无法再被旋转。
字符串 target 代表可以解锁的数字你需要给出解锁需要的最小旋转次数如果无论如何不能解锁返回 -1 。
分析
首先说明为什么使用双向BFS 在这里我们可以把起点比做一个圆的圆心我们使用BFS就是对这个圆进行向外延伸当延伸到目标点时圆的面积就是时间复杂度而我们采用双向BFS就是从两 个点作为圆心再进行延伸当相交时两个圆的面积小于只采用一个圆的面积当目标点离起始点越远越明显
这里我们与单向BFS的差别主要在下面几点
这里有两个起始点一个还是原来的起点0000还有一个是我们的目标值从这两个点开始发散的向四周发散的寻找所以我们需要创建两个队列和两个保存已经遍历元素的哈希集当一个队列的元素在另一个队列里面出现这时说明两个点之间已经“打通”找到了最短距离这里注意我们尽量每次让两个队列平均的进行添加这基于BFS的特性这里结束循环的条件是两个队列都不为空因为只要有一个位置空就说明两点之间不能达到
代码
package Power;import java.util.*;public class doubleBFS {class Solution {String t, s;SetString set new HashSet();public int openLock(String[] _ds, String _t) {s 0000;t _t;if (s.equals(t)) return 0;for (String d : _ds) set.add(d);if (set.contains(s)) return -1;int ans bfs();return ans;}int bfs() {// d1 代表从起点 s 开始搜索正向// d2 代表从结尾 t 开始搜索反向DequeString d1 new ArrayDeque(), d2 new ArrayDeque();/** m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来* e.g.* m1 {1000:1} 代表 1000 由 s0000 旋转 1 次而来* m2 {9999:3} 代表 9999 由 t9996 旋转 3 次而来*/MapString, Integer m1 new HashMap(), m2 new HashMap();d1.addLast(s);m1.put(s, 0);d2.addLast(t);m2.put(t, 0);/** 只有两个队列都不空才有必要继续往下搜索* 如果其中一个队列空了说明从某个方向搜到底都搜不到该方向的目标节点* e.g.* 例如如果 d1 为空了说明从 s 搜索到底都搜索不到 t反向搜索也没必要进行了*/while (!d1.isEmpty() !d2.isEmpty()) {int t -1;if (d1.size() d2.size()) {t update(d1, m1, m2);} else {t update(d2, m2, m1);}if (t ! -1) return t;}return -1;}int update(DequeString deque, MapString, Integer cur, MapString, Integer other) {int m deque.size();while (m-- 0) {String poll deque.pollFirst();char[] pcs poll.toCharArray();int step cur.get(poll);// 枚举替换哪个字符for (int i 0; i 4; i) {// 能「正向转」也能「反向转」这里直接枚举偏移量 [-1,1] 然后跳过 0for (int j -1; j 1; j) {if (j 0) continue;// 求得替换字符串 str// 这里使用的方法非常巧妙把字符为0和9的特殊情况处理了int origin pcs[i] - 0;// 取模处理9int next (origin j) % 10;// 如果为0.0-1为-1进行处理变成9if (next -1) next 9;char[] clone pcs.clone();clone[i] (char)(next 0);String str String.valueOf(clone);// 如果死亡数组里面包含就重新执行循环if (set.contains(str)) continue;// 如果已经遍历过就重新执行循环if (cur.containsKey(str)) continue;// 如果在「另一方向」找到过说明找到了最短路否则加入队列if (other.containsKey(str)) {return step 1 other.get(str);} else {deque.addLast(str);// 添加更新步数cur.put(str, step 1);}}}}return -1;}}
}
