当前位置：首页 > news >正文

Kimi k2.6 LeetCode 2983. 回文串重新排列查询 Java实现

news 2026/6/5 2:34:34

以下是 LeetCode 2983. 回文串重新排列查询的 Java 实现，核心思路是将字符串分成两半，对右半部分反转后进行前缀和预处理，然后对每个查询进行分类讨论。

核心思路

1. 对称处理：将字符串 `s` 分为左右两半，右半部分反转后与左半部分对齐
2. 前缀和：预处理两个前缀和数组，分别记录左半和反转后右半的字符频次
3. 差异数组：预处理 `diff[i]` 表示前 `i` 个位置中，左右两半对应位置字符不同的个数
4. 查询分类：对于每个查询，根据两个区间 `[a,b]` 和 `[c,d]`（映射到左半部分后）的位置关系分为三种情况：
- 包含关系：一个区间完全包含另一个
- 不相交：两个区间没有交集
- 相交但不包含：需要计算各自多出的字符是否能互相匹配

Java 代码

```java
class Solution {
public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
int n = s.length();
int m = n / 2;

// 左半部分
String left = s.substring(0, m);
// 右半部分反转，使其与左半部分对称位置对齐
String rightReversed = new StringBuilder(s.substring(m)).reverse().toString();

// pre1[i][c] = left[0..i-1] 中字符 c 的出现次数
// pre2[i][c] = rightReversed[0..i-1] 中字符 c 的出现次数
int[][] pre1 = new int[m + 1][26];
int[][] pre2 = new int[m + 1][26];
// diff[i] = 前 i 个位置中，left[j] != rightReversed[j] 的个数
int[] diff = new int[m + 1];

for (int i = 1; i <= m; i++) {
// 复制前一个状态
System.arraycopy(pre1[i - 1], 0, pre1[i], 0, 26);
System.arraycopy(pre2[i - 1], 0, pre2[i], 0, 26);

// 更新当前字符计数
pre1[i][left.charAt(i - 1) - 'a']++;
pre2[i][rightReversed.charAt(i - 1) - 'a']++;

// 更新不匹配计数
diff[i] = diff[i - 1] + (left.charAt(i - 1) == rightReversed.charAt(i - 1) ? 0 : 1);
}

boolean[] ans = new boolean[queries.length];

for (int i = 0; i < queries.length; i++) {
int[] q = queries[i];
int a = q[0], b = q[1];
// 将右半部分的查询映射到反转后的坐标
// 原字符串中 s[c..d] 对应反转后 rightReversed[n-1-d .. n-1-c]
int c = n - 1 - q[3];
int d = n - 1 - q[2];

// 保证 a <= c，方便统一处理
if (a <= c) {
ans[i] = check(pre1, pre2, diff, a, b, c, d);
} else {
ans[i] = check(pre2, pre1, diff, c, d, a, b);
}
}

return ans;
}

/**
* 检查查询是否可行
* 假设 a <= c，即第一个区间在第二个区间左边或重合
*
* @param pre1 第一个字符串（对应 left）的前缀和
* @param pre2 第二个字符串（对应 rightReversed）的前缀和
* @param diff 不匹配前缀和数组
* @param a,b 第一个区间 [a,b]（在 pre1 对应的字符串上）
* @param c,d 第二个区间 [c,d]（在 pre2 对应的字符串上），且 a <= c
*/
private boolean check(int[][] pre1, int[][] pre2, int[] diff,
int a, int b, int c, int d) {
// 条件1：[0, a-1] 和 [max(b,d)+1, m-1] 必须已经匹配（无法修改的部分）
// diff[a] > 0 表示 [0, a-1] 中有不匹配
// diff[m] - diff[max(b,d)+1] > 0 表示 [max(b,d)+1, m-1] 中有不匹配
if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
return false;
}

// 情况1：第二个区间完全包含在第一个区间内（d <= b）
// 此时两个可重排区间的并集就是 [a,b]
// 需要 [a,b] 中 pre1 和 pre2 的字符频次相同
if (d <= b) {
return Arrays.equals(count(pre1, a, b), count(pre2, a, b));
}

// 情况2：两个区间不相交（b < c）
// 需要中间部分 [b+1, c-1] 已经匹配，且两个区间各自内部字符频次匹配
if (b < c) {
return diff[c] - diff[b + 1] == 0
&& Arrays.equals(count(pre1, a, b), count(pre2, a, b))
&& Arrays.equals(count(pre1, c, d), count(pre2, c, d));
}

// 情况3：两个区间相交但不包含（c <= b < d）
// 需要计算各自多出的字符是否能互补
// pre1 在 [a,b] 中多出的部分 = [a,b] 的字符 - [a,c-1] 的字符（这部分 pre2 已经匹配）
// pre2 在 [c,d] 中多出的部分 = [c,d] 的字符 - [b+1,d] 的字符（这部分 pre1 已经匹配）
int[] cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
int[] cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));

// 如果减法出现负数，说明无法匹配；否则需要 cnt1 == cnt2
return cnt1 != null && cnt2 != null && Arrays.equals(cnt1, cnt2);
}

/**
* 计算区间 [l, r] 的字符频次（闭区间）
*/
private int[] count(int[][] pre, int l, int r) {
int[] res = new int[26];
for (int i = 0; i < 26; i++) {
res[i] = pre[r + 1][i] - pre[l][i];
}
return res;
}

/**
* 数组减法 a - b，如果出现负数返回 null
*/
private int[] sub(int[] a, int[] b) {
int[] res = new int[26];
for (int i = 0; i < 26; i++) {
res[i] = a[i] - b[i];
if (res[i] < 0) {
return null;
}
}
return res;
}
}
```

复杂度分析

关键点说明

要点说明
右半反转将 `s[n/2..n-1]` 反转后，位置 `i` 和 `n-1-i` 对应回文的对称位置
查询映射 `c' = n-1-d`, `d' = n-1-c`，将右半查询映射到反转后的坐标系
不可变区域查询区间之外的位置必须已经对称匹配，否则无法通过重排修复
相交处理当两个可重排区间相交时，各自"独有"的部分必须字符频次相同才能互补

查看全文

http://www.jsqmd.com/news/952361/