[the 300th weekly match of leetcode]

The first 300 Weekly match

Decrypt the message

subject

---

Ideas

• simulation , Just mark it .

---

Code

class Solution {
    
public:
    string decodeMessage(string key, string message) {
    
        string res = "";
        int n = key.size();
        bool st[26] = {
    0};
        map<char, int> mp;
        int now = 0;
        for (int i = 0; i < n; i++) {
    
            if(key[i] == ' ') continue;
            if(!st[key[i] - 'a']) {
    
                st[key[i] - 'a'] = true;
                mp[key[i]] = now;
                now ++;
            }
        }
        for (int i = 0; i < message.size(); i++) {
    
            if(message[i] == ' ') res += ' ';
            else {
    
                res += mp[message[i]] + 'a';
            }
        }
        return res;
    }
};

---

Spiral matrix IV

subject

---

Ideas

• Set the current direction $now$,（0、1、2、3） Corresponding direction array $walk$.
• Set up, down, left and right （lx、rx、ly、ry） Four borders , Adjust when turning the direction .

---

Code

class Solution {
    
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    
        vector<vector<int>> res(m, vector<int>(n, -1));
        ListNode *p = head;
        if(p == nullptr) return res;
        
        vector<int> v;
        while(p) {
     v.push_back(p->val); p = p->next; }
        
        int x = 0, y = -1;
        int walk[4][2] = {
    0, 1, 1, 0, 0, -1, -1, 0};
        int now = 0;
        int lx = 0, rx = m - 1, ly = 0, ry = n - 1;
        
        for (int i = 0; i < v.size(); i++) {
    
            int dx = x + walk[now][0], dy = y + walk[now][1];
            if(dx > rx || dx < lx || dy > ry || dy < ly) {
    
                if(now == 0) lx += 1;
                if(now == 1) ry -= 1;
                if(now == 2) rx -= 1;
                if(now == 3) ly += 1;
                now = (now + 1) % 4;
                dx = x + walk[now][0], dy = y + walk[now][1];
            }
            res[dx][dy] = v[i];
            x = dx, y = dy;
        }
        return res;
    }
};

---

Number of people who know the secret

subject

---

Ideas

• I thought at first , Just take a dynamic array , Simulated deletion 、 The process of adding people . But time , The space cost is bound to be great .

• This needs to be optimized ：

  • It is found that for the $i$ God ： In the current collection Everyone who can share secrets （$i>=x+delay$）, New people added , Their state （ Time is the beginning $i$ God 、delay、forget） All are consistent .（ This is equivalent to that we don't need to add everyone one by one , Instead, you can directly replace it with a variable equivalent ）
  • Find that time is monotonically increasing , Parameters $delay、forget$ Is constant , Then the latter must be later than the former .

• Here I use $map<int,int>$ For storage ： The first $i$ God , The number of $j$.

---

Code

class Solution {
    
public:
    constexpr static int mod = 1e9 + 7;
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        map<int, int> mp;
        int res = 0;
        mp[1] = 1;
        for (int i = 2; i <= n; i++) {
    
            int cnt = 0;
            for (auto &x: mp) {
    
                int a = x.first, b = x.second;
                if(i >= a + forget) {
     mp.erase(a); continue; }
                if (i >= a + delay) cnt = (cnt + b) % mod;
            }
            mp.insert({
    i, cnt});
        }
        for (auto &x: mp) res = (res + x.second) % mod;
        return res % mod;
    }
};

---

The number of incremental paths in the grid graph

subject

---

Ideas

• Memory search

Consider the example illustration
3->4：1
1->3、1->3->4： 2

Adjacent can arrive , State shift $dp[i][j]=dp[x][y]+1$.

---

Code

class Solution {
    
public:
    constexpr static int mod = 1e9 + 7;
    int n, m;
    int walk[4][2] = {
    0, 1, 1, 0, 0, -1, -1, 0};
    
    int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp) {
    
        int s = 0;
        for (int i = 0; i < 4; i++) {
    
            int dx = x + walk[i][0];
            int dy = y + walk[i][1];
            if(dx >= n || dx < 0 || dy >= m || dy < 0) continue;
            if(grid[x][y] >= grid[dx][dy]) continue;
            if(dp[dx][dy]) {
     s += dp[dx][dy] + 1; continue; }
            s += dfs(dx, dy, grid, dp) + 1;
            s %= mod;
        }
        dp[x][y] = (s + dp[x][y]) % mod;
        return dp[x][y];
    }
    
    int countPaths(vector<vector<int>>& grid) {
    
        n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < m; j++) {
    
                if(!dp[i][j]) {
    
                    dfs(i, j, grid, dp);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res = (res + dp[i][j] + 1) % mod;
        return res;
    }
};

---