June 25, 2021 leetcode daily question
Rebate website https://www.cpa5.cn/Link: https://leetcode-cn.com/problems/open-the-lock/
Tags: breadth first search, array, hash table, string
subject
You have a turntable lock with four round dials. Each dial wheel has 10 numbers: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Each dial wheel can rotate freely: for example, change '9' to '0', and '0' to '9'. Each rotation can only rotate one digit of one dial wheel.
The initial number of the lock is' 0000 ', a string representing the number of four dials.
The list deands contains a set of death numbers. Once the number of the dial wheel is the same as any element in the list, the lock will be permanently locked and can no longer be rotated.
The string target represents the number that can be unlocked. You need to give the minimum number of rotations required for unlocking. If it cannot be unlocked anyway, return - 1.
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: Possible movement sequences are "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". be careful "0000" -> "0001" -> "0002" -> "0102" -> "0202" Such a sequence cannot be unlocked, Because when you dial "0102" The lock will be locked. input: deadends = ["8888"], target = "0009" Output: 1 Explanation: Rotate the last bit in reverse once "0000" -> "0009". input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output:-1 Explanation: Cannot rotate to target number and is not locked. input: deadends = ["0000"], target = "8888" Output:-1
Tips:
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target is not in deands
- target and deands [i] consist of only a few digits
analysis
The shortest path problem is usually solved by BFS. Needless to say, BFS is used for sequence traversal of a tree. Here, the initial state 0000 can be used as the root node of the tree, and the next possible state of 0000 is its child node, which is equivalent to sequence traversal of a tree. Each time you traverse a layer, the number of rotations is increased by 1. When you find the target given by the topic, the layer is the minimum number of rotations.
If there is a large amount of data, there may be tens of thousands of nodes on the first floor. The general BFS solution may explode in space. This situation can be solved by using two-way BFS. Search from two directions at the same time. Once the same value is searched, it means that the shortest path connecting the starting point and the ending point is found.
The basic implementation idea of "two-way BFS" is as follows:
- Create "two queues" for searching in two directions respectively;
- Create "two hash tables" for "solving duplicate searches on the same node" and "record conversion times";
- In order to make the two search directions "average" as much as possible, judge which queue has less capacity each time you take a value from the queue for expansion;
- If the node searched by the other party is found during the search, the shortest path is found.
The pseudo code corresponding to the basic idea of "two-way BFS" is roughly as follows:
d1,d2 Queue in both directions
m1,m2 For a hash table in two directions, record the distance between each node and the starting point
// Only when both queues are not empty, it is necessary to continue searching
// If one of the queues is empty, it means that the target node in that direction cannot be searched from one direction to the end
while(!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else {
update(d2, m2, m1);
}
}
// update is the logic of taking an element from queue d for "one complete expansion"
void update(Deque d, Map cur, Map other) {}
reference resources: https://leetcode-cn.com/problems/open-the-lock/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-wyr9/
code
General BFS:
class Solution {
// Turn the rotary table upward once
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);
}
// Turn the rotary table down once
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) {
// Death number
Set<String> deadLock = new HashSet<>();
// Number that has been turned
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();
// All nodes in the current queue spread around
for (int i = 0; i < len; i++) {
String cur = res.poll();
// If it is a death number, exit this cycle
if (deadLock.contains(cur)) {
continue;
}
// Go to target and directly return to step, which is the minimum number of rotations
if (cur.equals(target)) {
return step;
}
// For the current node, each paddle wheel rotates up and down
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);
}
}
}
// Increase steps
step++;
}
// If the target is not found after exhaustive enumeration, it means that it cannot be unlocked
return -1;
}
}
Bidirectional 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 stands for searching from the starting point s (forward)
// d2 stands for searching from the end t (reverse)
Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
/*
* m1 And m2 respectively record how many times the states in the two directions are converted
* e.g.
* m1 = {"1000":1} Represents "1000", which is derived from the rotation of s="0000" once
* m2 = {"9999":3} Represents "9999", which is rotated 3 times by t="9996"
*/
Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
d1.addLast(s);
m1.put(s, 0);
d2.addLast(t);
m2.put(t, 0);
/*
* Only when both queues are not empty, it is necessary to continue searching
* If one of the queues is empty, it means that the target node in a certain direction cannot be found
* e.g.
* For example, if d1 is empty, it means that the search from s can not find t, and the reverse search is unnecessary
*/
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);
// Enumerate which character to replace
for (int i = 0; i < 4; i++) {
// It can be "forward rotation" or "reverse rotation". Here, directly enumerate the offset [- 1,1], and then skip 0
for (int j = -1; j <= 1; j++) {
if (j == 0) continue;
// Get the replacement string 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 it is found in the "other direction", it indicates that the shortest path has been found, otherwise join the queue
if (other.containsKey(str)) {
return step + 1 + other.get(str);
} else {
deque.addLast(str);
cur.put(str, step + 1);
}
}
}
return -1;
}
}
