752. 打開轉盤鎖
2021-06-25 LeetCode每日一題
鏈接：//leetcode-cn.com/problems/open-the-lock/
標籤：廣度優先搜索、數組、哈希表、字元串
題目
你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每個撥輪可以自由旋轉：例如把 ‘9’ 變為 ‘0’，’0′ 變為 ‘9’ 。每次旋轉都只能旋轉一個撥輪的一位數字。
鎖的初始數字為 ‘0000’ ，一個代表四個撥輪的數字的字元串。
列表 deadends 包含了一組死亡數字，一旦撥輪的數字和列表裡的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉。
字元串 target 代表可以解鎖的數字，你需要給出解鎖需要的最小旋轉次數，如果無論如何不能解鎖，返回 -1 。
輸入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
輸出：6
解釋：
可能的移動序列為 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 這樣的序列是不能解鎖的，
因為當撥動到 "0102" 時這個鎖就會被鎖定。
輸入: deadends = ["8888"], target = "0009"
輸出：1
解釋：
把最後一位反向旋轉一次即可 "0000" -> "0009"。
輸入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
輸出：-1
解釋：
無法旋轉到目標數字且不被鎖定。
輸入: deadends = ["0000"], target = "8888"
輸出：-1
提示：
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 僅由若干位數字組成
分析
最短路問題，通常使用BFS求解。BFS就不用多說了，樹的層序遍歷就是使用BFS，這裡可以把初始狀態0000作為樹的根節點，而0000的下一可能狀態就是它的子節點，這就相當於一棵樹的層序遍歷了。每遍歷一層，則旋轉次數加1，找到題目給定的target時，所在的那層即需要旋轉的最小次數。
如果在數據量大的情況下，可能一層就會有幾萬幾十萬個節點，一般BFS解法，可能會空間爆炸。這種情況可以使用雙向BFS解決，同時從兩個方向開始搜索，一旦搜索到相同的值，意味著找到了一條聯通起點和終點的最短路徑。
「雙向 BFS」的基本實現思路如下：
- 創建「兩個隊列」分別用於兩個方向的搜索；
- 創建「兩個哈希表」用於「解決相同節點重複搜索」和「記錄轉換次數」；
- 為了儘可能讓兩個搜索方向「平均」，每次從隊列中取值進行擴展時，先判斷哪個隊列容量較少；
- 如果在搜索過程中「搜索到對方搜索過的節點」，說明找到了最短路徑。
「雙向 BFS」基本思路對應的偽程式碼大致如下：
d1、d2 為兩個方向的隊列
m1、m2 為兩個方向的哈希表，記錄每個節點距離起點的
// 只有兩個隊列都不空，才有必要繼續往下搜索
// 如果其中一個隊列空了，說明從某個方向搜到底都搜不到該方向的目標節點
while(!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else {
update(d2, m2, m1);
}
}
// update 為從隊列 d 中取出一個元素進行「一次完整擴展」的邏輯
void update(Deque d, Map cur, Map other) {}
參考：//leetcode-cn.com/problems/open-the-lock/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-wyr9/
編碼
一般BFS：
class Solution {
// 轉盤向上撥動一次
private String upOne(String str, int index) {
char[] chs = str.toCharArray();
if (chs[index] == '9') {
chs[index] = '0';
} else {
chs[index] += 1;
}
return new String(chs);
}
// 轉盤向下撥動一次
private String downOne(String str, int index) {
char[] chs = str.toCharArray();
if (chs[index] == '0') {
chs[index] = '9';
} else {
chs[index] -= 1;
}
return new String(chs);
}
public int openLock(String[] deadends, String target) {
// 死亡數字
Set<String> deadLock = new HashSet<>();
// 已經轉過的數字
Set<String> visited = new HashSet<>();
for (String str : deadends) {
deadLock.add(str);
}
Queue<String> res = new LinkedList<>();
res.offer("0000");
visited.add("0000");
int step = 0;
while (!res.isEmpty()) {
int len = res.size();
// 當前隊列中的所有節點向周圍擴散
for (int i = 0; i < len; i++) {
String cur = res.poll();
// 如果是死亡數字，則退出這次循環
if (deadLock.contains(cur)) {
continue;
}
// 轉到target，直接返回step即為最小旋轉次數
if (cur.equals(target)) {
return step;
}
// 對於當前節點，每個撥輪進行向上和向下轉動
for (int j = 0; j < 4; j++) {
String next = upOne(cur, j);
if (!visited.contains(next)) {
res.offer(next);
visited.add(next);
}
next = downOne(cur, j);
if (!visited.contains(next)) {
res.offer(next);
visited.add(next);
}
}
}
// 增加步數
step++;
}
// 如果窮舉完還沒有找到目標，則說明無法解鎖
return -1;
}
}
雙向BFS：
class Solution {
String t, s;
Set<String> 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 開始搜索（反向）
Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
/*
* m1 和 m2 分別記錄兩個方向出現的狀態是經過多少次轉換而來
* e.g.
* m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋轉 1 次而來
* m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋轉 3 次而來
*/
Map<String, 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(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
String poll = deque.pollFirst();
char[] pcs = poll.toCharArray();
int step = cur.get(poll);
// 枚舉替換哪個字元
for (int i = 0; i < 4; i++) {
// 能「正向轉」也能「反向轉」，這裡直接枚舉偏移量 [-1,1] 然後跳過 0
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
// 求得替換字元串 str
int origin = pcs[i] - '0';
int next = (origin + j) % 10;
if (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;
}
}
