以下是 LeetCode 3343. 统计平衡排列的数目的 Java 实现。这道题的核心思路是记忆化搜索 组合数学。题目分析- 平衡排列定义偶数位0,2,4...数字之和等于奇数位1,3,5...数字之和- 设字符串长度为 n偶数位有 (n1)/2 个奇数位有 n/2 个- 先统计每个数字出现次数计算总和。如果总和为奇数直接返回 0- 目标从每个数字的出现次数中分配一部分到偶数位一部分到奇数位使得偶数位数字之和等于总和的一半代码实现javaclass 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] - lfor (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 所有数字后检查 j0 a0 b0复杂度- 时间复杂度: O(10 \times n^2 \times (n 10)) — 其中 10 是数字种类数- 空间复杂度: O(10 \times n^2 \times (n/21)) — 记忆化数组大小参考来源- (Doocs LeetCode 官方题解)- (每日一题题解)
尧图网络