第 437 场周赛
T1 找出长度为 K 的特殊子字符串
直接暴力行不行呢？
class Solution {
public:
bool hasSpecialSubstring(string s, int k) {
int n = s.size();
for (int i = 0; i + k <= n; i++) {
if (i > 0 && s[i] == s[i - 1]) {
continue;
}
if (i + k < n && s[i + k - 1] == s[i + k]) {
continue;
}
bool f = true;
for (int j = i + 1; j < i + k; j++) {
if (s[i] != s[j]) {
f = false;
break;
}
}
if (f) {
return true;
}
}
return false;
}
};
T2 吃披萨
此题略难，wa 了三次。
每四个一组，共 \(n/4\) 组，那么会有 \(x\) 组取 \(Z\)，\(y\) 组取 \(Y\)。其中 \(x + y == n / 4\)，并且 \(y = n / 8\)。
那么，我们的贪心准则就是取最大的 \(x\) 个元素做 \(Z\)，然后剩下的最大和次大去凑一组，次大的会贡献给答案。
class Solution {
public:
long long maxWeight(vector<int>& p) {
using ll = long long;
sort(p.begin(), p.end());
int n = p.size();
int l = 0, r = n - 1;
int cnt = n / 4;
ll res = 0;
for (int i = 0; i < cnt / 2 + (cnt % 2); i++) {
res += p[r];
r--;
l += 3;
}
for (int i = 0; i < cnt / 2; i++) {
r--;
res += p[r];
r--;
l += 2;
}
return res;
}
};
T3 选择 K 个互不重叠的特殊子字符串
这题在场上可是难到我了，emmm。
题目要求分出 K 段不重叠的子串，并且每个子串内部的字符都是独享的，字符串的其他部分并没有这些字符。
因此，如果我们想要有 a 字符，就需要把所有的 a 字符囊括进来，这样一来，如果中间还夹杂着别的字符，那也需要把别的字符都囊括进来。这个过程会扩张若干次。
而每次扩张的复杂度其实并不高，假设每次扫描 26 种字符，只扩张一次，使用二分去检查当前扫描字符是否需要扩张，那么复杂度就是 \(26\log n\)，最多扩张 \(26\) 次，因此总体复杂度就是 \(26^2\log n\)。
我们对所有字符都扩张一次，那么复杂度是 \(26^3\log n\)。
然后，得到的这些区间，每个单拎出来都是特殊子字符串。我们要找到他们的最大不重叠集合。这个也是老题，435. 无重叠区间。
当然，我们这个题中不会有两个区间有交叉，但可能会有覆盖。不过这个情形可以忽略，一并当做普通题目来做。
class Solution {
public:
bool maxSubstringLength(string s, int k) {
if (k == 0) return true;
int n = s.size();
unordered_map<char, vector<int>> b;
for (int i = 0; i < s.size(); i++) {
b[s[i]].push_back(i);
}
vector<pair<int, int>> v;
for (auto &[c, cv] : b) {
int l = cv.front(), r = cv.back();
bool expond = true;
while (expond) {
expond = false;
for (auto &[t, tv] : b) {
if (t == c) continue;
int cnt = upper_bound(tv.begin(), tv.end(), r) - lower_bound(tv.begin(), tv.end(), l);
if (cnt != 0 && cnt != tv.size()) {
expond = true;
l = min(l, tv.front());
r = max(r, tv.back());
}
}
}
if (l != 0 || r != n - 1) {
// cout << l << ' ' << r << endl;
v.push_back(make_pair(l, r));
}
}
sort(v.begin(), v.end(), [](const pair<int, int> <h, const pair<int, int> &rth) {
return lth.second < rth.second;
});
int cnt = 0;
int R = -1;
for (auto p : v) {
if (p.first <= R) {
R = max(R, p.second);
} else {
R = p.second;
cout << p.first << ' ' << p.second << ' ' << cnt << endl;
cnt++;
}
}
return k <= cnt;
}
};
T4 最长 V 形对角线段的长度
这个题，第一眼下去就是 DP，但是怎么 DP 呢？
我想的是每个位置存当前方向，以及是否拐弯这两个状态。但这样下来就有 \(500 * 500 * 8\) 个状态需要存。
代码写起来参数会比较乱。后来看到一种解法，我们可以外层固定初始方向，这样可以节省 3 倍的空间。
是的，因为不同初始方向之间的问题是相互独立的。
int d[505][505][2];
class Solution {
public:
static constexpr int inf = 0x3f3f3f3f;
int lenOfVDiagonal(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int dir[4][2] = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
auto check = [&](int x, int y, int nx, int ny) {
if (x < 0 || x >= n || y < 0 || y >= m) {
return false;
}
if (grid[x][y] == 0 || grid[x][y] == 1) {
return grid[nx][ny] == 2;
} else {
return grid[nx][ny] == 0;
}
};
int k = 0;
function<int(int, int, int)> dfs = [&](int i, int j, int t) {
if (grid[i][j] == 1) {
return 1;
}
int &res = d[i][j][t];
if (res != -inf) return res;
if (t == 0) {
int ri = i - dir[k][0];
int rj = j - dir[k][1];
if (check(ri, rj, i, j)) {
res = max(res, dfs(ri, rj, t) + 1);
}
} else {
int ri = i - dir[(k + 1) % 4][0];
int rj = j - dir[(k + 1) % 4][1];
if (check(ri, rj, i, j)) {
res = max(res, dfs(ri, rj, 1) + 1);
res = max(res, dfs(ri, rj, 0) + 1);
}
}
return res;
};
int res = 0;
for (k = 0; k < 4; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
d[i][j][0] = d[i][j][1] = -inf;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res = max(res, dfs(i, j, 0));
res = max(res, dfs(i, j, 1));
}
}
}
return res;
}
};
本站总访问量 Loading 次
本站总访客数 Loading 人