Kimi LeetCode 3343. 统计平衡排列的数目 Java实现

以下是 LeetCode 3343. 统计平衡排列的数目的 Java 实现。这道题的核心思路是：记忆化搜索 + 组合数学。

题目分析

- 平衡排列定义：偶数位（0,2,4...）数字之和等于奇数位（1,3,5...）数字之和
- 设字符串长度为 n，偶数位有 `(n+1)/2` 个，奇数位有 `n/2` 个
- 先统计每个数字出现次数，计算总和。如果总和为奇数，直接返回 0
- 目标：从每个数字的出现次数中，分配一部分到偶数位，一部分到奇数位，使得偶数位数字之和等于总和的一半

代码实现

```java
class Solution {
private final int[] cnt = new int[10]; // 每个数字的出现次数
private final int mod = (int) 1e9 + 7;
private Integer[][][][] f; // 记忆化数组
private long[][] c; // 组合数表

public int countBalancedPermutations(String num) {
int s = 0;
for (char ch : num.toCharArray()) {
cnt[ch - '0']++;
s += ch - '0';
}
// 如果总和为奇数，无法平衡
if (s % 2 == 1) {
return 0;
}

int n = num.length();
int m = n / 2 + 1;

// 初始化记忆化数组
f = new Integer[10][s / 2 + 1][m][m + 1];

// 预处理组合数 C[n][k]
c = new long[m + 1][m + 1];
c[0][0] = 1;
for (int i = 1; i <= m; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}

// dfs(i, j, a, b):
// i: 当前处理的数字(0-9)
// j: 偶数位还需要凑的和
// a: 偶数位还剩下的空位
// b: 奇数位还剩下的空位
return dfs(0, s / 2, n / 2, (n + 1) / 2);
}

private int dfs(int i, int j, int a, int b) {
// 所有数字处理完毕
if (i > 9) {
return ((j | a | b) == 0) ? 1 : 0;
}
// 偶数位没位置了但还需要凑和，不可能
if (a == 0 && j != 0) {
return 0;
}
// 记忆化
if (f[i][j][a][b] != null) {
return f[i][j][a][b];
}

int ans = 0;
// 枚举当前数字 i 放到偶数位的个数 l
// 放到奇数位的个数就是 cnt[i] - l
for (int l = 0; l <= Math.min(cnt[i], a); ++l) {
int r = cnt[i] - l; // 放到奇数位的个数
// 需要满足：奇数位放得下，且偶数位凑的和不超过目标
if (r >= 0 && r <= b && l * i <= j) {
// 从偶数位 a 个位置选 l 个放数字 i: C[a][l]
// 从奇数位 b 个位置选 r 个放数字 i: C[b][r]
long ways = c[a][l] * c[b][r] % mod;
int next = dfs(i + 1, j - l * i, a - l, b - r);
ans = (int) ((ans + ways * next % mod) % mod);
}
}

return f[i][j][a][b] = ans;
}
}
```

核心思路说明

要点 说明
状态定义 `dfs(i, j, a, b)` 表示处理到数字 `i` 时，偶数位还需凑 `j` 的和，还剩 `a` 个偶数位空位和 `b` 个奇数位空位
转移 枚举数字 `i` 放到偶数位的个数 `l`，奇数位自动放 `cnt[i]-l` 个
组合数 用 `C[a][l] * C[b][r]` 计算当前数字的放置方案数
边界 处理完 0-9 所有数字后，检查 `j==0 && a==0 && b==0`

复杂度

- 时间复杂度: O(10 \times n^2 \times (n + 10)) — 其中 10 是数字种类数
- 空间复杂度: O(10 \times n^2 \times (n/2+1)) — 记忆化数组大小

参考来源

- (Doocs LeetCode 官方题解)
- (每日一题题解)