Leetcode -752- Opens the spin lock
This is the third day of my participation in Gwen Challenge
[Blog link]
A path to learning at 🐔
The nuggets home page
[B].
[答 案]
Leetcode topic link
[making address]
Code link
[introduction]
Idea 1: BFS+ memory storage
- The first thing we have to do is figure out what is the boundary condition that we can’t meettarget
- 1. Illegal target (excluded in the title)
- 2. All possible targets are included in deadends
- 3. The limit array contains 0000
- The switch to target can only be done with target +-1 +-10 +-100 +-1000
- Is reserved when the current digit is 0 or 9
- According to the question, it can be predicted that there are 8 possibilities for the transformation of each tree, that is, all branch nodes 8^4, we can branch and subtract according to all 1 branch nodes
- Case 2 is the pruning condition
- Enumerating all changes starting at 0000 and then doing breadth-first traversal
- It then records the minimum number of changes to the current position, and finally returns the minimum number of changes in the result set when all cases have been traversed
- If the result set cannot be satisfied, -1 is returned
- The judgment of this idea is too complicated and can be optimized into the judgment scheme of idea two
public int openLock(String[] deadends, String target) {
// save deadends to set
Set<String> set = new HashSet<>();
Map<String, Integer> map = new HashMap<>();
if ("0000".equals(target)) {
return 0;
}
for (String dead : deadends
) {
if ("0000".equals(dead)) {
return -1;
}
set.add(dead);
}
Queue<String> queue = new LinkedList<>();
queue.add("0000");
map.put("0000".0);
while(! queue.isEmpty()) { String temp = queue.poll();if (temp.equals(target)) {
return map.get(temp);
}
for (int i = 0; i < 4; i++) {
String pre = temp.substring(0, i);
String cur = temp.substring(i + 1.4);
if (temp.charAt(i) == '0') {
if(! set.contains(pre +"1" + cur)) {
queue.add(pre + "1" + cur);
set.add(pre + "1" + cur);
map.put(pre + "1" + cur, map.get(temp) + 1);
}
if(! set.contains(pre +"9" + cur)) {
queue.add(pre + "9" + cur);
set.add(pre + "9" + cur);
map.put(pre + "9" + cur, map.get(temp) + 1); }}else if (temp.charAt(i) == '9') {
if(! set.contains(pre +"0" + cur)) {
queue.add(pre + "0" + cur);
set.add(pre + "0" + cur);
map.put(pre + "0" + cur, map.get(temp) + 1);
}
if(! set.contains(pre +"8" + cur)) {
queue.add(pre + "8" + cur);
set.add(pre + "8" + cur);
map.put(pre + "8" + cur, map.get(temp) + 1); }}else {
String key1 = pre + (Integer.parseInt(temp.substring(i, i + 1)) + 1) + cur;
if(! set.contains(key1)) { queue.add(key1); set.add(key1); map.put(key1, map.get(temp) +1);
}
String key2 = pre + (Integer.parseInt(temp.substring(i, i + 1)) - 1) + cur;
if(! set.contains(key2)) { queue.add(key2); set.add(key2); map.put(key2, map.get(temp) +1); }}}}return -1;
}
Copy the code12. Time complexity O(BD ⋅d2b^d \cdot d^ 2BD + MD) where b is 10 (base), d is the number of digits of the four-lock, and M is the length of the boundary array
Idea 2: Judgment condition optimization
public int openLock(String[] deadends, String target) {
// save deadends to set
Set<String> set = new HashSet<>();
Map<String, Integer> map = new HashMap<>();
for (String dead : deadends
) {
if ("0000".equals(dead)) {
return -1;
}
set.add(dead);
}
Queue<String> queue = new LinkedList<>();
queue.add("0000");
map.put("0000".0);
int size = 1;
while(! queue.isEmpty()) { String temp = queue.poll();if (temp.equals(target)) {
return map.get(temp);
}
char[] c = temp.toCharArray();
for (int i = 0; i < 4; i++) {
char tempC = c[i];
int x = tempC - '0';
int y = x;
c[i] = (char) (x + 1 > 9 ? '0' : x + 1 + '0');
String s = String.valueOf(c, 0.4);
if(! set.contains(s)) { queue.offer(s); set.add(s); map.put(s, map.get(temp) +1);
}
c[i] = (char) (y - 1 < 0 ? 9 + '0' : y - 1 + '0');
s = String.valueOf(c, 0.4);
if(! set.contains(s)) { queue.offer(s); set.add(s); map.put(s, map.get(temp) +1);
}
if (s.equals(target)) {
returnmap.get(target); } c[i] = tempC; }}return -1;
}
Copy the code12. Time complexity O(BD ⋅d2b^d \cdot d^ 2BD + MD) where b is 10 (base), d is the number of digits of the four-lock, and M is the length of the boundary array
Idea 3: Bidirectional BFS
- The difficulty of optimizing one-way BFS lies in space complexity, which leads to a large memory consumption as queues increase
- ⋅ D2b ^d \cdot d^ 2BD + MD **
- The optimization of bidirectional traversal is more about spatial complexity
- In fact, the idea of bidirectional BSF is somewhat similar to the idea of binary search, that is, from a one-way scan from the starting point, to the starting point and end point of the scanning process
- We first scan the starting point and the ending point respectively according to the one-way scanning scheme
- However, in this case, to ensure that the number of scans on both sides is almost the same, you can perform discriminating scan on the size of queues
- To be precise, bidirectional scanning is more like a discrete scan, which changes BFS from a one-way to a discrete scan, rather than following the sequential order of each node
- If one side of the map contains the current pop-up elements of the other side of the queue, it indicates that the two sides of the queue meet, and the sum of the values of the two sides of the queue + 1 is returned
class Solution {
Set<String> set = new HashSet<>();
Set<String> traced = new HashSet<>();
public int openLock(String[] deadends, String target) {
//corner case
if ("0000".equals(target)){
return 0;
}
Map<String, Integer> rmap = new HashMap<>(), lmap = new HashMap<>();
Deque<String> rqueue = new ArrayDeque<>(), lqueue = new ArrayDeque<>();
for (String s : deadends
) {
if (s.equals(target) || "0000".equals(s)) {
return -1;
}
set.add(s);
}
rqueue.add(target);
lqueue.add("0000");
lmap.put("0000".0);
rmap.put(target, 0);
while(! lqueue.isEmpty() && ! rqueue.isEmpty()) {int t = -1;
if (lqueue.size() <= rqueue.size()) {
t = trace(lqueue, lmap, rmap);
} else {
t = trace(rqueue, rmap, lmap);
}
if(t ! = -1) {
returnt; }}return -1;
}
public int trace(Deque<String> queue, Map<String, Integer> cur, Map<String, Integer> other) {
String temp = queue.pollFirst();
if (other.containsKey(temp)) {
return other.get(temp) + cur.get(temp) + 1;
}
for (int i = 0; i < 4; i++) {
char[] c = temp.toCharArray();
char tempC = c[i];
int x = tempC - '0';
int y = x;
c[i] = (char) (x + 1 > 9 ? '0' : x + 1 + '0');
String s1 = String.valueOf(c, 0.4);
if(! set.contains(s1)){if (other.containsKey(s1)) {
return other.get(s1) + cur.get(temp) + 1;
}else{
if(! traced.contains(s1)){ queue.addLast(s1); } traced.add(s1); cur.put(s1, cur.get(temp) +1);
}
}
c[i] = (char) (y - 1 < 0 ? 9 + '0' : y - 1 + '0');
String s2 = String.valueOf(c, 0.4);
if(! set.contains(s2)){if (other.containsKey(s2)) {
return other.get(s2) + cur.get(temp) + 1;
} else {
// Check whether the current node has been scanned
if(! traced.contains(s2)){ queue.addLast(s2); } traced.add(s2); cur.put(s2, cur.get(temp) +1); }}}return -1; }}Copy the code⋅ D2b ^d \ Cdot d^ 2BD + MD **
The remaining two algorithms are beyond my comprehension