LeetCode周赛300，差点AK，刚拿到的勋章要丢了……

大家好，日拱一卒，我是梁唐。

今天是周一，我们来聊聊昨天上午的LeetCode周赛。

这一次是LeetCode周赛第300场，是由未来汽车赞助的。前1000名都能获得内推的机会，第一名还能获得车模……不得不说还是挺慷慨的。

这次的赛题质量不错，难度梯度不错，总体来说比以往的几场要稍难一些。这一次由于老梁没睡好影响了发挥，赛前好不容易拿到的勋章要丢了……丢之前纪念一下orz。

逛评论区的时候看到一条很有意思的评论，承包了我一整天的笑点……

好了，言归正传，让我们看看本次的题目吧。

解密消息

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
2. 将替换表与普通英文字母表对齐，形成对照表。
3. 按照对照表 替换 message 中的每个字母。
4. 空格 ' ' 保持不变。

• 例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。

返回解密后的消息。

题解

这题难度不大，主要是读题的时候需要仔细。这题当中的字母映射是反向影响，比如key中是happy，第一字符是h，这表示将密文中的h映射成a。之后首次出现的字母依次映射成bcd...。

很容易想到，我们可以使用一个数组u存储映射关系。因为最多只有26个字母，也就是26个映射，没有必要使用map，用数组即可。下标0表示字母a，下标25表示字母z。u[3]=0，表示将字母d映射成字母a。

由于映射是依次进行的，所以我们还需要使用一个变量来存储下一个被映射的字母。

class Solution {
public:
    string decodeMessage(string key, string message) {
        int u[30];
        memset(u, -1, sizeof u);
        
        int idx = 0;
        for (char c : key) {
            if (c == ' ' || u[c - 'a'] >= 0) continue;
            u[c-'a'] = idx++;
        }
        
        string ret = "";
        for (int i = 0; i < message.length(); i++) {
            int c = message[i] - 'a';
            if (message[i] == ' ' || u[c] == -1) ret.push_back(message[i]);
            else ret.push_back((char)('a' + u[c]));
        }
        return ret;
    }
};

同样的逻辑大佬写只要几行：

class Solution {
public:
    string decodeMessage(string key, string message) {
        int ord[26] = {0}, cnt = 0;
        for (char c : key) if (c >= 'a' && c <= 'z' && ord[c - 'a'] == 0) ord[c - 'a'] = ++cnt;
        for (char &c : message) if (c >= 'a' && c <= 'z') c = ord[c - 'a'] - 1 + 'a';
        return message;
    }
};

螺旋矩阵 IV

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

题解

螺旋矩阵以前我们校赛的时候出过，几乎是新手的噩梦。虽然题意很简单，但是要实现还是挺麻烦的。因为遍历的顺序一直在改变。

但如果我们仔细分析，会发现方向改变都是有迹可循的。每一次都是在边界的时候改变方向，并且每一次改变方向都是顺时针旋转90度。这里的边界有两种情况，一种是矩阵的边界，还有一种是已经填写的矩阵。

比如我们按照这个顺序向上遍历的时候，遇到了3，3是之前填的数字，也可以被视为是边界。

所以我们只需要记录一下当前的方向，每次在遇到边界的时候旋转90度即可。本题非常友好，告诉了我们链表当中的元素值都是非负数，那么我们可以将矩阵初始化成-1，这样我们只需要判断一下矩阵中的值是否大于等于0就能知道矩阵的某个位置有没有被遍历过了。

