算法练习专栏——leetcode——leetcode394周赛

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

原题

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

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

示例 1:

输入：word = “aaAbcBC”

输出：3

解释：

word 中的特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = “abc”

输出：0

解释：

word 中不存在大小写形式同时出现的字母。

示例 3:

输入：word = “abBCab”

输出：1

解释：

word 中唯一的特殊字母是 'b'。

提示：

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

思路

​ 略

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSpecialChars(string word) {
        int a[30], b[30];
        for (int i = 0; i < word.length(); i++) {
            int c = word[i];
            if ('a' <= c && c <= 'z') {
                a[c - 'a'] ++;
            } else {
                b[c - 'A'] ++;
            }
        }
        int res = 0;
        for (int i = 0; i <= 25; i++) {
            if (a[i] && b[i]) res++;
        }
        return res;
    }
};

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

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

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

示例 1:

输入：word = “aaAbcBC”

输出：3

解释：

特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = “abc”

输出：0

解释：

word 中不存在特殊字母。

示例 3:

输入：word = “AbBCab”

输出：0

解释：

word 中不存在特殊字母。

提示：

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

思路

​ 略

代码

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
class Solution {
public:
    int numberOfSpecialChars(string word) {
        int a[30], b[30];
        vector<vector<int>> p1, p2;
        p1.resize(30);
        p2.resize(30);
        
        for (int i = 0; i < word.length(); i++) {
            int c = word[i];
            if ('a' <= c && c <= 'z') {
                a[c - 'a'] ++;
                p1[c - 'a'].push_back(i);
            } else {
                b[c - 'A'] ++;
                p2[c - 'A'].push_back(i);
            }
        }
        
        for (auto k : p2[0]) cout << k << '\n';
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (a[i] && b[i]) {
                // cout << p1[i][p1[i].size() - 1] << " " << p2[i][0] << '\n';
                if (p1[i][p1[i].size() - 1] < p2[i][0]) res++;
            }
        }
        
        
        return res;
    }
};

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

原题

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

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

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

示例 1：

输入：grid = [[1,0,2],[1,0,2]]

输出：0

解释：

img

矩阵中所有格子已经满足要求。

示例 2：

输入：grid = [[1,1,1],[0,0,0]]

输出：3

解释：

img

将矩阵变成 [[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

解释：

img

这个矩阵只有一列，我们可以通过 2 次操作将所有格子里的值变为 1 。

提示：

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

思路

​ DP

代码

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
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        // 预处理把第 j 列都变成数字 k 的操作数
        int g[m][10];
        memset(g, 0, sizeof(g));
        for (int j = 0; j < m; j++) 
            for (int k = 0; k < 10; k++)
            	for (int i = 0; i < n; i++) {
                    if (grid[i][j] != k) g[j][k]++;
                }

        const int INF = 1e9;
        int f[m][10];
        for (int j = 0; j < m; j++) 
            for (int k = 0; k < 10; k++) 
                f[j][k] = INF;
        
        for (int k = 0; k < 10; k++) f[0][k] = g[0][k];
        
        // DP 方程
        for (int j = 1; j < m; j++) 
            for (int k = 0; k < 10; k++)
            	for (int kk = 0; kk < 10; kk++) 
                    if (k != kk) f[j][k] = min(f[j][k], f[j - 1][kk] + g[j][k]);

        int ans = INF;
        for (int k = 0; k < 10; k++) ans = min(ans, f[m - 1][k]);
        return ans;
    }
};

100276、最短路径中的边

原题

给你一个 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 。

注意，图可能不连通。

示例 1：

img

输入：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：

img

输入：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 。

提示：

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

思路

image-20240421192704948

注意：一定要倒着来搜，因为你从开始地方搜到的位置虽然一定是最短路径，但是终点并不一定是n-1这个点，这需要特别注意！！！

补充只知识点： INT_MAX和LLONG_MAX均存在与头文件limits.h中，分别表示int类型和long long类型的最大值。！！！！！！

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        vector<vector<tuple<int, int, int>>> g(n);
        for (int i = 0; i < edges.size(); i++) {
            auto& e = edges[i];
            int x = e[0], y = e[1], w = e[2];
            g[x].emplace_back(y, w, i);
            g[y].emplace_back(x, w, i);
        }

        // 板子
        vector<long long> dis(n, LLONG_MAX);
        dis[0] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [dx, x] = pq.top();
            pq.pop();
            if (dx > dis[x]) {
                continue;
            }
            for (auto [y, w, _] : g[x]) {
                int new_dis = dx + w;
                if (new_dis < dis[y]) {
                    dis[y] = new_dis;
                    pq.emplace(new_dis, y);
                }
            }
        }

        vector<bool> ans(edges.size());
        // 图不连通
        if (dis[n - 1] == LLONG_MAX) {
            return ans;
        }

        // 从终点出发 DFS
        vector<int> vis(n);

        // 内嵌式dfs函数编写学习
        function<void(int)> dfs = [&](int y) {
            vis[y] = true;
            for (auto [x, w, i] : g[y]) {
                if (dis[x] + w != dis[y]) {
                    continue;
                }
                ans[i] = true;
                if (!vis[x]) {
                    dfs(x);
                }
            }
        };

        
        dfs(n - 1);
        return ans;
    }
};