T1: 5993. 将找到的值乘以 2
思路
模拟
Code
class Solution {
public:
unordered_map<int,bool>mp;
int findFinalValue(vector<int>& nums, int ori){
for(auto& i:nums)
mp[i]=true;
while(mp.count(ori)){
ori*=2;
}
return ori;
}
};复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)
T2: 5981. 分组得分最高的所有下标
思路
遍历过程中，维护前缀中 0 的个数和后缀中 1 的个数。
Code
class Solution {
public:
unordered_map<int,vector<int>>mp;
vector<int> maxScoreIndices(vector<int>& nums) {
int sum=0,n=nums.size(),left=0,ans=INT_MIN;
for(auto& i:nums)
sum+=i;
for(int i=0;i<=n;++i){
if(i==0){
mp[sum].emplace_back(i);
ans=max(ans,sum);
}
else{
left+=nums[i-1];
int now=i-left+(sum-left);
mp[now].emplace_back(i);
ans=max(ans,now);
}
}
return mp[ans];
}
};复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(N)
T3: 5994. 查找给定哈希值的子串
思路
1.暴力
本题其实只要预处理下p的每个次方，注意是要用数组存也是可以卡过去的
2.滑动窗口
长度 K 是固定的，这提示我们使用滑动窗口来计算子串的哈希值。这里我们有两种选择：
- 从左向右滑动
- 从右向左滑动
注意到，若从前往后扫描，hashNext=(hashNow/power−s[old]+s[new]∗power^k)
由于使用了取模运算，除法应该采用乘法逆元实现，在mod不保证为质数情况下非常不优。
于是考虑从后往前处理，hashNext=( (hashNow-s[old] * power^k )) * power+s[new])%mod
Code
class Solution {
public:
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
long value=0,pow=1,mod=modulo,pp=power;
int pos=0;
for(int i=s.size()-k;i<s.size();++i){
value=((pow*(s[i]-'a'+1))%mod+value)%mod;
pow=(pow*power)%mod;
}
if(value-hashValue==0) pos=s.size()-k;
pow=1;
for(int i=0;i<k-1;++i) pow=(pow*pp)%mod;
for(int j=s.size()-k-1;j>=0;--j){
value=(((value-(pow*(s[j+k]-'a'+1)%mod)+mod)%mod*pp)%mod+(s[j]-'a'+1))%mod;
if(value-hashValue==0) pos=j;
}
return s.substr(pos,k);
}
};复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(N)
T4: 5995. 字符串分组
思路
并查集+枚举
由于字符串不含重复字母且只由小写字母组成，我们可以用一个二进制数来表示字符串，二进制数的第 i 位为 1 则表示第 i 个小写字母出现在 s 中。
枚举 words 中的字符串 s，并枚举 s 通过添加、删除和替换操作得到的字符串 t，如果 t 也在 words 中，则说明 s 和 t 可以分到同一组。我们可以用并查集来关联可以分到同一组的字符串。
遍历结束后，并查集中的集合个数就是 words 分组后的总组数，最大的集合即为字符串数目最多的组所包含的字符串数目。这可以在并查集合并的同时维护出来。
Code
class Solution {
// 并查集模板（哈希表写法）
unordered_map<int, int> fa, size;
int groups, maxSize = 0;
int find(int x) {
return fa[x] != x ? fa[x] = find(fa[x]) : x;
}
void merge(int x, int y) {
if (!fa.count(y)) return;
x = find(x);
y = find(y);
if (x == y) return;
fa[x] = y;
size[y] += size[x];
maxSize = max(maxSize, size[y]); // 维护答案
--groups;
}
public:
vector<int> groupStrings(vector<string> &words) {
groups = words.size();
for (auto &word : words) {
int x = 0;
for (char ch: word) {
x |= 1 << (ch - 'a'); // 计算 word 的二进制表示
}
fa[x] = x; // 添加至并查集
++size[x];
maxSize = max(maxSize, size[x]); // 维护答案
if (size[x] > 1) --groups;
}
for (auto &[x, _]: fa) { // 枚举所有字符串（二进制表示）
for (int i = 0; i < 26; ++i) {
merge(x, x ^ (1 << i)); // 添加或删除字符 i
if ((x >> i) & 1) {
for (int j = 0; j < 26; ++j) {
if (((x >> j) & 1) == 0) {
merge(x, x ^ (1 << i) | (1 << j)); // 替换字符 i 为 j
}
}
}
}
}
return {groups, maxSize};
}
};复杂度分析
- 时间复杂度：O(N∣Σ∣^2α(N))
- 空间复杂度：O(N)
额外拓展
个人总结
本次周赛，t1 t2 较为顺利，t3的话一直想着正向求但缺卡在最后一个点，想通过预处理p的每个次方来优化，但竟然更慢了，事后发现如果用数组存就能过了，但更为标准的做法是通过滑窗从后往前遍历，t4知道是并查集，但对于每个字符的操作没有用位运算，再加之时间不够，就不能不了了之😔