/**
 * 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:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ret(m, vector<int>(n, -1));
        ListNode* ptr = head;
        int i = 0, j = 0;
        int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, fx = 0;
        while (ptr != nullptr) {
            ret[i][j] = ptr->val;
            int ii = i + dir[fx][0], jj = j + dir[fx][1];
            if (ii == -1 || ii == m || jj == -1 || jj == n || ret[ii][jj] != -1) {
                fx = (fx + 1) % 4;
                ii = i + dir[fx][0];
                jj = j + dir[fx][1];
            }
            i = ii, j = jj;
            ptr = ptr->next;
        }
        return ret;
    }
};

知道秘密的人数

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

题解

这题看上去非常棘手，因为情况很复杂，有人要传播秘密，又有人会忘记秘密，并且被传播秘密的人又不能立即去传播秘密……

面对这样的题目，最好的方法就是把所有的变量都列举清楚，无论是推导的时候还是编码的时候，可以简化不少困难。

首先我们来分析一下当前知道秘密的人，这部分可以简单分成两拨。一拨人是有能力传播秘密的，一拨人是没有能力传播秘密的。这里面又可以细分，比如知道秘密的有些是今天才刚刚被传播的，有些是前几天就已经知道秘密但还没有能力传播的。

所以我们还需要根据时间明确一下，在此之前，我们先划分一下人群。我们把某天有能力传播秘密的当做是正式会员，记作mem(member)。把某天刚知道秘密但还不能传播的称作是候选人，记作cand(candidate)。把某天遗忘秘密的人称作是退休，记作retire。

接下来，我们分析一下这几个量之间的变化情况。

首先是正式会员，第i的会员数量mem[i]它的来源有两种，一种是之前就已经是正式会员并且延续到今天的，这个很简单，其实就是昨天的正式会员数量mem[i-1]。还有一种是今天刚刚知道秘密满delay天，刚刚转正的，这部分也不难，其实就是delay天前刚刚知道秘密的候选人数量，即cand[i-delay]。但还没完，还有一个去向，就是今天退休的人数，是retire[i]。

所以对于第i天来说，正式会员的数量是mem[i-1] + cand[i-delay] - retire[i]。

接着，我们来分析第i天刚刚知道秘密的人的数量。你会惊人地发现，它其实就是当天正式会员的数量。因为正式会员每人都能传播秘密给一个人，所以当天新接收秘密人的数量就是当天正式会员的数量。所以cand[i] = mem[i]。

接着，我们考虑退休的情况。虽然我们知道某天的正式会员的数量，但是它们都是不同时间转正的，很难直接计算退休的时间。因此我们需要转换视角，从知道秘密开始入手。退休的时间就是知道秘密之后的第forget天。我们已经知道当天新增的知道秘密的人数是cand[i]，那么forget天之后退休的人数必然也是cand[i]，所以retire[i+forget] = cand[i]。

但到这里有一个问题，我们要求某天所有知道秘密的人数时少了一部分。少了哪一部分呢？我们现在只有当前能传播的人数以及刚刚知道秘密的人数，少了那些之前已经知道秘密但今天还没能传播的人数。这部分人数怎么算呢？其实就是把每天新增知道秘密的人数加起来，再减去当天转正的人数。我们用totc来记录当前所有没转正的人数，即totc[i] = totc[i-1] + cand[i] - cand[i-delay]。

其实我们可以省掉一个数组，前面也说了cand[i] = mem[i]，这两个数组可以合并。但推理的时候，这两个数组代表的含义是不同的，分开来思路会更清晰一些。

class Solution {
public:
    int peopleAwareOfSecret(int n, int d, int f) {
        vector<int> cand(n+4, 0), mem(n+4, 0), retire(n+4, 0), totc(n+4, 0);
        int Mod = 1e9 + 7;
        retire[f+1] = 1;
        mem[d] = 1;
        
        for (int i = d+1; i <= n; i++) {
            cand[i] = ((mem[i-1] + cand[i-d] - retire[i]) % Mod + Mod) % Mod;
            if (i + f < n+1) retire[i+f] = cand[i];
            mem[i] = ((mem[i-1] + cand[i-d] - retire[i]) % Mod + Mod) % Mod;
            totc[i] = ((totc[i-1] + cand[i] - cand[i-d]) % Mod + Mod) % Mod;
        }
        
        return ((totc[n] + mem[n]) % Mod + Mod) % Mod;
    }
};

网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

题解

非常遗憾，这题在比赛的时候没能做出来。有想到一个方法，但是超时了。

我们简单分析一下，这题最大的数据范围是1000 x 1000。如果是递增矩阵，即一个元素的右边和下边的元素都比它大左侧和上方的元素都比它小的矩阵，如下：

对于这样的矩阵而言，能够找到的递增序列不仅数量多，而且长度也很长。如果一一遍历的话，一定会超时。如果做题经验比较丰富的话，到这里应该已经反应过来了，十有八九要通过动态规划来解决。我们不再关心每一条路径，只关心数量更少的状态，以及状态之间的转移关系，通过状态的分析得到最终的答案。

这题的状态也不难找，我们可以用dp[i][j]表示以坐标(i, j)为结尾的递增串的数量。转移的方式也很简单，我们只要看一下它四个方向上的数字是否比它小，如果比它小就存在转移关系。

但麻烦的点在于它四个方向上的位置不一定得到了最终的结果，它四周的结果又依赖它的四周，这样的依赖还会传递……

有没有什么办法可以解决这个问题呢？

其实是不难想到的，有一种算法可以天然解决这种依赖传递的问题，它就是递归。我们要求dp[i][j]需要先求dp[i+1][j]，我们要求dp[i+1][j]可能又需要先求dp[i+2][j]……没关系，使用递归我们可以一层一层递归下去，由于题目要求严格递增序列，这样的依赖一定是有尽头的，所以递归深度是有限的，不可能无限递归。

其次是已经递归过的位置就不用再求一次了，我们可以把每个位置的结果都存下来。这种做法叫做记忆化搜索，也是一种非常常见的技巧。

这道题其实挺直接的，只要能想到记忆化搜索，就算是搞定了，基本上没有什么弯弯绕。大家直接看代码就行：

class Solution {
public:
    int countPaths(vector<vector<int>>& grid) {
        int Mod = 1e9 + 7;
        typedef pair<int, int> pii;
        queue<pii> que, nque;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<long long>> f(m, vector<long long>(n, 0));
    
        int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        function<long long(int, int)> dp = [&](int x, int y) -> long long {
            if (f[x][y] > 0) return f[x][y];
            f[x][y] = 1;
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny == n || grid[x][y] <= grid[nx][ny]) {
                    continue;
                }
                f[x][y] = (f[x][y] + dp(nx, ny)) % Mod;
            }
            return f[x][y];
        };
        
        int ret = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret = (ret + dp(i, j)) % Mod;
            }
        }
        
        return ret;
    }
};

虽然比赛的时候发挥不太好，但本次比赛的题目质量还是可以的，有一定的阶梯性，对思维的锻炼也很不错。推荐错过比赛的小伙伴可以尝试一下赛后练习，或者模拟比赛。

好了，我们下周再见吧~