算法leetcode

leetcode第300场周赛：逆向思维的思想

字数统计: 3k字   |   阅读时长: 12分
,

摘要: 本文是 leetcode 第 300 周赛的记录。主要涉及的算法包括哈希表、模拟、逆向思维、动态规划。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

这是 leetcode 第 300 场周赛，本场比赛由蔚来赞助，前 1000 名可获得简历内推，力度还是很大的。

本场比赛主要涉及到的算法是哈希表、模拟、逆向思维、动态规划。这次的题目相对比较简单，其中第 3 题算是比较有亮点，考察了逆向思维。第 4 题如果对动态规划比较熟的话，可以秒做。成绩如下：

4 道题涉及到的算法点，以及参考链接如下：

周赛历史记录: 【连载】leetcode周赛

A题

给你字符串 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’）。

返回解密后的消息。

1
2
3
4
5
6
提示：
26 <= key.length <= 2000
key 由小写英文字母及 ' ' 组成
key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
1 <= message.length <= 2000
message 由小写英文字母和 ' ' 组成

示例 1：
输入：key = “the quick brown fox jumps over the lazy dog”, message = “vkbs bs t suepuv”
输出：”this is a secret”
解释：对照表如上图所示。
提取 “the quick brown fox jumps over the lazy dog” 中每个字母的首次出现可以得到替换表。

示例 2：
输入：key = “eljuxhpwnyrdgtqkviszcfmabo”, message = “zwx hnfx lqantp mnoeius ycgk vcnjrdb”
输出：”the five boxing wizards jump quickly”
解释：对照表如上图所示。
提取 “eljuxhpwnyrdgtqkviszcfmabo” 中每个字母的首次出现可以得到替换表。

算法: 哈希表

用一个长为 26 的数组，下标分别代表 a ~ z 这 26 个小写字母，数组的值表示对应的解密后的字母。遍历 key 的每个字符，如果该字符在数组中没有更新过，则更新，否则就跳过。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string decodeMessage(string key, string message) {
        vector<char> mapping(26, '#');
        char i = 'a';
        for(const char &ch: key)
        {
            if(ch == ' ')
                continue;
            if(mapping[ch - 'a'] != '#')
                continue;
            mapping[ch - 'a'] = i++;
        }
        string result = message;
        int n = result.size();
        for(int i = 0; i < n; ++i)
        {
            if(message[i] == ' ')
                continue;
            result[i] = mapping[message[i] - 'a'];
        }
        return result;
    }
};

B题

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

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

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

返回生成的矩阵。

1
2
3
4
5
提示：
1 <= m, n <= 1e5
1 <= m * n <= 1e5
链表中节点数目在范围 [1, m * n] 内
0 <= Node.val <= 1000

示例 1：
输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。

示例 2：
输入：m = 1, n = 4, head = [0,1,2]
输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。
注意，矩阵中剩下的空格用 -1 填充。

算法: 模拟

本题是螺旋矩阵这个系列的题目，要按要求进行打印，属于模拟题。

打印过程是从外到内一圈一圈进行的，对于某一圈打印的过程，横纵坐标的最大值最小值是用于判断边界关键信息。当一圈打印结束，需要更新横纵坐标的最大值最小值这个关键信息。

代码(C++)

dx 和 dy 中各个数值的顺序需要注意，代码中的顺序正好是向右，向下，向左，向上这个顺序，当判断出界需要该方向的时候，直接 d++ 就可以了，详见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> result(m, vector<int>(n, -1));
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        // 范围
        int up = 0, down = m - 1, left = 0, right = n - 1;
        int d = 0;
        int x = 0, y = 0;
        ListNode *node = head;
        while(node != nullptr)
        {
            result[x][y] = node -> val;
            if(x + dx[d] == up && y + dy[d] == left)
            {
                d = 0;
                ++up;
                --down;
                ++left;
                --right;
            }
            else if(x + dx[d] < up || x + dx[d] > down || y + dy[d] < left || y + dy[d] > right)
            {
                d++;
            }
            x = x + dx[d];
            y = y + dy[d];
            node = node -> next;
        }
        return result;
    }
};

