第 394 场 LeetCode 周赛题解

A 统计特殊字母的数量 I

哈希：遍历然后枚举

class Solution {
  public:
    int numberOfSpecialChars(string word) {
        unordered_map<char, int> m;
        for (auto ch : word)
            m[ch] = 1;
        int res = 0;
        for (char ch = 'a'; ch <= 'z'; ch++)
            if (m.count(ch) && m.count('A' + ch - 'a'))
                res++;
        return res;
    }
};

B count-the-number-of-special-characters-ii/

哈希：遍历记录各小写字母的最后出现下标，及各大写字母的第一次出现的下标，然后枚举

class Solution {
  public:
    int numberOfSpecialChars(string word) {
        unordered_map<char, int> m;
        for (int i = 0; i < word.size(); i++)
            if (word[i] >= 'a' && word[i] <= 'z' || m.find(word[i]) == m.end())
                m[word[i]] = i;
        int res = 0;
        for (char ch = 'a'; ch <= 'z'; ch++)
            if (m.count(ch) && m.count('A' + ch - 'a') && m[ch] < m['A' + ch - 'a'])
                res++;
        return res;
    }
};

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

动态规划：设 $p[i][j]$ 为使 $grid$ 的前 $i+1$ 列行成的子矩阵满足条件的且最后一列都为 $j$ 的最少操作数，最终答案为 m i n { p [ n − 1 ] [ j ]    ∣    0 ≤ j ≤ 9 } min\{ p[n-1][j] \;|\; 0\le j\le 9 \} min{p[n−1][j]∣0≤j≤9}

class Solution {
  public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> col(n, vector<int>(10));//col[i][j]: 第i列中j的数目
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                col[j][grid[i][j]]++;
        vector<vector<int>> p(n, vector<int>(10));
        for (int j = 0; j < 10; j++)
            p[0][j] = m - col[0][j];
        for (int j = 1; j < n; j++) {
            for (int cur = 0; cur < 10; cur++) {
                p[j][cur] = INT32_MAX;
                for (int last = 0; last < 10; last++)//枚举前一行
                    if (last != cur)
                        p[j][cur] = min(p[j][cur], p[j - 1][last] + m - col[j][cur]);
            }
        }
        int res = INT32_MAX;
        for (int v = 0; v < 10; v++)
            res = min(res, p[n - 1][v]);
        return res;
    }
};

D 最短路径中的边

最短路 + $bfs$：设 $d[i]$ 为 $0$ 到 $i$ 的最短路的长度，先用最 $dijkstra$ 求 $0$ 到 $n-1$ 的最短路。如果 $0$ 与 $n-1$ 连通，则从 $n-1$ 开始 $bfs$：设 $bfs$ 当前遍历到的节点为 $i$，若 $i$ 的邻接点 $j$ 满足 d [ j ] + w { j , i } = d [ i ] d[j]+w_{\{j,i\}}=d[i] d[j]+w{j,i}​=d[i] ，则将 $answer$ 数组中 $(j,i)$ 边对应的下标位置置为$true$ ，同时将 $j$ 加入 $bfs$ 队列。

class Solution {
  public:
    using ll = long long;
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> e(n);
        map<pair<int, int>, int> id;//记录各表在edges中的下标
        for (int i = 0; i < edges.size(); i++) {//建图
            auto& edge = edges[i];
            e[edge[0]].push_back({edge[1], edge[2]});
            e[edge[1]].push_back({edge[0], edge[2]});
            id[{min(edge[0], edge[1]), max(edge[0], edge[1])}] = i;
        }
        vector<ll> d(n, INT64_MAX);
        d[0] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;//最小堆
        q.emplace(0, 0);
        while (!q.empty()) {//求最短路
            auto [di, i] = q.top();
            q.pop();
            for (auto [j, w] : e[i]) {
                if (d[j] > di + w) {
                    d[j] = di + w;
                    q.emplace(d[j], j);
                }
            }
        }
        vector<int> vis(n);
        queue<int> qu;
        vector<bool> res(edges.size());
        if (d[n - 1] != INT64_MAX)
            qu.push(n - 1);
        while (!qu.empty()) {//bfs
            auto i = qu.front();
            qu.pop();
            for (auto [j, w] : e[i]) {
                if (d[j] != INT64_MAX && d[j] + w == d[i]) {
                    res[id[make_pair(min(i, j), max(i, j))]] = true;
                    if (!vis[j]) {
                        vis[j] = 1;//入队标记
                        qu.push(j);
                    }
                }
            }
        }
        return res;
    }
};