leetcode第394场周赛：哈希表专场

字数统计: 3.1k字 | 阅读时长: 13分

2024-04-21

摘要: 本文是 leetcode 第 394 周赛的记录。主要涉及的算法包括哈希表、动态规划、最短路径

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

总览

2024 年 4 月 24 日进行了 leetcode 第 394 场周赛，本场比赛没有赞助公司，奖品是力扣周边，具体如下：

本场比赛的难度偏简单，1 个小时通过 4 题，名次还是普普通通的 372。成绩如下：

本场的前两个题考察的都是哈希表，第三个题的线性DP带有的附加信息也有哈希表的影子，可以算是哈希表专场。第 4 题考查的是 dijkstra 单源最短路径算法的应用，如果有模板的话可以很快解决。

各个题目涉及到的知识点汇总如下：

A题: 哈希集合
- 参考: 哈希表题目分类汇总
B题: 哈希映射
- 参考: 哈希表题目分类汇总
C题: 动态规划
- 参考: 单串线性DP：一个附加信息维度
D题: 最短路径
- 参考: 迪杰斯特拉算法(Dijkstra)

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

3120. 统计特殊字母的数量 I

给你一个字符串 word。如果 word 中同时存在某个字母的小写形式和大写形式，则称这个字母为特殊字母。

返回 word 中特殊字母的数量。

提示：

1 2	1 <= word.length <= 50 word 仅由小写和大写英文字母组成。

示例 1:
输入：word = “aaAbcBC”
输出：3
解释：
word 中的特殊字母是 ‘a’、’b’ 和 ‘c’。

示例 2:
输入：word = “abc”
输出：0
解释：
word 中不存在大小写形式同时出现的字母。

示例 3:
输入：word = “abBCab”
输出：1
解释：
word 中唯一的特殊字母是 ‘b’。

算法：哈希集合

建立一个哈希集合 setting，将 word 中的字符依次插入，过程中哈希集合会自动去重。

然后枚举 $i = 0,\cdots,25$，对应的小写字符和大写字符分别为：

1 2	ch = chr(ord('a') + i) CH = chr(ord('A') + i)

若 ch 与 CH 同时在 setting 中，则答案加 1。

代码 (Python)

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        setting = set(word)
        ans = 0
        for i in range(26):
            ch = chr(ord('a') + i)
            CH = chr(ord('A') + i)
            if ch in setting and CH in setting:
                ans += 1
        return ans

B 题

3121. 统计特殊字母的数量 II

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且每个小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个特殊字母。

返回 word 中特殊字母的数量。

提示：

1 2	1 <= word.length <= 2e5 word 仅由小写和大写英文字母组成。

示例 1:
输入：word = “aaAbcBC”
输出：3
解释：
特殊字母是 ‘a’、’b’ 和 ‘c’。

示例 2:
输入：word = “abc”
输出：0
解释：
word 中不存在特殊字母。

示例 3:
输入：word = “AbBCab”
输出：0
解释：
word 中不存在特殊字母。

算法：哈希映射

建立哈希映射 mapping，其中 mapping[c] 中保存 word 中字符 c 的所有出现位置。然后枚举 word 中的各个字符，依次填入。

然后枚举 $i = 0,\cdots,25$，对应的小写字符和大写字符分别如下（与上题一样）：

1 2	ch = chr(ord('a') + i) CH = chr(ord('A') + i)

若 ch、CH 同时出现在 mapping 中，且 mapping[ch] 最大值比 mapping[CH] 的最小值还小，则答案加 1。

代码(Python)

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        n = len(word)
        mapping = {}
        for i in range(26):
            ch = chr(ord('a') + i)
            CH = chr(ord('A') + i)
            mapping[ch] = []
            mapping[CH] = []
        for i in range(n):
            mapping[word[i]].append(i)
        ans = 0
        for i in range(26):
            ch = chr(ord('a') + i)
            CH = chr(ord('A') + i)
            if len(mapping[ch]) == 0:
                continue
            if len(mapping[CH]) == 0:
                continue
            if max(mapping[ch]) < min(mapping[CH]):
                ans += 1
        return ans

C 题

3122. 使矩阵满足条件的最少操作次数

