维格表联名的思维场，想通了算法才简单
这场周赛由 vika 维格联名，第二题和第四题都比较偏思维，想通了就很简单，想不通就会被罚坐
设计知识点：滑动窗口，逆向思维，位运算，状态压缩，贪心
5976. 检查是否每一行每一列都包含全部整数
给定一个 n\times n 的矩阵，判断每一行每一列是不是都包含了1\sim n 数据规定1\leq n\leq 100
题解
遍历每一行每一列，用哈希表记录数字是否出现即可
// cpp
class Solution {
public:
bool checkValid(vector<vector<int>>& m) {
int n = m.size();
for (int i = 0; i < n; ++i) {
unordered_map<int, int> mp;
for (int j = 0; j < n; ++j) mp[m[i][j]]++;
for (int i = 1; i <= n; ++i) if (!mp[i]) return false;
}
for (int i = 0; i < n; ++i) {
unordered_map<int, int> mp;
for (int j = 0; j < n; ++j) mp[m[j][i]]++;
for (int i = 1; i <= n; ++i) if (!mp[i]) return false;
}
return true;
}
};
5977. 最少交换次数来组合所有的 1 II
给定一个长为 n 的二进制环形数组，你可以花费一次操作，选择任意两个位置并交换上面的元素，现在要计算让所有 1 聚集在一起的最小操作数数据规定1\leq n\leq 10^5
题解
这个题正向思考比较麻烦，可以从结果出发
设一共有 k 个 1 ，那么数组最终的形态，一定是有一个长为 k 的全 1 子数
我们可以用一个长度为 k 的滑动窗口扫描数组，如果这个窗口是最终的子数组，我们需要统计窗口里的空位 0 ，这些位置可以被替换成 1 ，空位零最少的那个窗口即为答案环形数组需要做一个拼接，然后用取模操作防溢出时间复杂度\mathcal{O}(n)
// cpp
class Solution {
public:
int minSwaps(vector<int>& nums) {
int sum = 0;
for (auto& i: nums) sum += i;
int r = sum, temp = 0;
for (int i = 0; i < r; ++i) temp += (!nums[i]);
int ans = temp, n = static_cast<int>(nums.size());
while (r < n + sum) {
temp += (!nums[r % n]), temp -= (!nums[(r - sum) % n]);
ans = min(ans, temp);
r++;
}
return ans;
}
};
5978. 统计追加字母可以获得的单词数
给定字符串数组 a, b，a, b 中的每一个字符串 s 均由小写字母组成，并且每个字母只出现一次
现在你可以给 a 中的字符串 s 加上一个其本身从未出现的字母，然后做任意的排列，如果排列后的字符串 s' 在 b 中出现过，那么我们就称之为一个成功的转换，计算所有成功的转换
例如 ab 可以加上一个 c, d, e, ... , z，但是不能加上 a, b
数据规定1\leq a.size,\ b.size\leq 5\cdot 10^4,\ 1\leq a_{i}\leq 26
题解
对于 b 中的每个字符串 s，试删除某个字母，然后去 a 中判断是否存在即可
朴素的想法是将每个字符串排序，插入哈希表，复杂度会带一个小 \log ，我考虑到复制字符串的开销，用了 set，于是被卡常了，不过 set 怎么看都比 string 慢 : )
可以使用位运算，只需要一个 26 位的整数即可，本质上类似于将基于比较的排序换成基于空间的桶排序
时间复杂度 \mathcal{O}(26\cdot (n + m)) ，其中 n,\ m 分别为 a,\ b 的数组长度
// cpp
class Solution {
public:
int wordCount(vector<string>& st, vector<string>& tar) {
unordered_map<int, int> mp;
for (auto& i: st) {
int key = 0;
for (auto& j: i) {
key |= 1 << (j - 'a');
}
mp[key]++;
}
int ans = 0;
for (auto& i: tar) {
int key = 0;
for (auto& j: i) key |= 1 << (j - 'a');
for (int j = 0; j < 26; ++j) {
if (key & (1 << j)) {
int temp = key ^ (1 << j);
if (mp[temp]) {ans++; break;}
}
}
}
return ans;
}
};
5979. 全部开花的最早一天
给定 n 个花，给定两个数组 pT,\ gT ，分别代表每个花种植和开花需要的时间
你可以以任意顺序种植花朵，一朵花种完了就可以种植下一朵花，请返回让所有花都开花的最早时间
数据规定1\leq n\leq 10^5
题解
一般出现「以任意顺序」这种字眼，八九不离十是个贪心
顺序型贪心的证明方式一般是任取两个元素，判断调换顺序后是否影响结果
设 g_{1},\ g_{2} 表示两朵花的开花时间，设 p_{1},\ p_{2} 表示种植所需要的时间
先考虑开花时间的影响，不妨设 g_{1}\geq g_{2} ，考虑先后种植两朵花到开花所需要的时间
- 先 1 后 2 ，那么最晚开花时间为p_{1} + \max\left\{g_{1},\ p_{2} + g_{2}\right\}
- 先 2 后 1 ，那么最晚开花时间为 p_{2} + \max\left\{g_{2},\ p_{1} + g_{1}\right\} ，考虑到 g_{1}\geq g_{2} ，因此最大开花时间即为p_{2} + p_{1} + g_{1} 继续放缩，p_{1} + \max\left\{g_{1},\ p_{2} + g_{2}\right\}\leq p_{1} + \max\left\{g_{1},\ p_{2} + g_{1}\right\} = p_{1} + p_{2} + g_{1} 也就是说，先种植开花时间长的花朵，总耗时更短
再考虑种植时间的影响，在 g_{1} = g_{2} 的情况下，不妨设 p_{1}\geq p_{2} ，我们发现最晚的开花时间均为 p_{1} + p_{2} + 2\cdot g_{1} ，所以种植时间不会影响最终的开花时间
所以我们把所有花朵按照开花时长降序排列即可，时间复杂度\mathcal{O}(n\log n)
// cpp
class Solution {
public:
int earliestFullBloom(vector<int>& pT, vector<int>& gT) {
vector<vector<int>> vec;
for (int i = 0; i < static_cast<int>(pT.size()); ++i)
vec.push_back(vector<int>{pT[i], gT[i]});
sort(vec.begin(), vec.end(), [&](const vector<int>& a, const vector<int>& b) {return a[1] > b[1];});
int ans = 0, r = 0;
for (auto& i: vec) {
r += i[0];
ans = max(ans, r + i[1]);
}
return ans;
}
};