[数据结构与算法]【LeetCode第 300 场周赛】

第 300 场周赛

解密消息

题目

思路

• 模拟，打标记即可。

代码

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;
    }
};

螺旋矩阵 IV

题目

思路

• 设定当前方向 $now$，（0、1、2、3）对应方向数组 $walk$。
• 设定上下左右（lx、rx、ly、ry）四个边界，在转向方向的时候进行调整。

代码

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;
    }
};

知道秘密的人数

题目

思路

• 一开始想的，就是直接拿个动态数组，模拟删人、加人这个过程。但是时间，空间开销必然很大。

• 对此需要进行优化：

  • 发现对于第 $i$ 天：当前集合中所有能分享秘密的人（$i>=x+delay$），加出来的新人，他们的状态（时间都是起始第 $i$ 天、delay、forget）全部是一致的。（这里就等价于我们不需要将所有人一个一个都加入，而是直接用一个变量等价替换即可）
  • 发现时间是单调递增，参数 $delay、forget$ 是固定的，那么后来者状态一定晚于前者。

• 这里我用 $map<int,int>$ 进行存储： 第 $i$ 天，人数 $j$。

代码

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;
    }
};

网格图中递增路径的数目

题目

思路

• 记忆化搜素

考虑样例图解
3->4：1
1->3、1->3->4： 2

相邻能抵达，状态转移 $dp[i][j]=dp[x][y]+1$。

代码

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;
    }
};