给你一个大小为 m x n 的二维矩形 grid 。每次操作中，你可以将任一格子的值修改为任意非负整数。完成所有操作后，你需要确保每个格子 grid[i][j] 的值满足：

如果下面相邻格子存在的话，它们的值相等，也就是 grid[i][j] == grid[i + 1][j]（如果存在）。
如果右边相邻格子存在的话，它们的值不相等，也就是 grid[i][j] != grid[i][j + 1]（如果存在）。

请你返回需要的最少操作数目。

提示：

1 2	1 <= n, m <= 1000 0 <= grid[i][j] <= 9

示例 1：
输入：grid = [[1,0,2],[1,0,2]]
输出：0
解释：
矩阵中所有格子已经满足要求。

示例 2：
输入：grid = [[1,1,1],[0,0,0]]
输出：3
解释：
将矩阵变成 [[1,0,1],[1,0,1]] ，它满足所有要求，需要 3 次操作：
将 grid[1][0] 变为 1 。
将 grid[0][1] 变为 0 。
将 grid[1][2] 变为 1 。

示例 3：
输入：grid = [[1],[2],[3]]
输出：2
解释：
这个矩阵只有一列，我们可以通过 2 次操作将所有格子里的值变为 1 。

算法：动态规划

共有 m 行 n 列。

如果单独考虑一列 grid[0..m-1][j]，不论最终变到什么数字，最多也就是把所有元素都变一下，这样需要操作 m 次。

如果该列中出现了某个数字 c，次数为 cnt，则该列变为 c 所需的操作次数就是 m - cnt。这样要找变成哪个数字的操作次数最少，就相当于找该列哪个数字出现最多。

当考虑多列时，就需要考虑相邻列的限制了，两列最终变成的数字不能一样，因此当前列 $j$ 可以变成哪些数字，是取决于上一列 $j-1$ 变成了什么数字。

另一方面，第 $j$ 列的可选数字也仅取决于上一列 $j-1$ 选择的数字，而与更早的列无关。这样我们就发现了一个最优子结构，并做出以下状态定义。

定义 $dp[j][k]$ 表示第 $j$ 列取数字 $k$ 时，第 $0$ 到第 $j$ 列所需的最少操作次数。在这样的状态定义下，答案为 $\min(dp[n-1][0..9])$。

初始化的过程以及状态转移方程中都需要用到单独考虑第 $j$ 列时，若第 $j$ 列改为数字 $k$，需要的操作次数，记其为 op_cnt[j][k]，可以先预处理出来。

第一列的情况为初始条件，初始化过程为 $dp[0][k] = opcnt[0][k]$，状态转移方程如下：

$dp[j][k] = \min\limits_{l\neq k}(dp[j - 1][l]) + opcnt[j][k]$

代码(Python)

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # 预处理 op_cnt：
        # op_cnt[j][k] 表示第 j 列改为 k，所需次数
        op_cnt = [[m for _ in range(10)] for _ in range(n)]
        for j in range(n):
            for i in range(m):
                op_cnt[j][grid[i][j]] -= 1

        # dp[j][k] := 第 j 列取 k 时前 j 列的最小操作数
        dp = [[n * m for _ in range(10)] for _ in range(n)]
        # 初始化
        for k in range(10):
            dp[0][k] = op_cnt[0][k]
        for j in range(1, n):
            for k in range(10):
                for l in range(10):
                    if l == k:
                        continue
                    dp[j][k] = min(dp[j][k], dp[j - 1][l])
                dp[j][k] += op_cnt[j][k]
        ans = m * n
        for k in range(10):
            ans = min(ans, dp[n - 1][k])
        return ans

D 题

3123. 最短路径中的边

给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。

对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，如果 edges[i] 至少在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。

请你返回数组 answer 。

注意，图可能不连通。

提示：

2 <= n <= 5e4
m == edges.length
1 <= m <= min(5e4, n * (n - 1) / 2)
0 <= ai, bi < n
ai != bi
1 <= wi <= 1e5
图中没有重边。

示例 1：

