力扣第 439 场周赛
2025年3月4日大约 3 分钟
力扣第 439 场周赛
比赛时间 2025-03-02。本场周赛国服共 68 人 AK。
“人心中的成见是一座大山，任你怎么努力都休想搬动。”
——《哪吒之魔童降世》
T1. 找出最大的几近缺失整数（3 分）
解题思路
分类讨论。特别容易漏掉 k == n 的情况。
时间复杂度：O(n)。
参考代码
class Solution {
public int largestInteger(int[] nums, int k) {
int n = nums.length;
int[] cnt = new int[51];
for (int v : nums) cnt[v]++;
int ans = -1;
if (k == n) {
return Arrays.stream(nums).max().orElseThrow();
} else if (k == 1) {
for (int v : nums) {
if (cnt[v] == 1) ans = Math.max(ans, v);
}
return ans;
} else {
if (cnt[nums[0]] == 1) ans = Math.max(ans, nums[0]);
if (cnt[nums[n - 1]] == 1) ans = Math.max(ans, nums[n - 1]);
return ans;
}
}
}T2. 至多 K 次操作后的最长回文子序列（4 分）
解题思路
区间 DP。
时间复杂度：O(n^2 * k)。
参考代码
class Solution {
private char[] s;
private int[][][] memo;
public int longestPalindromicSubsequence(String S, int k) {
this.s = S.toCharArray();
int n = s.length;
memo = new int[n][n][k + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(memo[i][j], -1);
}
}
return dfs(0, n - 1, k);
}
private int dfs(int i, int j, int k) {
if (i >= j) return j - i + 1; // i=j+1 时返回 0，i=j 时返回 1
if (memo[i][j][k] != -1) return memo[i][j][k];
int res = Math.max(dfs(i + 1, j, k), dfs(i, j - 1, k)); // 枚举哪个不选
int d = Math.abs(s[i] - s[j]);
int cost = Math.min(d, 26 - d);
if (k - cost >= 0) {
res = Math.max(res, dfs(i + 1, j - 1, k - cost) + 2);
}
return memo[i][j][k] = res;
}
}T3. 长度至少为 M 的 K 个子数组之和（5 分）
解题思路
划分型 DP + 前缀和优化。
和 3077 题 几乎是一样的题目，一年前的 T4 hard，时过境迁，今年竟然放 T3 medium 了，（作为 T4 时候 clist rating 分是 2586，今天 T3 rating 分是 2460）
时间复杂度：O(nk)。
参考代码
class Solution {
public int maxSum(int[] nums, int k, int m) {
int n = nums.length;
long[] ps = new long[n + 1];
for (int i = 0; i < n; i++) {
ps[i + 1] = ps[i] + nums[i];
}
long[][] f = new long[k + 1][n + 1];
for (int i = 1; i <= k; i++) {
long mx = Long.MIN_VALUE / 2;
// 3077 verson
// long w = (i % 2 > 0 ? 1 : -1) * (k - i + 1);
// f[i][i - 1] = mx;
// for (int j = i; j <= n - (k - i); j++) {
// mx = Math.max(mx, f[i - 1][j - 1] - ps[j - 1] * w);
// f[i][j] = Math.max(f[i][j - 1], ps[j] * w + mx);
// }
for (int j = i * m - m; j < i * m; j++) {
f[i][j] = mx;
}
for (int j = i * m; j <= n - (k - i) * m; j++) {
mx = Math.max(mx, f[i - 1][j - m] - ps[j - m]);
f[i][j] = Math.max(f[i][j - 1], ps[j] + mx);
}
}
return (int) f[k][n];
}
}T4. 字典序最小的生成字符串（7 分）
解题思路
贪心 + 暴力匹配。
- 处理 'T' 条件：遍历第一个字符串的所有位置，如果遇到 'T'，则设置生成的字符串对应位置的字符为第二个字符串的对应字符，并标记这些位置为固定。
- 填充默认值：将所有未被固定的位置填充为 'a'，以确保字典序最小。
- 处理 'F' 条件：检查每个 'F' 位置的子字符串是否等于第二个字符串。如果相等，找到最后一个未被固定的位置，将其修改为最小的可能字符，使其不等于对应位置的字符。
- 最终验证：再次检查所有 'F' 条件，确保所有条件均被满足，否则返回空字符串。
时间复杂度：O(nm)。
参考代码
class Solution {
public String generateString(String str1, String str2) {
int n = str1.length();
int m = str2.length();
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int total_len = n + m - 1;
char[] res = new char[total_len];
Arrays.fill(res, '#');
boolean[] fixed = new boolean[total_len];
for (int i = 0; i < n; i++) {
if (s1[i] == 'T') {
for (int j = 0; j < m; j++) {
int pos = i + j;
if (pos >= total_len) return "";
if (res[pos] != '#' && res[pos] != s2[j]) return "";
res[pos] = s2[j];
fixed[pos] = true;
}
}
}
for (int i = 0; i < total_len; i++) {
if (res[i] == '#') res[i] = 'a';
}
for (int i = 0; i < n; i++) {
if (s1[i] == 'F') {
boolean equal = true;
for (int j = 0; j < m; j++) {
int pos = i + j;
if (res[pos] != s2[j]) {
equal = false;
break;
}
}
if (!equal) continue;
boolean modified = false;
for (int j = 0; j < m; j++) {
int pos = (i + m - 1) - j;
if (!fixed[pos]) {
res[pos] = (s2[j] != 'a') ? 'a' : 'b';
modified = true;
break;
}
}
if (!modified) return "";
}
}
for (int i = 0; i < n; i++) {
if (s1[i] == 'F') {
boolean equal = true;
for (int j = 0; j < m; j++) {
int pos = i + j;
if (res[pos] != s2[j]) {
equal = false;
break;
}
}
if (equal) return "";
}
}
return new String(res);
}
}（全文完）