Leetcode brush the daily problem and the next problem of the daily problem note 26/30

Writing in the front

This is the 26th day of my participation in Gwen Challenge

About to graduate, only to find himself in the interview algorithm hanging hammer. There is no way to zero based identity and classmates to join the force buckle brush problem army. My classmates are very good, they are usually just modest, verbally said that they will not, and I really will not… Nuggets encourage new people to blog every day, I also join in a lively, record every day brush the first two questions, these two questions I do. I plan to brush five questions every day. For the other questions, I can only memorize the routine by force and will not post them in my blog.

I am really just a vegetable chicken, what do not want to solve the problem from my reference, coding habits also need to improve, if you want to find brush problem master ask questions, I think it is better to go to the palace water sanye brush problem diary this big guy. I try not to see the solution of the problem before I make it, so as not to collide with the content of the big guy.

In addition, I also hope to have the leisure of the big guy to provide some higher clear problem-solving ideas to me, welcome to discuss ha!

Good nonsense does not say to begin the first two questions of the twenty-sixth day!

2021.6.26 One question of the day

773. Sliding puzzles

This question has huarong road inside taste, when I was a child to play with the toy, I remember that it seemed to play some rules, spiral movement and then can recover, now I have forgotten all… There should be a formula for this thing,

Similar to this kind of thing digital Huarong road how to solve?

Of course, if we need to do the problem now, it will be too late to find A solution from here and write the code. This kind of problem is either BFS or A*. In fact, yesterday’s daily problem can also use A*, but I am not familiar with this algorithm, so I did not dare to use it. So, before we do that, let me introduce you to A star.

A* algorithm is characterized by A starting cost and an end cost, and two cost functions constitute A complete cost function. Then the end cost is only determined after the road to the end is determined, so the total cost of the end cost is actually an estimate, the optimal route is the best end cost. That estimate function is also called the heuristic function, and in this case the heuristic function is the number of steps that each number in the current state takes to return to its position. Because putting a number back is actually the Manhattan distance between the two positions of that number, you can list the matrix of that distance, and then you can read the end cost directly against the matrix.


[ 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 ] \begin{bmatrix} 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 \\ \end{bmatrix}

Today this algorithm did not thoroughly understand, first with the official solution of the top…

One of the following questions per day

Reference to missing numbers in Offer 53-II. 0 to n-1

This problem uses binary search, missing number left number and serial number is on, right is one difference. That is, if all the numbers match the serial number, the missing number is the last one.


class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] ! = mid) r = mid;else l = mid + 1;
        }
        if(nums[r] == r) r++;
        returnr; }};Copy the code

summary

A* algorithm terminal cost, distance function selection, binary search

Refer to the link

A* algorithm for path planning