Leetcode brush the daily problem and the next problem of the daily problem notes 27/30

Writing in the front

This is the 27th 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 not to say the first two questions of the twenty-seventh day!

2021.6.27 One question of the day

909. Snakes and ladders

Simply put, there is a portal on the board, and when you reach the beginning of the portal, you can pass it, but only once. This question can still be A*, but yesterday’s experience told me that the water is too deep for me to grasp, I’d better be honest BFS better…

Last year’s collapse of sanxia living seems to be a similar topic of monopoly dice chess, there is a strange in the rear of the ass after chasing their own, also can’t let it catch up, they have to put the front of the strange row, they can throw bombs, that variable is much more than this, of course, and childhood board games are still nothing.

BFS takes the node number and the minimum number of times to reach that node as the state, and then updates the minimum number of times for the next six nodes with the possible six steps (i.e., the next time) after the current node. Because the chessboard is two-dimensional, but throwing the dice forward can only increase one dimension, so there is actually a hidden step to pull the number of the chessboard into one dimension operation. Let’s say the old number is pxy, and now the new number is qx, and the relationship between the two is going to be


p y = ⌊ q x – 1 N ⌋ p x = { q x – 1   m o d   N . p y   i s   e v e n N – 1 – ( q x – 1   m o d   N ) . p y   i s   o d d \texttt{p}_y = \lfloor \frac{\texttt{q}_x – 1}{N} \rfloor \\ \texttt{p}_x = {\left \{ \begin{array}{ll} \texttt{q}_x – 1 \ mod \ N, & \texttt{p}_y \ is \ even \\ N – 1 – \left ( \texttt{q}_x – 1 \ mod \ N \right ), & \texttt{p}_y \ is \ odd \\ \end{array} \right.}

Some people wonder why there are two numbers, but just go down and finish. The main thing is that the portals in the input are two-dimensional coordinates, and I can only keep this step here, because I don’t know whether there are more portals or more normal grids on the board, so it’s all converted.

I’m going to write this code, and I’m going to use p and Q when I’m representing the queue, so instead of using those two letters, I’m going to use r and C for ROL and COL, and the one-dimensional number is id.


class Solution {
    pair<int.int> id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        if (r % 2= =1) {
            c = n - 1 - c;
        }
        return {n - 1 - r, c};
    }

public:
    int snakesAndLadders(vector<vector<int>> &board) {
        int n = board.size(a);vector<int> vis(n * n + 1);
        queue<pair<int.int>> q;
        q.emplace(1.0);
        while(! q.empty()) {
            auto p = q.front(a); q.pop(a);for (int i = 1; i <= 6; i++) {
                int nxt = p.first + i;
                if (nxt > n * n) {
                    break;
                }
                auto rc = id2rc(nxt, n);
                if (board[rc.first][rc.second] > 0) {
                    nxt = board[rc.first][rc.second];
                }
                if (nxt == n * n) {
                    return p.second + 1;
                }
                if(! vis[nxt]) { vis[nxt] =true;
                    q.emplace(nxt, p.second + 1); }}}return - 1; }};Copy the code

One of the following questions per day

412. The Fizz Buzz

I won’t do the easy ones.


class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> result;
        for (int i = 1; i <= n; ++i) result.push_back(to_string(i));
        for (int i = 2; i < n; i += 3) result[i] = "Fizz";
        for (int i = 4; i < n; i += 5) result[i] = "Buzz";
        for (int i = 14; i < n; i += 15) result[i] = "FizzBuzz";
        returnresult; }};Copy the code

summary

Minimum number of BFS updates, note the change from one-dimensional to two-dimensional numbers. With simple questions, less use of residuals and division might improve efficiency.

Refer to the link

There is no