300th weekly match - leetcode

The first 300 Weekly match - Power button （LeetCode）

2325. Decrypt the message

Here is the string key and message , Represent an encryption key and an encrypted message respectively . Decrypt message The steps are as follows ：

Use key in 26 The order of the first occurrence of English lowercase letters is used to replace the letters in the table The order .
Align the replacement table with the common English alphabet , Form a comparison table .
According to the comparison table Replace message Every letter in .
Space ’ ’ remain unchanged .
for example ,key = “happy boy”（ The actual encryption key will contain every letter in the alphabet At least once ）, Accordingly , You can get some comparison tables （‘h’ -> ‘a’、‘a’ -> ‘b’、‘p’ -> ‘c’、‘y’ -> ‘d’、‘b’ -> ‘e’、‘o’ -> ‘f’）.
Returns the decrypted message .

 Examples 1：
 Input ：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
 Output ："this is a secret"
 explain ： The comparison table is shown in the above figure .
 extract  "the quick brown fox jumps over the lazy dog"  The first occurrence of each letter in can get a replacement table .

Problem analysis

Direct traversal key character string , Combine these characters with 26 The mapping of letters is stored in an array or hash table , As long as you traverse to a character, this character has not been mapped , Just follow 26 The order of the letters gives him a mapping .

And then traverse the string message, Convert the characters according to the mapping of the record and return .

AC Code

class Solution {
public:
    string decodeMessage(string key, string message) {
        int n=key.size();
        char c='a';
        unordered_map<char,char>mymap;
        for(int i=0;i<n;i++)
        {
            if (key[i] == ' ')continue;
            if(c>'z')break;
            if(mymap[key[i]]==0)
            {
                mymap[key[i]]=c++;
            }
        }
        string s;
        for(auto i:message)
        {
            if(i==' ')s+=i;
            else s+=mymap[i];
        }
        return s;
    }
};

2326. Spiral matrix IV

Here are two integers ：m and n , Represents the dimension of the matrix .

Another head node of the integer linked list head .

Please generate a size of m x n The spiral matrix of , The matrix contains all integers in the linked list . The integers in the linked list are from the matrix top left corner Start 、 Clockwise Press screw Fill in order . If there are still remaining spaces , Then use -1 fill .

Return the generated matrix .

 Example  1：
 Input ：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
 Output ：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
 explain ： The figure above shows how the integers in the linked list are arranged in the matrix .
 Be careful , The remaining spaces in the matrix are used  -1  fill .

Problem analysis

The difficulty lies mainly in the spiral traversal array , We can prepare an array of directions first , According to right （0,1） Next （1,0） Left （0,-1） On （-1,0）, In this way, we first traverse the array in the right direction , When you move to the boundary or to the lattice you have traversed before, you change the direction .

The remaining positions are set to -1, We can set all the matrices to -1, After traversing, don't worry about the rest of the grid .

AC Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>>v(m,vector<int>(n,-1));
        int d=0,x=0,y=0;
        while(head)
        {
            v[x][y]=head->val;
            head=head->next;
            int a=x+dx[d],b=y+dy[d];
            if(a>=m||a<0||b<0||b>=n||v[a][b]!=-1)
            {
                d=(d+1)%4;
                a=x+dx[d],b=y+dy[d];
            }
            x=a,y=b;
            
        }
        return v;
    }
};

2327. Number of people who know the secret

In the 1 God , A man discovered a secret .

Give you an integer delay , It means that everyone will find the secret delay After heaven , Every day To a new person Share Secret . I'll give you an integer at the same time forget , It means that everyone is discovering secrets forget Days later forget The secret . A person You can't Share secrets on and after the day you forget them .

Give you an integer n , Please go back to n At the end of the day , Number of people who know the secret . Because the answer could be big , Please put the result to 109 + 7 Remainder After the return .

 Example  1：

 Input ：n = 6, delay = 2, forget = 4
 Output ：5
 explain ：
 The first  1  God ： Suppose the first person is  A .（ One knows the secret ）
 The first  2  God ：A  Is the only one who knows the secret .（ One knows the secret ）
 The first  3  God ：A  Share the secret with  B .（ Two people know the secret ）
 The first  4  God ：A  Share the secret with a new person  C .（ Three people know the secret ）
 The first  5  God ：A  Forget the secret ,B  Share the secret with a new person  D .（ Three people know the secret ）
 The first  6  God ：B  Share the secret with  E,C  Share the secret with  F .（ Five people know the secret ）

Problem analysis

Set dynamic programming array f,f[i] It means ： The first i The new number of people who know secrets is f[i].

The first i The number of people added in days , That is the first. i Days ago forge Day to delay God knows the total number of people .

The first n God knows the total number of Secrets , That is the first. n Days ago forge Day to delay Days of f[i] The sum of .

AC Code

class Solution {
public:
    int MOD=1e9+7;
    typedef long long ll;
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<ll>f(n + 1);
        f[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            int j = i - delay;
            while (j > 0 && i - j < forget)
            {
                f[i] = (f[i] + f[j]) % MOD;
                j--;
            }
        }
        ll res = 0;
        for (int i = 0; i < forget; i++)
        {
            res = (res + f[n - i]) % MOD;
        }
        return res;
    }
};

2328. The number of incremental paths in the grid graph

To give you one m x n Integer grid graph of grid , You can move from a grid to 4 Any lattice adjacent in two directions .

Please return to the grid from arbitrarily Grid departure , achieve arbitrarily lattice , And the number in the path is Strictly increasing Number of paths for . Because the answer could be big , Please correct the results 109 + 7 Remainder After the return .

If the grids accessed in the two paths are not exactly the same , Then they are regarded as two different paths .

 Example  1：

 Input ：grid = [[1,1],[3,4]]
 Output ：8
 explain ： Strictly incremental paths include ：

-  The length is  1  The path of ：[1],[1],[3],[4] .
-  The length is  2  The path of ：[1 -> 3],[1 -> 4],[3 -> 4] .
-  The length is  3  The path of ：[1 -> 3 -> 4] .
   Number of paths is  4 + 3 + 1 = 8 .

Problem analysis

Memory search .

Start at each point dfs, See how many different paths can be extended from a point , Record in a two-dimensional array f in ,f[i] [j] Said to （i,j) The path to the starting point is f[i] [j] strip .

dfs When , If the next grid （x,y） The value of is greater than the current grid （i,j）, It means that the current grid can be extended to that grid , that f[i] [j] You can get more f[x] [y] Path out , And then to [x] [y] Continue as a starting point dfs. The final result is a two-dimensional array f The total sum of .

AC Code

class Solution {
public:
    typedef long long ll;
    int MOD=1e9+7;
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},n,m;
    ll f[1050][1050];
    vector<vector<int>>v;
    ll dp(int x,int y)
    {
        if(f[x][y]!=0)return f[x][y];
        f[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<m&&v[a][b]>v[x][y])
            {
                f[x][y]=(f[x][y]+dp(a,b))%MOD;
            }
        }
        return f[x][y];
    }
    int countPaths(vector<vector<int>>& grid) {
        v=grid;
        n=grid.size(),m=grid[0].size();
        ll res=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                res=(res+dp(i,j))%MOD;
            }
        }
        return res;
    }
};