本場周賽由 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);
}
};
複制