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

Writing in the front

This is the 28th 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 much say the first two questions that begin 28 days!

2021.6.28 A question of the day

815. Bus routes

This problem is to find the minimum number of transfers, that is, as long as the name of a line can cover the place to go. Then list all possible transfers and find the one with the least number of transfers. This is the same idea as BFS. In fact, the idea of this problem is A bit like A*, although I am not familiar with, but to the concept of I will. The first step is to traverse all the routes, categorizing the routes that contain the starting points and the routes that contain the terminal points. Then enumerate a pair of routes, one from the previous set and one from the later set, called route I and route j respectively. Edge [I][j] = edge[j][I] = 1 if two routes have the same station in (I, j).

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        int n = routes.size(a); vector<vector<int>> edge(n, vector<int>(n));
        vector<int> sourceBuses;
        vector<int> targetBuses;
        unordered_map<int, unordered_set<int>> busSites;
        for (int i = 0; i < n; i++) {
            for (int& site:routes[i]) {
                busSites[i].insert(site);
                if (site == source) {
                    sourceBuses.push_back(i);
                }
                if (site == target) {
                    targetBuses.push_back(i); }}}for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int& site:routes[j]) {
                    if (busSites[i].count(site)) {
                        edge[i][j] = edge[j][i] = 1; }}}}vector<int> dis(n, - 1);
        queue<int> que;
        for (int& bus:sourceBuses) {
            dis[bus]=1;
            que.push(bus); 
        }
        while(! que.empty()) {
            int x = que.front(a); que.pop(a);for (int y = 0; y < n; y++) {
                if (edge[x][y] && dis[y] == - 1) {
                    dis[y] = dis[x] + 1;
                    que.push(y); }}}int ret = INT_MAX;
        for (int& bus:targetBuses) {
            if(dis[bus] ! =- 1) {
                ret = min(ret, dis[bus]); }}return ret == INT_MAX ? - 1: ret; }};Copy the code

One of the following questions per day

1796. The second largest number in a string

This question is written according to the title. Go straight to code

class Solution {
public:
    int secondHighest(string s) {
        set<int> sett;
        for(char ch:s)
        {
            if(isdigit(ch))
                sett.insert(static_cast<int>(ch-'0'));
        }
        if(sett.size()"2) return - 1;
        int a=0,b=0;
        for(int i:sett)
        {
            if(i>b) b=i;
            if(b>a) swap(a,b);
        }
        returnb; }};Copy the code

summary

Bus routes are typical of BFS, using points to construct sets and playing with edges made of two points. Set A flag here and try A star and other methods of constructing sets later in this article.

Look at the title to write a simple topic, I also do not ask for speed brush double hundred.

Refer to the link

There is no