LC weekly 300

6108. Decrypt the message

class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char,char> map;
        map.clear();
        char index = 'a';
        for(auto &x : key) {
            if(x == ' ') continue;
            if(map.count(x)) continue;
            map[x] = index;
            index++;
        }
        
        string res;
        for(auto &x : message) {
            if(x == ' ') res += x;
            else {
                char c = map[x];
                res += c;
            }
        }
        return res;
    }
};

6111. Spiral matrix IV

/**
 * 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>> grid(m, vector<int>(n, -1));
        vector<vector<bool>> sta(m, vector<bool>(n, false));
        for(int i = 0,x = 0,y = 0,d = 0;i < m * n;i++) {
            if(head == nullptr) break;
            grid[x][y] = head->val;
            sta[x][y] = true;
            head = head->next;
            
            int a = x + dx[d],b = y + dy[d];
            if(a < 0 || a == m || b < 0 || b == n || sta[a][b]){
                d = (d + 1) % 4;
                a = x + dx[d],b = y + dy[d];
            }
            x = a,y = b;
        }
        return grid;
    }
};

solution:

        First initialize the matrix to -1, Then do it according to the method of spiral matrix . 

6109. Number of people who know the secret

solution:

        State means :dp[i] It means the first one i God knows the number of Secrets
        State calculation :dp[i] = dp[i - forget] ~ dp[i - delay] The number of people adds up
        Return value answer ：dp[n] Push forward forget The number of people who know the secret accumulates

const int mod = 1e9 + 7;
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        //dp[i] It means the first one i God knows the number of Secrets 
        // The answer is No n Enumerate back forget The number of people in days 
        vector<long> dp(n + 1);
        long ans = 0,num = 0;   //ans Save return value ,num Save the first i God knows the number of Secrets 
        // initialization 
        dp[1] = 1;

        for(int i = 2;i <= n;i++) {
            int in_f = i - forget;
            int in_d = i - delay;   //dp[i] Only by dp[i - forget] ~ dp[i - delay] decision 
            num = 0;
            while(in_d >= 0 && in_d > in_f) {   //in_d > in_f Because I can't share that day 
                num += dp[in_d] % mod;
                in_d--;
            }
            dp[i] = num;      
        }

   		int t = forget;
		while (n >= 0 && t >= 1) {
			ans = (ans + dp[n]) % mod;
			n--;
			t--;
		}
		return (int) ans;
    }
};

6110. The number of incremental paths in the grid graph

solution:

        Used in the competition BFS, Only pass 34/36, Time limit exceeded .

const int N = 1e9 + 7;
class Solution {
public:
    int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};
    typedef pair<int,int> PII;
    vector<vector<int>> g;
    vector<vector<int>> sta;
    int ans = 0;
    int countPaths(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        g = grid;
        sta = vector<vector<int>> (m, vector<int> (n, -1));
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++) {
                bfs(i, j);
            }
        return (ans + m * n) % N;
    }
    
    void bfs(int i,int j) {
        if(sta[i][j] != -1) ans += sta[i][j];
        int res = 0;
        queue<PII> que;
        que.push({i,j});
        while(!que.empty()) {
            auto t = que.front();
            que.pop();
            for(int i = 0;i < 4;i++) {
                int a = t.first + dx[i],b = t.second + dy[i];
                if(a < 0 || a == g.size() || b < 0 || b == g[0].size() || g[a][b] <= g[t.first][t.second]) continue;
                if(sta[a][b] != -1) {
                    res += sta[a][b];
                    continue;
                }
                que.push({a,b});
                res++;
            } 
        }
        sta[i][j] = res + 1;
        ans += res % N;
    }
};

        dfs+ Memory search + Pruning

const int mod = 1e9 + 7;
class Solution {
public:
    int f[1010][1010];
    int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};
    vector<vector<int>> g;
    int countPaths(vector<vector<int>>& grid) {
        memset(f, -1, sizeof(f));   // Initialization status 
        g = grid;
        int m = grid.size(),n = grid[0].size();
        long ans = 0;
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++) {
                ans = (ans + dfs(i, j)) % mod;
            }
        return (int)ans % mod;
    }
    int dfs(int x,int y) {
        if(f[x][y] != -1) return f[x][y];   // prune 
        int res = 1;
        for(int i = 0;i < 4;i++) {
            int a = x + dx[i],b = y + dy[i];
            if(a < 0 || a == g.size() || b < 0 || b == g[0].size() || g[a][b] <= g[x][y]) continue;
            res += dfs(a, b) % mod;
        } 
        f[x][y] = res;
        return f[x][y] % mod;
    }
};