欢迎大家加QQ群:623375442。这周题目难度不大比较套路。
Q1. 特殊操作字符串 I
题目翻译
给定一个字符串 s
,它由小写英文字母和特殊字符 *
、#
、%
组成。按照从左到右的顺序,处理字符串并构建新的字符串 result
,处理规则如下:
- 如果当前字符是小写英文字母,则将该字母附加到
result
的末尾。 - 如果当前字符是
*
,则删除result
的最后一个字符(如果存在)。 - 如果当前字符是
#
,则将当前的result
复制一遍并追加到自身后面。 - 如果当前字符是
%
,则将当前的result
进行反转。
返回处理完所有字符后得到的最终字符串 result
。
示例:
输入:s = "a#b%*"
输出:"ba"
处理过程:
i s[i] 操作 当前 result
0 'a' 附加 'a' "a"
1 '#' 复制自身 "aa"
2 'b' 附加 'b' "aab"
3 '%' 反转 "baa"
4 '*' 删除最后一个字符 "ba"
解题思路
使用一个 StringBuilder sb
来维护当前的 result
:
- 遇到小写字母时,调用
sb.append(c)
。 - 遇到
*
时,如果sb
非空,则删除最后一个字符:sb.deleteCharAt(sb.length() - 1)
。 - 遇到
#
时,将sb
的内容复制一遍并追加:sb.append(sb)
。 - 遇到
%
时,对sb
进行原地反转:sb.reverse()
。
遍历完输入字符串后,将 sb.toString()
返回。
class Solution {
public String processStr(String s) {
// 使用 StringBuilder 来高效地构建和修改字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isLowerCase(c)) {
// 如果是小写字母,直接追加到 sb
sb.append(c);
} else if (c == '*') {
// 如果是 '*',删除 sb 的最后一个字符(如果存在)
if (sb.length() >= 1) sb.deleteCharAt(sb.length() - 1);
} else if (c == '#') {
// 如果是 '#',将当前 sb 内容复制并追加到自身后面
sb.append(sb);
} else {
// 如果是 '%',将 sb 内容进行翻转
sb.reverse();
}
}
// 返回最终结果
return sb.toString();
}
}
Q2. 最小化最大组件代价
题目翻译
给定一个无向连通图,包含 n
个节点(编号从 0
到 n-1
),以及一个 edges
数组,其中 edges[i] = [u_i, v_i, w_i]
表示节点 u_i
和 v_i
之间存在一条权重为 w_i
的无向边。另外给定一个整数 k
。
你可以删除任意条边,使得剩余图的连通分量数目不超过 k
。每个连通分量的代价定义为该连通分量中边权重的最大值;如果某个连通分量没有边,则其代价为 0
。
返回在满足至多 k
个连通分量的前提下,所有连通分量的最大代价的最小可能值。
示例:
输入:n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
输出:4
说明:
删除权重为 6 的边(节点 3-4 之间),此时图分为两部分:
- 一个只包含节点 4 的单独连通分量,费用为 0。
- 其余节点的连通分量中最大边权为 4。
因此最大代价为 4。
解题思路
要想让图分成至多 k
个组件,并且最大组件代价最小,就要尽可能保留小权重的边,删除大权重的边。当保留的边数使得连通分量数量降到 k
时,当前考虑的边权就是答案。
具体做法:
- 如果
n <= k
,说明可以让每个节点单独为一个连通分量,最大代价为0
,直接返回0
。 - 按照边权从小到大排序
edges
。 - 使用并查集(DSU),一开始有
n
个连通分量。 - 从最小权重边开始,依次尝试合并两个端点所在的分量。合并一次(即删除更高权重边以外都保留),分量数
remain
减1
。 - 当
remain <= k
时,说明当前这条边的权值就是最终答案。
class Solution {
public int minCost(int n, int[][] edges, int k) {
// 如果节点数不超过 k,则可以不保留任何边,最大代价为 0
if (n <= k) {
return 0;
}
// 按权值升序排序
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
// 初始化并查集
DSU uf = new DSU(n);
// 遍历每条边
for (int[] e : edges) {
uf.union(e[0], e[1]); // 合并两个节点
// 如果连通分量数量已降至 k 或更少,则当前边权即答案
if (uf.remain <= k) {
return e[2];
}
}
// 理论上不会到达这里
return Integer.MAX_VALUE;
}
}
// 并查集(DSU)结构
class DSU {
int[] parent; // parent[i] 表示节点 i 的父节点
int remain; // 当前剩余的连通分量数量
public DSU(int N) {
parent = new int[N];
remain = N; // 初始时每个节点都是单独的分量
for (int i = 0; i < N; ++i) {
parent[i] = i; // 自己的父节点初始化为自己
}
}
// 查找操作,带路径压缩
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个集合
public void union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fx] = fy; // 将 fx 的根指向 fy
--remain; // 分量数减 1
}
}
}
Q3. 特殊操作字符串 II
题目翻译
给定一个字符串 s
,由小写英文字母和特殊字符 *
、#
、%
组成;以及一个整数 k
。
同样按从左到右对字符串进行处理,构建一个新的字符串 result
,规则与 Q1 完全一致:
- 小写字母:追加到
result
。 *
:删除result
最后的一个字符(如果存在)。#
:复制当前result
并追加到自身。%
:反转当前result
。
返回最终 result
的第 k
个字符(0 下标)。如果 k
超出 result
长度范围,则返回 '.'
。
示例:
输入:s = "a#b%*", k = 1
输出:"a"
同 Q1 的示例,最终字符串为 "ba",其中下标 1 处的字符是 'a'。
解题思路
由于最终字符串的长度可能非常大(指数级增长),无法直接构建。需要在遍历时维护当前长度 l
,并使用倒序扫描来 "回溯" 找到第 k
个字符。
- 预处理阶段:先按原顺序扫描
s
,用一个栈stack
记录每次遇到*
操作前的长度,将长度len
变化记录下来,最后得到处理完所有字符后的总长度l
。 - 如果
l <= k
,说明k
越界,直接返回'.'
。 - 从
s
的末尾开始倒序遍历每个操作,根据以下规则更新l
和k
:- 字母:如果
l == k+1
,则当前字符就是答案;否则l--
。 *
:从stack
弹出上一次删除前的长度,赋值给l
。#
:因为#
是复制一倍,故当前长度为原长度的两倍,记原长度为ne = l/2
。如果k >= ne
(落在复制部分),则k -= ne
;然后将l = ne
。%
:反转操作对索引的映射是k = l-1-k
。
- 字母:如果
直到找到目标字符。
class Solution {
public char processStr(String s, long k) {
// 用栈记录每次 '*' 删除操作前的长度
Stack<Long> stack = new Stack<>();
// 先计算最终字符串的长度
long l = calculateLength(s, stack);
// 如果 k 越界,直接返回 '.'
if (l <= k) {
return '.';
}
// 从后向前回溯操作
for (int i = s.length() - 1; i >= 0; --i) {
char c = s.charAt(i);
if (Character.isLowerCase(c)) {
// 如果当前位置是字母,且当前 l 正好是 k+1,则找到了答案
if (l == k + 1) {
return c;
}
// 否则长度减 1,继续回溯
--l;
} else if (c == '*') {
// '*' 操作:回退到删除前的长度
l = stack.pop();
} else if (c == '#') {
// '#' 操作:复制操作前的长度
long ne = l / 2;
// 如果 k 落在复制出来的第二份里,则调整 k
if (ne <= k) {
k -= ne;
}
// 回退 l 到复制前
l = ne;
} else {
// '%' 操作:索引映射到反转前的位置
k = l - 1 - k;
}
}
// 理论上不会到达这里
return '1';
}
// 计算最终字符串长度的辅助函数
private long calculateLength(String s, Stack<Long> stack) {
long len = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isLowerCase(c)) {
// 字母:长度加 1
++len;
} else if (c == '*') {
// '*':记录当前长度到栈,然后删除最后一个字符(如果有)
stack.push(len);
len = Math.max(0, len - 1);
} else if (c == '#') {
// '#': 复制,长度翻倍
len *= 2;
}
// '%' 只影响内容顺序,不改变长度
}
return len;
}
}
Q4. 图中的最长回文路径
题目翻译
给定一个整数 n
和一个无向图,图中包含 n
个节点(编号 0
到 n-1
),由二维数组 edges
表示无向边,其中 edges[i] = [u_i, v_i]
表示节点 u_i
与 v_i
之间存在一条边。另有一个长度为 n
的字符串 label
,其中 label[i]
是节点 i
对应的字符。
你可以从任意节点出发,沿着边移动,每个节点至多访问一次,形成一条简单路径。路径上的节点所对应的字符连接成一个字符串。返回可以形成的回文字符串的最大长度。
示例:
输入:n = 3, edges = [[0,1],[1,2]], label = "aba"
输出:3
解释:
可选路径 0 → 1 → 2,对应字符串 "aba",是最长的回文,长度为 3。
解题思路
由于节点数 n
最多为较小量级(例如 n <= 12
),可以用状态压缩和动态规划。
- 状态表示:用一个整数
mask
的二进制位来表示当前路径上访问过的节点集合,mask
范围[1, 2^n)
。 - 预处理所有子集:先按子集大小(节点数)分组,存储到
countMap[c]
,其中包含所有大小为c
的子集mask
。 - 连通性预处理:使用邻接矩阵
isConnected[u][v]
判断两个节点是否有边。 -
动态规划三维数组:
isValid[l][r][mask]
表示在子集mask
范围内,能够构成一个以l
为起点、r
为终点的回文路径。- 若子集大小
i = 1
,单节点总是回文,isValid[l][l][mask] = true
。 - 若
i = 2
,两节点如果连通且字符相同,则isValid[l][r][mask] = true
。 - 若
i > 2
,枚举子集两端l
和r
,要求字符相同,且在剩余子集remain = mask ^ (1<<l) ^ (1<<r)
中存在一条从某t1
到t2
的回文路径,并且t1
与l
相邻,t2
与r
相邻。
- 若子集大小
- 更新结果:每当某个
isValid[l][r][mask]
变为true
,就可以更新最大回文长度res = 子集大小
。
此方法时间复杂度约为 O(n^2 * 2^n * n^2)
,适用于 n <= 12
的场景。
class Solution {
public int maxLen(int n, int[][] edges, String label) {
// 建立邻接矩阵,标记节点间连通关系
boolean[][] isConnected = new boolean[n][n];
for (int[] e : edges) {
isConnected[e[0]][e[1]] = true;
isConnected[e[1]][e[0]] = true;
}
// 按子集大小分组存储所有子集
List<Integer>[] countMap = new List[n + 1];
for (int i = 1; i <= n; ++i) {
countMap[i] = new ArrayList<>();
}
int max = 1 << n;
for (int mask = 1; mask < max; ++mask) {
int c = Integer.bitCount(mask); // 子集大小
countMap[c].add(mask);
}
// 三维 DP 数组,isValid[l][r][mask] 表示 mask 子集内可从 l 到 r 构成回文路径
boolean[][][] isValid = new boolean[n][n][max];
int res = 1; // 最少回文长度为 1
// 按子集大小从小到大枚举
for (int size = 1; size <= n; ++size) {
for (int mask : countMap[size]) {
// 枚举子集两端节点 l
outer:
for (int l = 0; l < n; ++l) {
if ((mask & (1 << l)) == 0) continue; // l 不在子集中
if (size == 1) {
// 单节点子集,总是回文
isValid[l][l][mask] = true;
} else if (size == 2) {
// 两节点子集,如果连通且字符相同,则是回文
for (int r = l + 1; r < n; ++r) {
if ((mask & (1 << r)) != 0
&& label.charAt(l) == label.charAt(r)
&& isConnected[l][r]) {
isValid[l][r][mask] = true;
isValid[r][l][mask] = true;
res = 2;
}
}
} else {
// 大于两个节点的子集,需要更复杂的转移
for (int r = l + 1; r < n; ++r) {
if ((mask & (1 << r)) != 0
&& label.charAt(l) == label.charAt(r)) {
int remain = mask ^ (1 << l) ^ (1 << r);
// 在剩余子集中寻找可行路径
for (int t1 = 0; t1 < n; ++t1) {
if ((remain & (1 << t1)) == 0 || !isConnected[t1][l]) continue;
for (int t2 = 0; t2 < n; ++t2) {
if ((remain & (1 << t2)) != 0
&& isValid[t1][t2][remain]
&& isConnected[t2][r]) {
// 找到可行回文,更新状态和结果
isValid[l][r][mask] = true;
isValid[r][l][mask] = true;
res = size;
// 跳出到下一个 l
continue outer;
}
}
}
}
}
}
}
}
}
return res;
}
}