「知识点:暴力」
遍历字符串,记录每个字符第一次出现的位置。当某个字符再次出现时,说明找到了相同的两个字符,那就更新一下最大长度。
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;
}
};
「知识点:枚举」
先来思考一个事情:累加
和轮转
都是一个循环操作,即字符串s
经过若干次操作后,一定还会回到最开始的样子。
对于累加操作来说,当累加步长a
确定后,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;
}
};
「知识点:排序,动态规划」
设选定了 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());
}
};
「知识点:并查集」
如果两个整数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;
}
};