Open the turntable lock
Title Link
Title Description:
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 paddle wheel can rotate freely: for example, change '9' to '0', and '0' to '9' (remember). 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. If it cannot be unlocked anyway, return - 1.
Example 1:
Input: deands = ["0201", "0101", "0102", "1212", "2002"], target = "0202"
Output: 6
Explanation:
The possible moving sequence is "0000" - > "1000" - > "1100" - > "1200" - > "1201" - > "1202" - > "0202".
Note that sequences such as "0000" - > "0001" - > "0002" - > "0102" - > "0202" cannot be unlocked,
Because when you dial "0102", the lock will be locked.
Example 2:
Input: deands = ["8888"], target = "0009"
Output: 1
Explanation:
Rotate the last bit in reverse once to "0000" - > "0009".
Example 3:
Enter: deands = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], target = "8888"
Output: - 1
Explanation:
Cannot rotate to target number and is not locked.
Practice: Feige didn't see the meaning of the title at first, thinking that he had to enumerate all possible transformations. He ignored that he could only rotate to the adjacent position, so he didn't pass. Later, he found that there were only two transformations for a digit, namely, the left and right. Did he think of a binary tree when he saw the left and right? And because he was looking for the shortest path, he used breadth first search, The combination of breadth first search and binary tree is not the sequence traversal of binary tree? So far, we have found a way. Secondly, the password in deands cannot be unlocked, so as long as the password is in it, it cannot be used.
The following code is:
class Solution {
public int openLock(String[] deadends, String target) {
Queue<String>queue=new LinkedList<>();
HashSet<String>lockSet=new HashSet<>();
for(String x:deadends){
lockSet.add(x);
}
HashSet<String>visited=new HashSet<>();
queue.offer("0000");
visited.add("0000");
if(lockSet.contains("0000")){//If the initial passwords are in the S lock area, you don't have to waste your time
return -1;
}
int result=0;
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
String cur=queue.poll();
if(cur.equals(target)){
return result;
}
char[]cc=cur.toCharArray();
for(int i=0;i<4;++i){
char x=cc[i];
cc[i]=(x=='9'?'0':(char)(x+1));//right
String s1=new String(cc);
cc[i]=(x=='0'?'9':(char)(x-1));//Left
String s2=new String(cc);
if(!lockSet.contains(s1)&&(!visited.contains(s1))){
queue.offer(s1);
visited.add(s1);
}
if(!lockSet.contains(s2)&&(!visited.contains(s2))){
queue.offer(s2);
visited.add(s2);
}
cc[i]=x;
}
size--;
}
result++;
}
return -1;
}
}
Oh, by the way, some big guys know why I changed x-1 and x+1 into cc[i]-1 and cc[i]+1. The result is wrong? The cc[i] was restored after Mingming??
Minimal genetic change
Link to this question
A gene sequence is represented by an 8-character string, in which each character belongs to any one of "a", "C", "G" and "T".
Suppose we want to investigate the change of a gene sequence. A gene change means that a character in the gene sequence has changed.
For example, a gene change occurs when the gene sequence changes from "AACCGGTT" to "AACCGGTA".
At the same time, the result of each gene change needs to be a legal gene string, that is, the result belongs to a gene bank.
Now, given three parameters - start, end and bank, which represent the starting gene sequence, target gene sequence and gene bank respectively, please find out the minimum number of changes required to change the starting gene sequence into the target gene sequence. If the target change cannot be achieved, return - 1.
be careful:
The starting gene sequence is legal by default, but it does not necessarily appear in the gene bank.
If a starting gene sequence needs to be changed many times, the gene sequence after each change must be legal.
It is assumed that the starting gene sequence is different from the target gene sequence.
Example 1:
start: "AACCGGTT"
end: "AACCGGTA"
bank: ["AACCGGTA"]
Return value: 1
Example 2:
start: "AACCGGTT"
end: "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
Return value: 2
The practice is the same as that in my previous article Word Chain The practice is basically the same. I won't say more, but go directly to the code:
class Solution {
public int minMutation(String start, String end, String[] bank) {
Queue<String>queue=new LinkedList<>();
HashSet<String>set=new HashSet<>();
HashSet<String>visited=new HashSet<>();
String s="ACGT";
for(String x:bank){
set.add(x);
}
queue.offer(start);
visited.add(start);
int result=1;
while(!queue.isEmpty()){
int len=queue.size();
while(len>0){
String word=queue.poll();
char[]cc=word.toCharArray();
for(int i=0;i<cc.length;++i){
char xx=cc[i];
for(int j=0;j<4;++j){
if(xx!=s.charAt(j)){
cc[i]=s.charAt(j);
String newWord=new String(cc);
if(!visited.contains(newWord)&&set.contains(newWord)){
queue.offer(newWord);
visited.add(newWord);
}
if(visited.contains(newWord)&&newWord.equals(end)){
return result;
}
}
}
cc[i]=xx;
}
len--;
}
result++;
}
return -1;
}
}
If you think it's good, pay attention and praise it!!!