本文主要是介绍LeetCode 第394场周赛个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
100294. 统计特殊字母的数量 I
原题链接
思路分析
AC代码
100291. 统计特殊字母的数量 II
原题链接
思路分析
AC代码
100290. 使矩阵满足条件的最少操作次数
原题链接
思路分析
AC代码
100276. 最短路径中的边
原题链接
思路分析
AC代码
100294. 统计特殊字母的数量 I
原题链接
100294. 统计特殊字母的数量 I
思路分析
签到题不说了
AC代码
class Solution {
public:int numberOfSpecialChars(string word) {int res = 0;unordered_set<char> st;for(auto x : word) st.insert(x);for(char x = 'a', y = 'A'; x <= 'z'; x ++, y ++)if(st.count(x) && st.count(y)) res ++;return res;}
};100291. 统计特殊字母的数量 II
原题链接
100291. 统计特殊字母的数量 II
思路分析
比赛中为了一次ac避免罚时，选择统计每个字符的第一次出现位置和最后一次出现位置
然后遍历26个小写字母判断它们的最后一次出现位置是否比大写字母第一次出现位置靠前即可
时间复杂度O(n)
AC代码
class Solution:def numberOfSpecialChars(self, word: str) -> int:first, last = dict(), dict()n = len(word)for i, x in enumerate(word[::-1]):first[x] = n - ifor i, x in enumerate(word):last[x] = ires = 0for ch in range(ord('a'), ord('z') + 1):x = chr(ch)if x in last and str.upper(x) in first and last[x] < first[str.upper(x)]:res += 1return res100290. 使矩阵满足条件的最少操作次数
原题链接
100290. 使矩阵满足条件的最少操作次数
思路分析
最终形态：每列都相等，不存在相同的相邻两列
那么我们只需要讨论每一列取什么值能够使得每相邻两列不同且操作次数最少
定义状态f(i, j)，为考虑到第 i 列且第i列取j，两两相邻列不重复的最小操作次数
记cnt[i][j]为原网格第i列中j的出现次数
那么有转移方程f(i + 1, j) = min(f(i + 1, j), f(i, k) + m - cnt[i + 1][j])
状态数：n * k，k = 10，状态转移O(k)
故时间复杂度O(nk^2)
AC代码
class Solution {
public:int minimumOperations(vector<vector<int>>& g) {int m = g.size(), n = g[0].size();vector<vector<int>> cnt(n + 1, vector<int>(10));for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)cnt[j + 1][g[i][j]] ++;vector<vector<int>> f(n + 1, vector<int>(10));for(int i = 0; i < n; i++)for(int j = 0; j < 10; j++){f[i + 1][j] = 1e9;for(int k = 0; k < 10; k++){if(k == j) continue;f[i + 1][j] = min(f[i + 1][j], f[i][k] + m - cnt[i + 1][j]);}}return *min_element(f[n].begin(), f[n].end());}
};100276. 最短路径中的边
原题链接
100276. 最短路径中的边
思路分析
唯一一发WA在这道题了，变量名写错了淦
emm，最短路&dijkstra变形题中非常经典的变形，都是在dijkstra上加个递推
和这道题一个路子：1976. 到达目的地的方案数
只不过把求最短路的数目改为了对所有最短路上边的标记
最短路的数目都能求这个自然也能求，换汤不换药
定义pre[i]为结点 i 在到达n - 1的所有最短路的前驱边编号的集合
我们求dijkstra的时候，记出队结点为x
如果dst[x] + w(x, y) < dst[y]，那么清空pre[y]，把<x, y>的编号假如pre[y]
如果dst[x] + w(x, y) = dst[y]，把<x, y>的编号假如pre[y]
然后路径恢复，即从n - 1往前跑一直走到0即可
时间复杂度O(mlogm)
AC代码
class Solution {
public:typedef long long LL;typedef pair<LL, int> PLI;typedef pair<int, int> PII;typedef pair<PII, int> PIII;#define mkp make_pairvector<bool> findAnswer(int n, vector<vector<int>>& edges) {int m = edges.size();vector<vector<PIII>> g(n);vector<LL> dst(n, 1e12);vector<bool> ret(m);vector<unordered_set<int>> pre(n);for(int i = 0; i < m; i++) g[edges[i][0]].emplace_back(mkp(edges[i][1], edges[i][2]), i), g[edges[i][1]].emplace_back(mkp(edges[i][0], edges[i][2]), i);priority_queue<PLI, vector<PLI>, greater<PLI>> pq;pq.emplace(dst[0] = 0, 0);while(pq.size()){auto [d, x] = pq.top();pq.pop();if(x == n - 1) break;for(auto&e : g[x]){int y = e.first.first, w = e.first.second, i = e.second;if(dst[x] + w < dst[y]){pre[y].clear();pre[y].insert(i);pq.emplace(dst[y] = dst[x] + w, y);}else if(dst[x] + w == dst[y]){pre[y].insert(i);}}}if(dst[n - 1] == 1e12) return ret;queue<int> q;q.emplace(n - 1);vector<bool> vis(n); while(q.size()){auto t = q.front(); q.pop();if(vis[t]) continue;vis[t] = 1;for(auto x : pre[t]){int u = edges[x][0], v = edges[x][1];//cout << u << ' ' << v << ' ';ret[x] = 1;if(u == t) swap(u, v);q.emplace(u);}}return ret;}
};
/*
输出：
[false,false,false,false,false,false,false,false,true,false,false,false]
预期：
[false,false,false,true,false,false,false,false,true,false,false,false]
*/这篇关于LeetCode 第394场周赛个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