输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
输出：[true,true,true,false,true,true,true,false]
解释：
以下为节点 0 出发到达节点 5 的所有最短路：
路径 0 -> 1 -> 5 ：边权和为 4 + 1 = 5 。
路径 0 -> 2 -> 3 -> 5 ：边权和为 1 + 1 + 3 = 5 。
路径 0 -> 2 -> 3 -> 1 -> 5 ：边权和为 1 + 1 + 2 + 1 = 5 。

示例 2：

输入：n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]
输出：[true,false,false,true]
解释：
只有一条从节点 0 出发到达节点 3 的最短路 0 -> 2 -> 3 ，边权和为 1 + 2 = 3 。

算法：最短路径

首先建立邻接表。

然后通过用堆的方式实现的 dijkstra 最短路径算法，分别走一遍以 start=0 为起点，以及以 end=0 为起点的情况，得到 d 和 rd。其中 d[v] 表示从 start 到 v 的最短路径长度、rd[v] 表示从 v 到 end 的最短路径长度。

假设 dijkstra_heap(g, start, N) 为以上最短路径算法的接口，其中 g 是邻接表、start 为起点，N 为节点数，于是我们只需要调用以下两次即可：

1 2	vector<int> d = dijkstra_heap(g, start, n); vector<int> rd = dijkstra_heap(g, end, n);

上述 dijkstra 算法的原理与实现可以参考文章迪杰斯特拉算法(Dijkstra)，其中有代码模板，这里直接使用代码模板。

d 和 rd 都得到之后，枚举每条边 (u, v, w)，判断该边是否是某条最短路径中的一条边，若满足以下条件之一，则判定成功：

1 2	d[u] + w + rd[v] == d[end] d[v] + w + rd[u] == d[end])

上述判定的含义是，d[end] 表示 start 到 end 的最短路径。如果 uv 是某条最短路径中的一条边，则以下两种情况至少有一种成立：

从 start 先以最短路径 d[u] 走到 u，然后以 w 走到 v，最后再以最短路径 rd[v] 走到 end，其长度之和等于 start 到 end 的最短路径。
从 start 先以最短路径 d[v] 走到 v，然后以 w 走到 u，最后再以最短路径 rd[u] 走到 end，其长度之和等于 start 到 end 的最短路径。

代码(C++)

struct Cmp
{
    bool operator() (const vector<int>& item1, const vector<int>& item2)
    {
        return item1[1] > item2[1]; // 最小堆
    }
};

vector<int> dijkstra_heap(vector<vector<vector<int> > >& g, int start, int N)
{
    // dijkstra 堆实现 $O(E\log V + V\log V)$
    // 不能有负权

    // 存放 start 到各个点的最短路径
    vector<int> d(N + 1, INT_MAX / 3);
    d[start] = 0;

    // 队列元素 (节点编号，到 start 的距离)
    priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
    pq.push({start, 0});
    while(!pq.empty())
    {
        vector<int> cur = pq.top();
        pq.pop();
        if(d[cur[0]] < cur[1])
            continue;
        for(vector<int> son: g[cur[0]])
        {
            if(d[son[0]] <= d[cur[0]] + son[1])
                continue;
            d[son[0]] = d[cur[0]] + son[1];
            pq.push({son[0], d[son[0]]});
        }
    }
    return d;
}

class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        vector<vector<vector<int>>> g(n);
        for(const vector<int>& e: edges)
        {
            g[e[0]].push_back({e[1], e[2]});
            g[e[1]].push_back({e[0], e[2]});
        }

        int start = 0;
        int end = n - 1;
        // d[v] := 从 start 到 v 的最短路径长度
        vector<int> d = dijkstra_heap(g, start, n);
        // rd[v] := 从 v 到 end 的最短路径长度
        vector<int> rd = dijkstra_heap(g, end, n);

        int m = edges.size();
        vector<bool> result(m, false);
        for(int i = 0; i < m; ++i)
        {
            int u = edges[i][0];
            int v = edges[i][1];
            int w = edges[i][2];
            if(d[u] + w + rd[v] == d[end] || d[v] + w + rd[u] == d[end])
                result[i] = true;
        }
        return result;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

leetcode第394场周赛：哈希表专场

总览

A 题

算法：哈希集合

代码 (Python)

B 题

算法：哈希映射

代码(Python)

C 题

算法：动态规划

代码(Python)

D 题

算法：最短路径

代码(C++)