LeetCode 第 211 场周赛 (哈希表、字符串（取模、枚举）、排序+最长上升子序列和、筛法求约数+并查集)

1624. 两个相同字符之间的最长子字符串

class Solution { public: int maxLengthBetweenEqualCharacters(string s) { map<char,vector<int>> mp; for(int i=0;i<s.size();i++){ char c = s[i]; mp[c].push_back(i); } int ans = -1; for(const auto &it:mp){ auto &v = it.second; ans = max(ans,v.back()-v[0]-1); } return ans; } };

1625. 执行操作后字典序最小的字符串

这两种操作其实都是取模操作，都有周期性，完全可以可以暴力枚举所有情况。

b是偶数的话只能变动奇数位的数字，否则还可以变动偶数位的数字，两层循环分别枚举就可以了。

小技巧，将s拼接成两份，然后截取子串就可以实现类似队列的循环操作。

枚举

时间复杂度：$O(S^2\ast D^2)$

class Solution { public: string findLexSmallestString(string s, int a, int b) { int n = s.size(); string ans = s; string t = s + s; int g = gcd(n, b); for (int i = 0; i < n; i += g) { string p = t.substr(i, n); for (int j = 0; j <= 9; ++j) { int th = g % 2 == 0 ? 0 : 9; // for (int k = 0; k <= th; ++k) { string q(p); for (int t = 1; t < n; t += 2) q[t] = '0' + (q[t] - '0' + a * j) % 10; for (int t = 0; t < n; t += 2) q[t] = '0' + (q[t] - '0' + a * k) % 10; ans = min(ans, q); } } } return ans; } }; BFS暴力+unordered_set去重 class Solution { public: string findLexSmallestString(string s, int a, int b) { unordered_set<string> vis; vis.insert(s); string ans = s; queue<string> q; q.push(s); int len = s.size(); while(!q.empty()){ string cur = q.front(); q.pop(); if(cur<ans) ans = cur; string nxt = cur.substr(len-b,b)+cur.substr(0,len-b); if(vis.find(nxt)==vis.end()){ vis.insert(nxt); q.push(nxt); } for(int j=1;j<len;j+=2){ cur[j] = char((cur[j]-'0'+a)%10+'0'); } if(vis.find(cur)==vis.end()){ vis.insert(cur); q.push(cur); } } return ans; } };

1626. 无矛盾的最佳球队 这题的思维的跳跃点实际上是二维降成一维排序。

最长上升子序列和 class Solution { public: int bestTeamScore(vector<int>& scores, vector<int>& ages) { int n = scores.size(); vector<pair<int,int>> v(n); for(int i=0;i<n;i++){ v[i] = {ages[i],scores[i]}; } sort(v.begin(),v.end()); vector<int> f(n,0); int ans = 0; for(int i=0;i<n;i++){ f[i] = v[i].second; for(int j=0;j<i;j++){ if(v[i].second>=v[j].second){ f[i] = max(f[i],f[j]+v[i].second); } } ans = max(ans,f[i]); } return ans; } };

1627. 带阈值的图连通性

两两使用GCD算法求最大公约数的时间复杂度为$O(n^2\ast log(n))$借助筛法的思路。由于所有的约数必定$t<num<=n$。所以假设$d$是某些对的公约数，那么$2d、3d、4d、\dots \dots$等等，它们就满足题目中要求的边的存在条件。 时间复杂度：$O(n\ast log(n))$ (调和级数)至于点和点的连通性使用并查集维护就好。 const int N = 10010; class Solution { public: int f[N]; int find(int x){ return x==f[x]?x:f[x] = find(f[x]); } void merge(int x,int y){ f[find(x)] = find(y); } vector<bool> areConnected(int n, int t, vector<vector<int>>& queries) { for(int i=0;i<N;i++) f[i] = i; for(int i = t+1;i<=n;i++){ for(int j=1;j*i<=n;j++){ merge(i,j*i); } } vector<bool> ans; for(auto& v:queries){ if(find(v[0])==find(v[1])){ ans.push_back(true); }else{ ans.push_back(false); } } return ans; } };