不愧是自动驾驶公司，周赛考大家基环树
本场周赛由 AutoX 联名，作为新年第一场力扣周赛，题目还挺有意思的，是个头脑风暴的好选择。
涉及的知识点：贪心，拓扑排序，动态规划，图数据挖掘
5967. 检查是否所有 A 都在 B 之前
给定一个只包含 A, B 的字符串，判断是否所有的字符 A 都出现在字符 B 前
题解
容易归纳出，符合题意的字符串要么是 A..AB..B 式，要么是 B..B 式，用一个 flag 标记即可
// cpp
class Solution {
public:
bool checkString(string s) {
bool flag = false;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == 'b') flag = true;
else if (flag && s[i] == 'a') return false;
}
return true;
}
};
5968. 银行中的激光束数量
给定 n 个长为 m 的 01 字符串，对于相邻的两个字符串，它们任意两个 1 可以组成一个激光束，计算所有激光束数量
题解
先处理出每个字符串含有的 1 的数量，并且把不含 1 的字符串剔除
然后相邻的两个值乘起来即可，求和即为答案
// cpp
class Solution {
public:
int numberOfBeams(vector<string>& bank) {
vector<int> vec;
for (auto& i: bank) {
int cnt = 0;
for (auto& j: i) if (j == '1') cnt++;
if (cnt) vec.push_back(cnt);
}
int ans = 0;
for (int i = 0; i < static_cast<int>(vec.size()) - 1; ++i) {
ans += vec[i] * vec[i + 1];
}
return ans;
}
};
5969. 摧毁小行星
有一个质量为 m 的行星，以及 n 个质量为 a_{i} 的小行星你可以任意排列小行星的顺序，让行星与之相撞，相撞的条件是 m\geq a_{i} ，同时相撞之后由于相吸效应，行星质量要加上a_{i} 请你判断行星是否可以撞毁所有小行星？
数据规定1\leq n,\ m,\ a_{i}\leq 10^5
题解
考虑贪心，我们选取剩下的小行星中最大的不超过 m 的行星，拿出来和行星撞一下，这样可以保证行星的质量局部最大，在之后的相撞中不落下风
可以用一个有序集和来存储数据，找到相撞的行星后将其删除，时间复杂度\mathcal{O}(n\log n)
// cpp
class Solution {
public:
bool asteroidsDestroyed(int m, vector<int>& a) {
typedef long long LL;
multiset<LL> st(a.begin(), a.end());
LL sum = m;
int n = static_cast<int>(a.size());
for (int i = 0; i < n; ++i) {
auto x = st.upper_bound(sum);
if (x == st.begin()) return false;
x--;
sum += (*x);
st.erase(x);
}
return true;
}
};
也可以从最小的开始吸收，代码更简单
// cpp
class Solution {
public:
bool asteroidsDestroyed(int m, vector<int>& a) {
sort(a.begin(), a.end());
typedef long long LL;
LL sum = m;
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
if (sum < a[i]) return false;
sum += a[i];
}
return true;
}
};
5970. 参加会议的最多员工数
有 n 个员工，每个员工有一个心仪的对象（保证不是自己）
有一个无限大的圆桌，如果一个员工旁边坐着自己心仪的对象，那么他就会参加会议
请问最多有多少员工参加会议？
数据规定1\leq n\leq 10^5
题解
考虑建图，我们发现如下性质
- 每个点有且仅有一个出边
- 无自环
实际上这个是基环树的概念，每个点有且仅有一个出边，叫做基环内向树；如果每个点有且仅有一个入边，叫做基环外向树
不过管他什么图论模型，用到的算法基本上就是搜索、拓扑排序、最短路和动态规划
分析一下，能够上桌的只有两种情况
- 首尾相连的环
- 局部有一个二元环，环的两边分别拉下去一条链
我们可以用拓扑排序做一个图挖掘，最终子图上只会剩下环
1 -- 2 -- 3 5 -- 6
\ /
\ / 7 --- 8
\ / \ /
4 9
在拓扑排序的过程中，我们可以依据拓扑序做动态规划，计算到每个员工最大的依赖数，这样统计第二种情况答案的时候直接用最长链的长度相加即可
时间空间复杂度均为\mathcal{O}(n)
// cpp
class Solution {
public:
int maximumInvitations(vector<int>& f) {
int n = static_cast<int>(f.size());
vector<int> dp(n);
vector<int> ind(n);
for (int i = 0; i < n; ++i) {
ind[f[i]]++;
}
queue<int> q;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
if (!ind[i]) q.push(i);
}
while (!q.empty()) {
int temp = q.front(); q.pop();
int to = f[temp];
dp[to] = max(dp[to], dp[temp] + 1);
ind[to]--;
if (!ind[to]) q.push(to);
}
int ans1 = 0, ans2 = 0;
vector<bool> vis(n);
for (int i = 0; i < n; ++i) {
if (!ind[i] || vis[i]) continue;
if (f[f[i]] == i) {
vis[f[i]] = true, vis[i] = true;
ans1 += dp[f[i]] + dp[i];
}
else {
int cnt = 1;
for (int j = f[i]; j != i; j = f[j]) {
vis[j] = true;
cnt++;
}
ans2 = max(ans2, cnt);
}
}
return max(ans1, ans2);
}
};
腾讯云开发者
