力扣第 456 场周赛
2025年7月1日大约 4 分钟
力扣第 456 场周赛
比赛时间 2025-06-29。本场周赛国服共 135 人 AK。
我以前有一个房东，他告诉我，他长大的地方，就在我即将搬去的那一区。他说，在他小时候，那里是农田，他爸爸就在田里种西瓜。他张开手臂，很夸张地对我描述，那些西瓜大概有四英尺长。过了一会儿我才想到，对一个七岁的孩子来说，就算一个普通的西瓜看起来也像是庞然大物。随着年龄增长，他记忆中的西瓜也跟着长大。
你也可以用相同的逻辑来看待儿时的创伤。当我们还小的时候，创伤可能让我们觉得难以承受。但现在我们长大了，或许已拥有从不同的角度来面对它的能力。也许，现在痛苦已经不像从前那样难以承受了。用较成熟、理性的态度来处理权力斗争，不只能让你面对过去的伤痛，也能让你不再受其负面影响。这些负面影响，也就是自我局限的信念。
——克里斯多福·孟《亲密关系》
虽然但是，《亲密关系》还是应该读 罗兰·米勒 的版本。
T1. 分割字符串（4 分）
解题思路
哈希表模拟。
时间复杂度：O(n * sqrt(n))。
参考代码
class Solution {
public List<String> partitionString(String s) {
int n = s.length();
Set<String> set = new HashSet<>();
List<String> ans = new ArrayList<>();
int i = 0;
while (i < n) {
for (int j = i + 1; j <= n; j++) {
String sub = s.substring(i, j);
if (!set.contains(sub)) {
set.add(sub);
ans.add(sub);
i = j - 1;
break;
}
}
i++;
}
return ans;
}
}T2. 相邻字符串之间的最长公共前缀（4 分）
解题思路
前后缀分解。
时间复杂度：O(L)。其中 L 为 words[i] 的长度总和。
参考代码
class Solution {
public int[] longestCommonPrefix(String[] words) {
int n = words.length;
if (n == 1) return new int[1];
if (n == 2) return new int[2];
int[] pre = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
pre[i] = getLcpLen(words[i], words[i + 1]);
}
int[] L = new int[n - 1];
L[0] = pre[0];
for (int i = 1; i < n - 1; i++) {
L[i] = Math.max(L[i - 1], pre[i]);
}
int[] R = new int[n - 1];
R[n - 2] = pre[n - 2];
for (int i = n - 3; i >= 0; i--) {
R[i] = Math.max(R[i + 1], pre[i]);
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
if (i == 0) {
ans[i] = R[1];
} else if (i == n - 1) {
ans[i] = L[n - 3];
} else {
int max1 = i - 2 >= 0 ? L[i - 2] : 0;
int max2 = i + 1 <= n - 2 ? R[i + 1] : 0;
int max3 = getLcpLen(words[i - 1], words[i + 1]);
ans[i] = Math.max(Math.max(max1, max2), max3);
}
}
return ans;
}
private int getLcpLen(String str1, String str2) {
int minLen = Math.min(str1.length(), str2.length());
for (int i = 0; i < minLen; i++) {
if (str1.charAt(i) != str2.charAt(i)) {
return i;
}
}
return minLen;
}
}T3. 划分数组得到最小 XOR（5 分）
解题思路
二分答案 + 划分型 DP。
或者直接划分型 DP。
时间复杂度：O(logU * n^3)。上界大概是 O(30 * 250^3) = O(468,750,000)。
参考代码
class Solution {
private int n, k;
private int[] pre_xor;
public int minXor(int[] nums, int k) {
this.n = nums.length;
this.k = k;
pre_xor = new int[n + 1];
for (int i = 1; i <= n; i++) {
pre_xor[i] = pre_xor[i - 1] ^ nums[i - 1];
}
int left = 0;
int right = 1 << 30;
while (left < right) {
int mid = left + (right - left) / 2;
// 边界二分 F, F,..., F, [T, T,..., T]
// ----------------------^
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean check(int mid) {
boolean[][] dp = new boolean[n + 1][k + 1];
dp[0][0] = true;
for (int j = 1; j <= k; j++) {
for (int i = j; i <= n; i++) {
for (int p = j - 1; p < i; p++) {
if (dp[p][j - 1]) {
int xor_val = pre_xor[i] ^ pre_xor[p];
if (xor_val <= mid) {
dp[i][j] = true;
break; // 找到一种分割方式即可，跳出内层循环
}
}
}
}
}
return dp[n][k];
}
}T4. 升级后最大生成树稳定性（6 分）
解题思路
二分答案 + 并查集。
时间复杂度：O((n+m)lognlogU)。
参考代码
class Solution {
private int n, k;
private List<int[]> mustEdges, optionalEdges;
public int maxStability(int n, int[][] edges, int k) {
this.n = n;
this.k = k;
mustEdges = new ArrayList<>();
optionalEdges = new ArrayList<>();
for (int[] edge : edges) {
if (edge[3] == 1) {
mustEdges.add(edge);
} else {
optionalEdges.add(edge);
}
}
int left = 0;
int right = (int) 2e5;
while (left < right) {
int mid = left + (right - left) / 2;
// 边界二分 F, F,..., F, [T, T,..., T]
// ----------------------^
if (!check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left - 1;
}
private boolean check(int X) {
DSU uf = new DSU(n);
for (int[] edge : mustEdges) {
int u = edge[0], v = edge[1], s = edge[2];
if (s < X) {
return false;
}
int ru = uf.find(u);
int rv = uf.find(v);
if (ru != rv) {
uf.union(u, v);
} else {
return false;
}
}
int upgrades = 0;
for (int[] edge : optionalEdges) {
int u = edge[0], v = edge[1], s = edge[2];
if (s >= X) {
int ru = uf.find(u);
int rv = uf.find(v);
if (ru != rv) {
uf.union(u, v);
}
}
}
for (int[] edge : optionalEdges) {
int u = edge[0], v = edge[1], s = edge[2];
if (s < X && 2 * s >= X) {
int ru = uf.find(u);
int rv = uf.find(v);
if (ru != rv) {
uf.union(u, v);
upgrades++;
if (upgrades > k) {
break;
}
}
}
}
return uf.sz == 1 && upgrades <= k;
}
static class DSU {
int[] fa;
int sz;
public DSU(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) fa[i] = i;
sz = n;
}
int find(int x) { // 查找
return x == fa[x] ? fa[x] : (fa[x] = find(fa[x]));
}
void union(int p, int q) { // 合并
p = find(p);
q = find(q);
if (p == q) return;
fa[q] = p;
sz--;
}
}
}（全文完）