Open the turntable lock
June 25, 2021
Title Description
You have a turntable lock with four round wheels. Each paddle has 10 digits: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . Each paddle wheel can rotate freely: for example, the '9' Become '0'，'0' Become '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. list deadends 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 cannot be rotated. character string target Represents the number that can be unlocked. You need to give the minimum number of rotations. If you can't unlock anyway, go back -1. Example 1: Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: The possible moving sequences are "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". be careful "0000" -> "0001" -> "0002" -> "0102" -> "0202" Such a sequence cannot be unlocked, Because when the dial reaches "0102" The lock will be locked. Example 2: input: deadends = ["8888"], target = "0009" Output: 1 Explanation: Turn the last bit in the opposite direction once "0000" -> "0009". Example 3: input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output:-1 Explanation: Cannot rotate to target number and is not locked. Example 4: input: deadends = ["0000"], target = "8888" Output:-1
Source: LeetCode
Link: https://leetcode-cn.com/problems/open-the-lock
The copyright belongs to Lingkou network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
thinking
My idea is to brute force solution, breadth optimal search, starting from 0000, traverse every number that can be reached, that is, each bit plus 1 or minus 1, use an array to store the current traversed number, and then skip the number of obstacles, when reaching the target number, it is the minimum number of steps
class Solution {
public int openLock(String[] deadends, String target) {
//Think about how to do it. From 0000 to 0202, four times is ok, but it will go through 01010201 or 0102, so we should avoid these two,
//That is to say, you need to add one to any of the other two bits first, and then subtract one at last. That is to say, the original 4 times + 2 times, used 6 times
//The most common method is to try from one number to another. If you are in deadends, you will return. If you are not, you will continue
//But where are the exits? Just try one by one. Use a used array to count the usage
//Is there any difference between adding one and subtracting one? It seems that there is no difference. Subtraction can reach, and addition can reach, but because the statistics is the minimum number
//Therefore, we also need to consider the situation of reduction
Set<String> set = new HashSet<>();
for(String s : deadends)
set.add(s);
//Mark whether each number has been reached
boolean[] used = new boolean[10000];
Queue<String> queue = new LinkedList<>();
//Two special cases need to be considered
if(set.contains("0000"))
return -1;
if(target.compareTo("0000") == 0)
return 0;
queue.add("0000");
used[0] = true;
int step = 0;
while(!queue.isEmpty()){
int size = queue.size();
step++;
while(size-- > 0){
String s = queue.poll();
//Then traverse the following 8 cases of s, 0-3 plus, 4-7 minus
for(int i = 0; i < 8; i++){
String next = getString(s, i);
if(!set.contains(next) && !used[Integer.valueOf(next)]){
queue.add(next);
used[Integer.valueOf(next)] = true;
}
if(next.compareTo(target) == 0){
//if(next.equals(target))
return step;
}
}
}
}
return -1;
}
public String getString(String s, int index){
boolean flag = index < 4 ? true : false; //The first four are plus and the last four are minus
index = index % 4;
char[] cc = s.toCharArray();
if(flag){
cc[index] = cc[index] == '9' ? '0' : (char)(cc[index] + 1);
}else{
cc[index] = cc[index] == '0' ? '9' : (char)(cc[index] - 1);
}
return new String(cc);
}
}
Look at the problem solution, mainly BFS and A algorithm, A algorithm do not want to go into, previously on machine learning class, mainly learn about two-way BFS. Jump to question 127, which is basically the same as this question. This question is to change the number, 127 is to change the letter. Write the code of bidirectional BFS
127. Word Solitaire
Title Description
Dictionaries wordList From the word beginWord and endWord The transformation sequence of is a sequence formed according to the following specifications: The first word in the sequence is beginWord . The last word in the sequence is endWord . Only one letter can be changed at a time. The middle word in the conversion process must be a dictionary wordList The words in. Here are two words for you beginWord and endWord And a dictionary wordList ，Find from beginWord reach endWord The number of words in the shortest conversion sequence of. If there is no such conversion sequence, return 0. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: a shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", Returns its length 5. Example 2: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: endWord "cog" Is not in the dictionary, so cannot convert.
Source: LeetCode
Link: https://leetcode-cn.com/problems/word-ladder
The copyright belongs to Lingkou network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
thinking
Bidirectional BFS to reduce the width of the search space. When the same elements exist in two queues, it means that the path of change has been found and the number of steps needed for the current change is returned
Note that there is no method in the queue to determine whether an element exists, so you need to put the elements in the queue in a temporary hash table
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
//If not in the result set, return 0 directly
if(!set.contains(endWord))
return 0;
if(beginWord.equals(endWord))
return 1;
//Two way, two queue s
Queue<String> q1 = new LinkedList<>();
q1.add(beginWord);
Queue<String> q2 = new LinkedList<>();
q2.add(endWord);
//Usage of tag strings
Set<String> used = new HashSet<>();
//Number of traversal steps
int step = 1;
//Start two way search
while(!q1.isEmpty() && !q2.isEmpty()){
//Starting from the smaller one, define q1 as the smaller one
if(q1.size() > q2.size()){
Queue<String> temp = q1;
q1 = q2;
q2 = temp;
}
//Diffusion of q1
int len = q1.size();
step++;
while(len-- > 0){
//Fetches the current string
String s = q1.poll();
//Judge the result of the string diffusion
boolean flag = getString(s, q1, q2, used, set);
if(flag)
return step;
}
}
return 0;
}
public boolean getString(String s, Queue<String> q1, Queue<String> q2, Set<String> used, Set<String> set){
int l = s.length();
char[] cc = s.toCharArray();
Set<String> temp = new HashSet<>(q2);
for(int i = 0; i < l; i++){
char cur = cc[i];
for(char j = 'a'; j <= 'z'; j++){
if(cc[i] == j)
continue;
cc[i] = j;
//New string
String next = new String(cc);
if(set.contains(next) && !used.contains(next)){
q1.add(next);
used.add(next);
}
if(temp.contains(next))
return true;
}
cc[i] = cur;
}
return false;
}
}
773. Slide Puzzle
On June 26, 2021, I wrote a question every day, which was basically the same as yesterday's question
Title Description
In a 2 x 3 It's on the board( board)There are five bricks and tiles, using the number one~5 To express, And a vacancy is represented by 0. A move is defined as selecting 0 to exchange with an adjacent number (up, down, left and right). Finally when the board board The result is that [[1,2,3],[4,5,0]] The puzzle board was solved. The initial state of a puzzle board is given, and the minimum number of times the puzzle board can be solved is returned. If the puzzle board cannot be solved, it is returned -1 . Example: Input: board = [[1,2,3],[4,0,5]] Output: 1 Explanation: exchange 0 and 5, 1 step complete Input: board = [[1,2,3],[5,4,0]] Output:-1 Explanation: there is no way to complete the puzzle board Input: board = [[4,1,2],[5,0,3]] Output: 5 Explanation: The minimum number of moves to complete the puzzle board is 5, A mobile path: Not yet moved: [[4,1,2],[5,0,3]] Move once: [[4,1,2],[0,5,3]] Move 2 times: [[0,1,2],[4,5,3]] Move 3 times: [[1,0,2],[4,5,3]] Move 4 times: [[1,2,0],[4,5,3]] Move 5 times: [[1,2,3],[4,5,0]] Input: board = [[3,2,4],[1,5,0]] Output: 14
Source: LeetCode
Link: https://leetcode-cn.com/problems/sliding-puzzle
The copyright belongs to Lingkou network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
thinking
One way BFS, as like as two peas, is the same as yesterday.
class Solution {
//Preprocessing adjacent positions
int[][] neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
public int slidingPuzzle(int[][] board) {
//Or is it the same as yesterday's BFS, considering how to carry out digital exchange, or will it become yesterday's string? Or do you operate directly on arrays?
//Learn how to deal with official interpretation
//Because the array size is fixed, the strings are arranged in the form of 0 1 2 3 4 5,
//Then the adjacent position of 0 can be exchanged is 1 3, and the adjacent position of 1 can be exchanged is 0 2 4
//This is processed in advance, and then traversed when it reaches a certain location for exchange
//Similarly, a set is used to represent the state that has been reached
//Convert to string first
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 2; i++){
for(int j = 0; j < 3; j++){
sb.append(board[i][j]);
}
}
String s = sb.toString();
String target = "123450";
if(s.equals(target))
return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(s);
int step = 0;
Set<String> set = new HashSet<>();
set.add(s);
while(!queue.isEmpty()){
int size = queue.size();
step++;
while(size-- > 0){
String curr = queue.poll();
int index = 0;
for(int i = 0; i < curr.length(); i++){
if(curr.charAt(i) == '0'){
index = i;
break;
}
}
int[] pos = neighbor[index];
//Exchange two positions in curr to get a new string
for(int i = 0; i < pos.length; i++){
String next = getString(curr, index, pos[i]);
if(!set.contains(next)){
set.add(next);
queue.offer(next);
}
if(next.equals(target))
return step;
}
}
}
return -1;
}
public String getString(String s, int i, int j){
char[] cc = s.toCharArray();
char temp = cc[i];
cc[i] = cc[j];
cc[j] = temp;
return new String(cc);
}
}
Astar algorithm appears in all three problems, so this algorithm is studied here
I think it's very detailed. The two properties are also very clear. It's very clear when combined with the code
class Solution {
//Look at the official solution of Astar, and then basically did not understand how to do, but this code and bfs code is basically the same, combined with the code to see it is very clear
//It's just that the queue is replaced by the priority queue, and then the sorting rule is changed. This rule is also the main algorithm idea
int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
public int slidingPuzzle(int[][] board) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 3; ++j) {
sb.append(board[i][j]);
}
}
String initial = sb.toString();
if ("123450".equals(initial)) {
return 0;
}
//The priority queue is arranged according to f
PriorityQueue<AStar> pq = new PriorityQueue<AStar>((a, b) -> a.f - b.f);
pq.offer(new AStar(initial, 0));
Set<String> seen = new HashSet<String>();
seen.add(initial);
while (!pq.isEmpty()) {
//Take out the elements at the top of the queue and update them
AStar node = pq.poll();
for (String nextStatus : get(node.status)) {
if (!seen.contains(nextStatus)) {
if ("123450".equals(nextStatus)) {
return node.g + 1;
}
pq.offer(new AStar(nextStatus, node.g + 1));
seen.add(nextStatus);
}
}
}
return -1;
}
// Enumerates the state of status obtained by an exchange operation
public List<String> get(String status) {
List<String> ret = new ArrayList<String>();
char[] array = status.toCharArray();
int x = status.indexOf('0');
for (int y : neighbors[x]) {
swap(array, x, y);
ret.add(new String(array));
swap(array, x, y);
}
return ret;
}
public void swap(char[] array, int x, int y) {
char temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
//Main algorithm idea
class AStar {
// Manhattan distance is the number of steps required for each location to reach other locations
public static int[][] dist = {
{0, 1, 2, 1, 2, 3},
{1, 0, 1, 2, 1, 2},
{2, 1, 0, 3, 2, 1},
{1, 2, 3, 0, 1, 2},
{2, 1, 2, 1, 0, 1},
{3, 2, 1, 2, 1, 0}
};
public String status;
public int f, g, h;
//G(x) is the "actual" path length from the starting point s to the node X. note that G(x) is not necessarily the shortest
//H(x) is the "estimated" shortest path length from node x to terminal t, which is called heuristic function;
//H * (x) denotes the "actual" shortest path length from node x to destination T, which we can't find in the process of breadth first search. We need to approximate h * (x) with H(x);
//F(x) satisfies F(x) = G(x) + H(x), which is the "estimated" path length from the starting point s to the end point t.
//We always select the smallest F(x) corresponding to X to search, so A * algorithm needs to use priority queue to achieve.
public AStar(String status, int g) {
//Here g is actually the number of steps taken, that is, the distance to the initial state
this.status = status;
this.g = g;
this.h = getH(status);
//f is the distance from the initial state to the end state, which is sorted according to the distance, and then the state is updated
this.f = this.g + this.h;
}
// Compute heuristic function
// Calculate the distance from the current state to the target state, that is, the distance to 123450, so you need to subtract "1" here. For example, 1 needs to go to position 0 and 5 needs to go to position 4
// After all the five numbers are put in place, 0 will naturally be put in place, so we don't count the situation of 0 here
public static int getH(String status) {
int ret = 0;
for (int i = 0; i < 6; ++i) {
if (status.charAt(i) != '0') {
ret += dist[i][status.charAt(i) - '1'];
}
}
return ret;
}
}
Looking back at yesterday's question, the A * algorithm is actually the same as today's one. It mainly designs the algorithm for finding h. in these two questions, it calculates the distance to the target state, and then updates the queue according to the distance