A leetcode.cn/problems/count-the-number-of-special-characters-i/" rel="nofollow">统计特殊字母的数量 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 leetcode.cn/problems/count-the-number-of-special-characters-ii/" rel="nofollow">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 leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/" rel="nofollow">使矩阵满足条件的最少操作次数

动态规划：设 $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 leetcode.cn/problems/find-edges-in-shortest-paths/" rel="nofollow">最短路径中的边

最短路 + $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()) {//bfsauto 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;}
};