LeetCode 周赛题解 211
5543. 两个相同字符之间的最长子字符串
「知识点：暴力」
遍历字符串，记录每个字符第一次出现的位置。当某个字符再次出现时，说明找到了相同的两个字符，那就更新一下最大长度。
class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
int anw = -1;
std::unordered_map<char, int> pos;
for(int i = 0; i < s.size(); i++) {
if(auto it = pos.find(s[i]); it != pos.end()) {
anw = max(anw, i - it->second-1);
} else {
pos.insert(make_pair(s[i], i));
}
}
return anw;
}
};
5544. 执行操作后字典序最小的字符串
「知识点：枚举」
先来思考一个事情：累加和轮转都是一个循环操作，即字符串s经过若干次操作后，一定还会回到最开始的样子。
对于累加操作来说,当累加步长a确定后，0 到 9 这这十个数字就构成了一张有向图:
- 图中一共有十个节点，分别对应数字 0 到 9.
- 有向边：如果一条边从
节点u指向节点v，则代表
。
如上图所以，当 a确定后，图中每个节点都在且只在一个环中，所以经过若干次(最多十次)累加操作后，还是会回到初始状态。
同理，经过若干次(最多 s.size() 次)轮转操作后，s也会回到初始状态。
总结一下，设s的长度为 n，轮转最多产生 n 个不同的字符串。当轮转步长b为奇数时，配合累加操作，最多产生
个不同的字符串；为偶数时，配合累加操作，最多产生
个不同的子字符串。
基于输入数据的规模，直接枚举所有的字符串，然后记录其中最小的字符串即可。
class Solution {
public:
string findLexSmallestString(string s, int a, int b) {
string anw = s;
for(int i = 0; i <= s.size(); i++) {
// 轮转
s = s.substr(b, s.size()) + s.substr(0, b);
// 修改奇数位置
for(int j = 0; j < 10; j++) {
for(int k = 1; k < s.size(); k += 2) {
s[k] += a;
if(s[k] > '9') {
s[k] = '0' + (s[k]-'9'-1);
}
}
if(b%2) {
// b为奇数，此时通过轮转，也能修改偶数位置
for(int m = 0; m < 10; m++) {
for(int k = 0; k < s.size(); k += 2) {
s[k] += a;
if(s[k] > '9') {
s[k] = '0' + (s[k]-'9'-1);
}
}
anw = min(anw, s);
}
} else {
anw = min(anw, s);
}
}
}
return anw;
}
};
5545. 无矛盾的最佳球队
「知识点：排序，动态规划」
设选定了 m 个无矛盾的队员，记为 members。将 members 升序排序(首先按 age 排序，age 相同的按照 score 排序)，必然符合下述要求：
设所有队员为 allMem，并将 allMem 按照升序排序（规则同上）。设 dp[i] 表示以第 i 个队员为最大值(年龄和能力均最大，即第 members[n-1])时，最优解的得分。则有:
最终答案为
。
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
vector<pair<int, int>> vec;
for(int i = 0; i < scores.size(); i++) {
vec.push_back(make_pair(ages[i], scores[i]));
}
sort(vec.begin(), vec.end());
vector<int> dp(vec.size());
for(int i = 0; i < vec.size(); i++) {
dp[i] = vec[i].second;
for(int j = 0; j < i; j++) {
if(vec[j].second <= vec[i].second) {
dp[i] = max(dp[i], dp[j] + vec[i].second);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
5128. 带阈值的图连通性
「知识点：并查集」
如果两个整数x, y存在公因数 d 满足 d > threshold，则 x 与 d 也必然至少存在一个大于 threshold的公因数，y 与 d 亦然。
枚举 d ∈ (threadhold, n]，找出所有能被 d 整除的数字，这些数字对应的城市必然是联通的。
通过上述
的预处理，我们可以得到一个用并查集表示的森林。这样，查询的平均时间复杂度可以降到
。
class Solution {
public:
int fa[10001];
int find(int x) {
int tmp = x;
while(fa[x] != x) {
x = fa[x];
}
while(fa[tmp] != tmp) {
int f = fa[tmp];
fa[tmp] = x;
tmp = f;
}
return x;
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
fa[fu] = fv;
}
vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
for(int i = 1; i <= n; i++) {
fa[i] = i;
}
for(int i = threshold+1; i <= n; i++) {
for(int j = i+i; j <= n; j += i) {
merge(i, j);
}
}
vector<bool> anw;
for(const auto &q : queries) {
anw.push_back(find(q[0]) == find(q[1]));
}
return anw;
}
};