完整视频讲解
🎬 前往 Bilibili 观看《力扣双周赛 187 四题完整题解》
视频章节：
00:00 3992 - 重新排列字符串以避免字符对
02:02 3993 - 交替数列的最大元素
04:01 3994 - 划分数组的最少相邻交换次数
06:05 3995 - 转换字符串的最小成本 III
本文整理第 187 场力扣双周赛的四道题。四份 Java 17 代码均经过本地编译、官方样例、边界用例与差分测试；本次采用本地模式，没有向力扣账号提交代码，因此不把本地验证写成平台 Accepted。
题目总览
| 题号 | 题目 | 难度 | 核心方法 | 时间复杂度 |
|---|---|---|---|---|
| 3992 | 重新排列字符串以避免字符对 | Easy | 三类字符分桶构造 | O(n) |
| 3993 | 交替数列的最大元素 | Medium | 峰值上界与构造公式 | O(1) |
| 3994 | 划分数组的最少相邻交换次数 | Medium | 三类别逆序对计数 | O(n) |
| 3995 | 转换字符串的最小成本 III | Hard | 不重叠区间前缀 DP | O(nRL) |
3992. 重新排列字符串以避免字符对｜三类字符分桶
题意
给定字符串 s 和两个不同字符 x、y。可以任意重排 s，要求结果中每个 y 都出现在每个 x 之前，返回任意一个满足条件的排列。
核心思路
题目只约束 x 与 y 的相对位置，其他字符放在哪里都不影响合法性。把字符分成三类：
Y：所有字符y；M：所有既不是x也不是y的字符；X：所有字符x。
最直接的合法骨架就是：
Y + M + X
代码先统计 x、y 的数量，再选择一个确定性布局：
countY < countX：输出Y + M + X；- 否则：按原顺序输出所有非
x字符，再输出全部x，即Non-X + X。
第二个布局仍然合法，因为 x != y，所以所有 y 都属于前面的 Non-X 部分。
例如 s = "zzayzb"、x = 'z'、y = 'a'：
Y = a
M = yb
X = zzz
answer = aybzzz
正确性证明
分两部分证明。
首先证明结果是原串的排列。第一种分支中，Y、M、X 三类两两不交，并完整覆盖 s 的所有字符；第二种分支中，所有非 x 字符与全部 x 同样两两不交并完整覆盖原串。因此每个输入字符都恰好写入一次。
再证明顺序条件。两种分支都把全部 x 放在最后的后缀。因为 x != y，所有 y 都位于这个后缀之前，所以任意 y 都出现在任意 x 的左侧。故算法返回的字符串一定合法。
复杂度
- 时间复杂度：
O(n)； - 空间复杂度：
O(n)，用于构造返回字符串。
Java 17 标程
class Solution {
public String rearrangeString(String s, char x, char y) {
int countX = 0;
int countY = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == x) {
countX++;
} else if (c == y) {
countY++;
}
}
StringBuilder answer = new StringBuilder(s.length());
if (countY < countX) {
for (int i = 0; i < countY; i++) {
answer.append(y);
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != x && c != y) {
answer.append(c);
}
}
} else {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != x) {
answer.append(c);
}
}
}
for (int i = 0; i < countX; i++) {
answer.append(x);
}
return answer.toString();
}
}
易错点
- 只修复一处
x、y逆序，不能保证全部y都在全部x前； - 第一种分支的中间段必须同时排除
x和y； countY < countX只是实现选择布局的条件，不是答案存在的条件；x或y没有出现时，约束可能自动成立。
3993. 交替数列的最大元素｜峰值上界与构造
题意
给定序列长度 n、首项 s 和相邻差绝对值上限 m。要求序列严格上升、严格下降交替出现，求所有合法整数序列中可能出现的最大元素。
核心观察
为了让最大值尽可能大，第一步应当向上：
- 先向上时，第一个峰值最多为
s + m； - 先向下时，
s本身就是第一个峰值，不会优于前者。
接下来考虑连续两个峰值 H、H'，中间谷值为 V。由于严格下降且元素为整数：
V <= H - 1
下一步最多上升 m：
H' <= V + m <= H + m - 1
所以每经过两步，峰值最多净增 m - 1。
公式
令：
q = floor(n / 2)
q 是下标 1, 3, 5, ... 上峰值的数量。第一个峰值是 s + m，后续 q - 1 个峰各增加至多 m - 1：
answer = s + m + (q - 1)(m - 1)
= s + q(m - 1) + 1
当 n = 1 时，序列只有首项，答案为 s。
例如 n = 4, s = 3, m = 5：
q = 2
answer = 3 + 2 × (5 - 1) + 1 = 12
可构造序列 3, 8, 7, 12 达到这个值。
正确性证明
上界方面，第一个峰值不超过 s + m；由 H' <= H + m - 1，其后每个峰值相对前一个峰值最多增加 m - 1。因此任何合法序列的最大元素都不超过公式值。
可达性方面，从 s 上升 m 得到第一个峰；之后每次从峰值下降 1，再上升 m。两条相邻边的差分别为 1 和 m，都不超过限制，而且严格下降、严格上升交替成立。每个新峰值恰好增加 m - 1，最终达到公式上界。
上界与构造值相同，因此公式就是答案。
复杂度
- 时间复杂度：
O(1)； - 空间复杂度：
O(1)。
Java 17 标程
class Solution {
public long maximumValue(int n, int s, int m) {
long peakCount = n / 2L;
int[] mavlorenti = {n, s, m};
if (mavlorenti[0] == 1) {
return mavlorenti[1];
}
return (long) mavlorenti[1]
+ peakCount * ((long) mavlorenti[2] - 1L)
+ 1L;
}
}
易错点
- 相邻两个峰值的净增上限是
m - 1，不是m； - 第一峰应先向上取得完整的
m增量； n = 1要单独处理；n很大，乘法和返回值必须使用long。
3994. 划分数组的最少相邻交换次数｜三类别逆序对
题意
通过相邻交换把数组划分成三段：
- 第一段元素全部小于
a； - 第二段元素全部位于闭区间
[a,b]； - 第三段元素全部大于
b。
三段可以为空，求最少相邻交换次数，并对 10^9 + 7 取模。
核心思路
具体数值只决定所属区间，可以压缩成三个类别：
value < a → 0
a <= value <= b → 1
value > b → 2
目标数组的类别序列必须形如 0* 1* 2*，也就是非递减序列。将一个序列通过相邻交换排成非递减顺序，最少交换次数恰好等于初始逆序对数量。
类别只有 0、1、2，无需树状数组。扫描前缀时维护：
middleCount：此前类别1的数量；largeCount：此前类别2的数量。
当前元素的新增贡献为：
读到 0：middleCount + largeCount
读到 1：largeCount
读到 2：0
例如类别序列 2,1,1,0：
读 2：+0，累计 0
读 1：+1，累计 1
读 1：+1，累计 2
读 0：+3，累计 5
答案为 5。
正确性证明
若 i < j 且类别 c[i] > c[j]，那么最终非递减序列中这两个元素的相对顺序必须颠倒。两个元素只有在某次相邻交换中彼此跨越时才能改变相对顺序，因此每个初始逆序对至少需要一次交换。
反过来，不断交换任意相邻逆序。一次交换恰好消除一个逆序对，不会增加其他逆序；当逆序数降为零时，类别序列已经非递减。因此恰好使用初始逆序对数量的交换就能完成目标。
扫描时，算法对每个元素准确统计所有以它为右端点的新逆序：类别 0 与此前所有 1、2 组成逆序；类别 1 只与此前的 2 组成逆序；类别 2 不会成为逆序右端点。不同右端点对应的逆序集合互不重叠，所以累计值就是全部逆序对数，也就是最少交换次数。
复杂度
- 时间复杂度：
O(n)； - 辅助空间复杂度：
O(1)。
Java 17 标程
class Solution {
public int minAdjacentSwaps(int[] nums, int a, int b) {
final long MOD = 1_000_000_007L;
long middleCount = 0;
long largeCount = 0;
long swaps = 0;
int[] ferlominta = nums;
for (int value : ferlominta) {
if (value < a) {
swaps += middleCount + largeCount;
} else if (value <= b) {
swaps += largeCount;
middleCount++;
} else {
largeCount++;
}
}
return (int) (swaps % MOD);
}
}
易错点
value == a或value == b都属于类别1；- 不能只统计相邻错序，答案是所有逆序对数量；
- 逆序对最多达到
n(n-1)/2，累计必须使用long； - 只在最终答案处取模，类别计数本身不能取模；
- 模拟实际交换会退化为
O(n²)。
3995. 转换字符串的最小成本 III｜不重叠区间 DP
题意
给定 source、target 和若干等长规则 pattern -> replacement。pattern 中的 '*' 可以匹配任意字符，实际规则费用等于基础费用加星号数量。一次规则覆盖的位置之后不能再被任何规则使用，求把 source 转成 target 的最小费用；不可行返回 -1。
核心观察
“用过的位置不能再次操作”意味着规则不能在同一区间上链式转换。每条规则必须：
- 直接匹配原始
source的一段连续子串； - 一次写出
target在同一段上的最终内容。
于是任意合法方案都等价于从左到右划分字符串：
source[i] == target[i]的单个字符可以免费保留；- 其他连续区间必须由一条规则直接完成；
- 所有分段天然互不重叠。
状态与转移
定义：
dp[i] = 完成前缀 [0,i) 的最小费用
初始化 dp[0] = 0，其他状态为无穷大。从每个可达位置 i 有两类转移。
免费单字符转移
若 source[i] == target[i]：
dp[i+1] = min(dp[i+1], dp[i])
规则区间转移
枚举规则 k，长度为 len[k]。它可以从 i 使用，当且仅当：
i + len[k] <= n；pattern[k]的每个非星号字符匹配source[i+j]；replacement[k][j] == target[i+j]对整段成立。
此时：
dp[i+len[k]] = min(dp[i+len[k]], dp[i] + fullCost[k])
其中 fullCost[k] 是基础费用加模式中的星号数量。
正确性证明
先从合法操作方案构造 DP 路径。合法方案的操作区间两两不重叠，按起点排序后，从左到右遍历：没有被操作的位置必须满足 source[i] == target[i]，对应免费边；每个操作区间直接匹配原始 source，并写出对应 target 子串，对应一条规则边。这样得到的 DP 路径与原方案费用相同。
再从 DP 路径构造合法方案。免费边只保留两串相等的字符；每条规则边都验证了原始 source 模式和最终 target 替换串。路径从左到右消费首尾相接的区间，因此所有规则区间互不重叠。按路径执行这些规则后，整个字符串恰好变为 target，费用等于路径权重。
合法方案与 DP 路径可以互相转换且保持费用，因此 dp[n] 就是最小费用；若 dp[n] 不可达，则不存在合法转换方案。
复杂度
设字符串长度为 n，规则数量为 R，最大规则长度为 L：
- 时间复杂度：
O(nRL)； - 空间复杂度：
O(n + R)。
Java 17 标程
class Solution {
public int minCost(String source, String target,
java.util.List<java.util.List<String>> rules, int[] costs) {
int n = source.length();
if (n != target.length()) {
return -1;
}
int ruleCount = rules.size();
String[] patterns = new String[ruleCount];
String[] replacements = new String[ruleCount];
int[] lengths = new int[ruleCount];
int[] fullCosts = new int[ruleCount];
for (int k = 0; k < ruleCount; ++k) {
patterns[k] = rules.get(k).get(0);
replacements[k] = rules.get(k).get(1);
lengths[k] = patterns[k].length();
int wildcardCount = 0;
for (int j = 0; j < lengths[k]; ++j) {
if (patterns[k].charAt(j) == '*') {
++wildcardCount;
}
}
fullCosts[k] = costs[k] + wildcardCount;
}
Object[] vornelipta = new Object[] {source, target, rules, costs};
final int INF = 1 << 29;
int[] dp = new int[n + 1];
for (int i = 0; i <= n; ++i) {
dp[i] = INF;
}
dp[0] = 0;
for (int i = 0; i < n; ++i) {
if (dp[i] == INF) {
continue;
}
if (source.charAt(i) == target.charAt(i)) {
dp[i + 1] = Math.min(dp[i + 1], dp[i]);
}
for (int k = 0; k < ruleCount; ++k) {
int len = lengths[k];
if (i + len > n) {
continue;
}
boolean matches = true;
for (int j = 0; j < len; ++j) {
char patternChar = patterns[k].charAt(j);
if (patternChar != '*' && patternChar != source.charAt(i + j)) {
matches = false;
break;
}
if (replacements[k].charAt(j) != target.charAt(i + j)) {
matches = false;
break;
}
}
if (matches) {
dp[i + len] = Math.min(
dp[i + len], dp[i] + fullCosts[k]
);
}
}
}
return dp[n] == INF ? -1 : dp[n];
}
}
易错点
- 规则不能在同一位置连续施加；
- 除了检查
pattern对source的匹配，还必须检查replacement是否等于目标子串； - 两串相同字符可以使用零费用单字符转移；
- 星号费用按模式中的
'*'数量计算； - 局部选择最便宜或最长规则不保证全局最优，必须使用 DP；
source与target长度不同时直接返回-1。
总结
本场四题可以归纳为四个很有迁移价值的建模动作：
- 只保留真正受约束的相对顺序：字符串排列题不需要搜索，把字符分桶后直接构造；
- 研究局部极值之间的净变化：峰、谷、峰三点给出
m-1的增长上界，再用同样结构达到上界； - 相邻交换排序等价于消除逆序对：类别很少时，用常数个计数器即可在线统计；
- 不重叠操作天然对应前缀分段：把免费位置和规则区间都视作 DP 边，就能统一求最小成本。
四题看起来分别属于构造、数学、计数与动态规划，但核心都在于删去无关细节，把题目压缩成最小状态。比记住具体代码更重要的是识别这种“分桶、局部上界、逆序、前缀分段”的转换。