C题

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

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

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

1
2
3
提示：
2 <= n <= 1000
1 <= delay < forget <= n

示例 1：
输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：
输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

算法: 逆向思维

一个人如果在第 x 天知道秘密，则第 [x + delay, x + forgot - 1] 天这个范围此人会分享该秘密。

如果采用逆向思维，那么在第 i 天时，第 [i - delay, i - forgot + 1] 天知道的人会在当前的第 i 天分享，同时第 i - forgot 天知道秘密的人会在当前的第 i 天忘掉。

这样的话，我们就可以知道第 i 天这一天会增加多少新知道秘密的人，这个数再加上第 1 ~ i-1 天知道秘密且尚未忘记的人数，即为第 i 天时知道秘密的人数。

第 1 天，有一个人知道。

从第二天开始，[2, n] 中的每一天我们都判断一次有多少人在这一天发生分享。

假设当前进行到第 i 天，我们只需要判断 [i - delay, i - forgot + 1] 中的每一天各有多少新增知道的人即可，这些数目的总和就是当天新知道秘密的人数。同时，i - forget 这一天知道秘密的人会遗忘，因此人数要清空。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int MOD = 1e9 + 7;
        using ll = long long;
        vector<int> additional(n);
        additional[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(i - forget >= 0)
                additional[i - forget] = 0;
            int left = i - forget + 1;
            int right = i - delay;
            if(right < 0)
                continue;
            for(int j = max(left, 0); j <= right; ++j)
            {
                additional[i] = ((ll)additional[i] + additional[j]) % MOD;
            }
        }

        int ans = 0;
        for(int x: additional)
            ans = ((ll)ans + x) % MOD;
        return ans;
    }
};

D题

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

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

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

1
2
3
4
5
6
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 1e5
1 <= grid[i][j] <= 1e5

示例 1：
输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：

  • 长度为 1 的路径：[1]，[1]，[3]，[4] 。
  • 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
  • 长度为 3 的路径：[1 -> 3 -> 4] 。
    路径数目为 4 + 3 + 1 = 8 。

示例 2：
输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：

  • 长度为 1 的路径：[1]，[2] 。
  • 长度为 2 的路径：[1 -> 2] 。
    路径数目为 2 + 1 = 3 。

算法: 动态规划

本题的思路与 329. 矩阵中的最长递增路径 几乎一样，都是在矩阵中找递增路径，那个题是求最长的递增路径，本题是求递增路径个数。

对矩阵中的每一个位置，我们求一次以该位置结尾的递增路径有多少条，将所有位置的结果加起来就得到最终的递增路径条数。

对于任意位置，首先它自己构成一个长度为 1 的递增路径。然后就要看四个方向中有没有比该位置的值小的，如果有，则可以从对应的方向走到当前位置形成递增路径。

综上，动态规划算法那如下：

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := 以 (i, j) 为结尾的递增路径条数。

答案：
sum(dp)

初始化：
如果四个方向都没有比当前元素值小的，则 dp[i][j] = 1

状态转移：
dp[i][j] = 1 + sum(dp[x][y])
其中 (x, y) 是 (i, j) 的相邻点，且 grid[x][y] < grid[i][j]

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int countPaths(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        // dp[i][j] := 以 (i, j) 为终点的严格递增路径条数
        dp = vector<vector<int>>(n, vector<int>(m, -1));
        int ans = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                ans = ((ll)ans + dfs(i, j, grid)) % MOD;
        return ans;
    }

    int n, m;
    vector<vector<int>> dp;
    using ll = long long;
    const int MOD = 1e9 + 7;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    int dfs(int i, int j, const vector<vector<int>>& grid)
    {
        if(dp[i][j] != -1)
            return dp[i][j];
        dp[i][j] = 1;
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if(grid[x][y] >= grid[i][j])
                continue;
            dp[i][j] = ((ll)dp[i][j] + dfs(x, y, grid)) % MOD;
        }
        return dp[i][j];
    }
};
Share