上分掉分，不过一念之间罢
久违的双周赛和单周赛连开。
开局以为上大分，结束之后掉大分，人生如戏罢！
涉及知识点：模拟，贪心，曼哈顿距离，前缀和，图论，搜索，分层图
双周赛 66
统计出现过一次的公共字符串
给定两个字典
，计算在两个字典中只出现一次的公共字符串个数
题解
维护两个哈希表，一个去重的集合即可，时间复杂度为
// cpp
class Solution {
public:
int countWords(vector<string>& w1, vector<string>& w2) {
set<string> st;
map<string, int> mp1, mp2;
for (auto& i: w1) mp1[i]++, st.insert(i);
for (auto& i: w2) mp2[i]++, st.insert(i);
int ans = 0;
for (auto& i: st) if (mp1[i] == 1 && mp2[i] == 1) ans++;
return ans;
}
};
从房屋收集雨水需要的最少水桶数
给定只含有 H 和 . 的字符串，前者表示房屋，后者表示空地
现在可以在空地放水桶，位置 i 的水桶可以服务 i - 1, i + 1 位置的房屋
请计算每个房屋都被水桶服务的情况下，放置的最少的水桶数，如果始终没法满足所有的房屋，返回 -1
字符串长度不超过
题解
先计算能够服务两个房屋的水桶位置，再去放置剩下的水桶，维护水桶的个数
用 mark 数组标记每个房屋被服务的情况，最后遍历 mark 数组，如果有一个房子没被服务，就返回 -1，否则返回水桶的个数，时间复杂度为
// cpp
class Solution {
public:
int minimumBuckets(string s) {
int n = s.size(), ans = 0;
vector<int> mark(n);
for (int i = 1; i < n - 1; ++i) {
if (s[i] != '.') continue;
if (s[i - 1] == 'H' && s[i + 1] == 'H' && !mark[i - 1] && !mark[i + 1]) {
ans++;
mark[i - 1] = mark[i + 1] = 1;
}
}
for (int i = 0; i < n; ++i) {
if (s[i] != '.') continue;
if (i + 1 < n && s[i + 1] == 'H' && !mark[i + 1]) {
mark[i + 1] = 1;
ans++;
}
else if (i - 1>= 0 && s[i - 1] == 'H' && !mark[i - 1]) {
mark[i - 1] = 1;
ans++;
}
}
for (int i = 0; i < n; ++i) if (s[i] == 'H' && !mark[i]) return -1;
return ans;
}
};
网格图中机器人回家的最小代价
给定
的网格，机器人位于
，目标前往
机器人可以上下左右移动，给定 row, col 数组，每移动到 i 行，消耗 row[i] 体力，每移动到 j 列，消耗 col[j] 体力
计算机器人到达目标的最小消耗体力
数据规定
题解
这个数据范围，不可能搜索；上下左右行动，不可能动态规划
非常容易证明，最小消耗一定是曼哈顿路径上的消耗，那么直接按照曼哈顿路径计算就行，时间复杂度
// cpp
class Solution {
public:
int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
int ans = 0;
int x = startPos[0], y = startPos[1];
int a = homePos[0], b = homePos[1];
for (int i = min(x, a); i <= max(x, a); ++i) ans += rowCosts[i];
for (int i = min(y, b); i <= max(y, b); ++i) ans += colCosts[i];
ans -= rowCosts[x], ans -= colCosts[y];
return ans;
}
};
统计农场中肥沃金字塔的数目
给定
的
网格，统计其中由全
组成的正金字塔和倒金字塔的数量
数据规定
题解
先维护一下每一行的前缀和
然后暴力遍历每个位置，再枚举行，依据行的子段和是否满足要求，以此判断是否构成正金字塔
倒金字塔同理，时间复杂度为
看了看题解区，也可以用动态规划优化到
// cpp
class Solution {
public:
int countPyramids(vector<vector<int>>& g) {
int m = g.size(), n = g[0].size();
vector<vector<int>> sum(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sum[i][j] = sum[i][j - 1] + g[i - 1][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (g[i - 1][j - 1] == 0) continue;
for (int k = i + 1; k <= m; ++k) {
int val = k - i;
if (j + val > n || j - val < 1) break;
if (sum[k][j + val] - sum[k][j - val - 1] != 2 * val + 1) break;
ans++;
}
for (int k = i - 1; k >= 1; --k) {
int val = i - k;
if (j + val > n || j - val < 1) break;
if (sum[k][j + val] - sum[k][j - val - 1] != 2 * val + 1) break;
ans++;
}
}
}
return ans;
}
};
单周赛 269
找出数组排序后的目标下标
给定无序数组 a 和一个目标值 tar，返回 a 排序后所有等于 tar 的下标
题解
排序后遍历
// cpp
class Solution {
public:
vector<int> targetIndices(vector<int>& nums, int tar) {
sort(nums.begin(), nums.end());
vector<int> vec;
for (int i = 0; i < nums.size(); ++i) if (nums[i] == tar) vec.push_back(i);
return vec;
}
};
半径为 k 的子数组平均值
给定数组 a，给定半径 k，对于一个位置 i，计算 [i - k, i + k] 里面元素的平均值，向下取整，如果边界溢出，返回 -1
题解
预处理前缀和之后扫描即可，时间复杂度
// cpp
class Solution {
public:
vector<int> getAverages(vector<int>& nums, int k) {
int n = nums.size();
vector<long long int> sum(n + 1);
vector<int> ans(n);
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 1; i <= n; ++i) {
if (i - k < 1 || i + k > n) ans[i - 1] = -1;
else ans[i - 1] = (sum[i + k] - sum[i - k - 1]) / (2 * k + 1);
}
return ans;
}
};
从数组中移除最大值和最小值
给定数组 a，每次操作只能移除头或尾一个元素，请你返回将最大值和最小值都移除的最小操作数
题解
先找到最大值和最小值的位置，不妨记为 p1, p2, p1 <= p2
考虑最后数组的状态，一定是一个子数组，因此我们有三种方式移除
- 从左往右移除，直到
p2被移调 - 从右往左移除，直到
p1被移调 - 移除
p1左边的，移除p2右边的
三种操作取最小值即可，时间复杂度为
// cpp
class Solution {
public:
int minimumDeletions(vector<int>& nums) {
int maxx = INT_MIN, mini = INT_MAX, n = nums.size();
int p_1 = -1, p_2 = -1;
for (int i = 0; i < n; ++i) {
if (nums[i] > maxx) maxx = nums[i], p_1 = i + 1;
if (nums[i] < mini) mini = nums[i], p_2 = i + 1;
}
int ans = 0;
int p1 = min(p_1, p_2), p2 = max(p_1, p_2);
ans = min(p1 + n - p2 + 1, min(p2, n - p1 + 1));
return ans;
}
};
找出知晓秘密的所有专家
给定 n 个专家，给定 m 个关系
对于每一个关系 [a, b, c]，表示 a, b 专家在 c 时间交谈
现在有一个秘密，如果专家 i 在 x 时间听到这个秘密，他就可以瞬间告诉其他与他正在交谈的专家
现在专家 0 告诉了专家 f，请你计算最终有多少个专家知道了秘密
数据规定
题解
考虑先把关系按照时间戳从小到大排序，之后可以按照时间戳进行一个分组
对于同一时间段，我们可以根据关系建图并做图搜索，起点是已经知道秘密且在图上的专家
本质上是一个分层图搜索问题，时间复杂度为
，前一部分是排序的复杂度，后一部分是图搜索的复杂度
// cpp 17
class Solution {
set<int> group;
map<int, unordered_map<int, vector<int>>> mp;
public:
void dfs(int u, int tm) {
for (auto& i: mp[tm][u]) {
if (group.find(i) == group.end()) {
group.insert(i);
dfs(i, tm);
}
}
}
vector<int> findAllPeople(int n, vector<vector<int>>& m, int f) {
group.insert(0), group.insert(f);
for (auto& i: m) { // 根据时间戳构建分层图，用 map<int, vector<int>> 存图
mp[i[2]][i[0]].push_back(i[1]);
mp[i[2]][i[1]].push_back(i[0]);
}
for (auto& [x, y]: mp) { // 根据时间戳遍历分层图
for (auto& [a, b]: y) { // 如果起点已经被感染，就 dfs
if (group.find(a) != group.end()) {
dfs(a, x);
}
}
}
vector<int> ans(group.begin(), group.end());
return ans;
}
};