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

Writing in the front

This is the 25th 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 25th day!

2021.6.25 One question of the day

Open the turntable lock

This question feels very difficult, why put in the middle question inside… I’m using bidirectional BFS, which is probably something most people would struggle to come up with, and look at the solution using A*… Well, I guess I didn’t do enough problems.

First according to the meaning of the question to turn the function of the knob, turn the knob, add or subtract one, encounter two ends of the 0 and 9 is a special case, 0 minus a is actually -1, this time should actually subtract -9, in the same way, 9 plus a is actually 10, this time should actually add -9.


int steps(int num)
    {
        if(num == 10)
        return 9 -;
        if(num == - 1)
        return 9 -;
        else return 1;
    }

Copy the code

There is a condition that can be used in this way. The search space of the problem must be the same as the local optimal and the global optimal. Otherwise, it is easy to fall into two pits in the bidirectional search, so that it will never come out.


class Solution {
public:
    int seen[10000];
    int ans = - 1;
    bool dead[10000];
    int q[10000];
    int openLock(vector<string>& deadends, string target) { 
        for(auto d : deadends){
            int tmp = stoi(d);
            dead[tmp] = 1;
        }

        if(dead[0])return - 1;
        if(target == "0000") return 0;
        int tar=stoi(target);
        bfs(tar);
        return ans;
    }
  
    int steps(int num)
    {
        if(num == 10)
        return 9 -;
        if(num == - 1)
        return 9 -;
        else return 1;
    }
  
    void bfs(int target)
    {    
        int hh=0,tt=0;

        q[0] = 0;
        while(hh <= tt){
            auto t = q[hh++];
            int prev = t;

            for(int i = 1 ; i <= 1000 ; i *= 10) {int num = t / i % 10; 
                int temp = t;

                // ++
                int tmp = temp + steps(num + 1) * i;
                if(! seen[tmp] && ! dead[tmp]){ q[tt++] = tmp; seen[tmp] = seen[prev] +1;
                }

                // --
                tmp = temp - steps(num - 1) * i;
                if(! seen[tmp] && ! dead[tmp]){ q[tt++] = tmp; seen[tmp] = seen[prev] +1; }}if(seen[target] ! =0){
                ans = seen[target];
                break; }}}};Copy the code

You can swipe the run, and this is the best looking result.

One question per day below

Offer 07. Rebuild binary tree

This question often appears in the multiple choice questions in the interview questions, hand drawing can also say two sentences, write code is estimated to respond for a while, I estimate that this aspect has to be strengthened.

Give a pre-order traversal and a mid-order traversal to sort out the tree structure. According to the characteristics of the two kinds of traversal, it can be determined that the root node of the whole tree is the first point of the middle-order traversal, and the leftmost leaf node of the whole tree is the first point of the pre-order traversal. And then based on this root and left, we’re basically playing with the concept of left subtrees. Root right and root left are opposite in the absence of right, so I just record a root_and_left and play without “right” for now. The root_and_left is a stack to be paired with another pointer. Index is a pointer to a middle-order traversal that I use to determine who I’m currently looking for a superior relationship to.


/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * /
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(! preorder.size()) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> stk;
        stk.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.size(a); i++) {int preorderVal = preorder[i];
            TreeNode* node = stk.top(a);if(node->val ! = inorder[inorderIndex]) { node->left =new TreeNode(preorderVal);
                stk.push(node->left);
            }
            else {
                while(! stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                    node = stk.top(a); stk.pop(a); inorderIndex++; } node->right =new TreeNode(preorderVal);
                stk.push(node->right); }}returnroot; }};Copy the code

summary

Two-way BFS

Look for the top of the stack. If you can’t find it, take it. If you can find it, go back.

Refer to the link

There is no