以下是 LeetCode 3343. 统计平衡排列的数目的 TypeScript 实现。这道题的核心思路是记忆化搜索 组合数学。思路分析- 平衡排列定义偶数位0,2,4...数字之和等于奇数位1,3,5...数字之和- 设字符串长度为 n偶数位有 n/2 个奇数位有 (n1)/2 个索引从 0 开始0 是偶数- 先统计每个数字出现次数计算总和。如果总和为奇数直接返回 0- 目标从每个数字的出现次数中分配一部分到偶数位一部分到奇数位使得偶数位数字之和等于总和的一半TypeScript 代码typescriptconst MX 80;const MOD 10 ** 9 7;// 预处理组合数 C[n][k]帕斯卡三角const c: number[][] Array.from({ length: MX }, () Array(MX).fill(0));(function init() {c[0][0] 1;for (let i 1; i MX; i) {c[i][0] 1;for (let j 1; j i; j) {c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % MOD;}}})();function countBalancedPermutations(num: string): number {const cnt Array(10).fill(0);let s 0;for (const ch of num) {const d ch;cnt[d];s d;}// 如果总和为奇数无法平衡if (s % 2 ! 0) {return 0;}const n num.length;const target s / 2;const evenSlots Math.floor(n / 2); // 偶数位个数索引 0,2,4...const oddSlots Math.floor((n 1) / 2); // 奇数位个数索引 1,3,5...// 记忆化缓存用 Record 实现key 为 i,j,a,bconst memo: Recordstring, number {};const dfs (i: number, j: number, a: number, b: number): number {// i: 当前处理的数字(0-9)// j: 偶数位还需要凑的和// a: 偶数位还剩下的空位// b: 奇数位还剩下的空位if (i 9) {// 所有数字处理完毕检查是否满足条件return (j | a | b) 0 ? 1 : 0;}if (a 0 j 0) {// 偶数位没位置了但还需要凑和不可能return 0;}const key ${i},${j},${a},${b};if (key in memo) {return memo[key];}let ans 0;// 枚举当前数字 i 放到偶数位的个数 lfor (let l 0; l Math.min(cnt[i], a); l) {const r cnt[i] - l; // 放到奇数位的个数// 需要满足奇数位放得下且偶数位凑的和不超过目标if (r 0 r b l * i j) {// 从偶数位 a 个位置选 l 个放数字 i: C(a, l)// 从奇数位 b 个位置选 r 个放数字 i: C(b, r)const t Number((((BigInt(c[a][l]) * BigInt(c[b][r])) % BigInt(MOD)) *BigInt(dfs(i 1, j - l * i, a - l, b - r))) %BigInt(MOD));ans (ans t) % MOD;}}memo[key] ans;return ans;};return dfs(0, target, evenSlots, oddSlots);}核心思路说明要点 说明状态定义 dfs(i, j, a, b) 表示处理到数字 i 时偶数位还需凑 j 的和还剩 a 个偶数位空位和 b 个奇数位空位转移 枚举数字 i 放到偶数位的个数 l奇数位自动放 cnt[i]-l 个组合数 用 C(a, l) * C(b, r) 计算当前数字的放置方案数TypeScript 中需要 BigInt 防止中间结果溢出边界 处理完 0-9 所有数字后检查 j0 a0 b0复杂度- 时间复杂度: O(10 \times n^2 \times (n 10)) — 其中 10 是数字种类数- 空间复杂度: O(10 \times n^2 \times (n/21)) — 记忆化缓存大小参考来源- (Doocs LeetCode 官方题解提供了标准 TypeScript 实现)- (Algo Monster提供了带详细注释的 TypeScript 实现)注意事项1. BigInt 的使用TypeScript 中 number 类型在计算组合数乘积时可能溢出需要用 BigInt 进行中间计算最后转回 number2. 组合数预处理使用帕斯卡三角在模块初始化时一次性预处理避免重复计算3. 记忆化 keyTypeScript 没有 Python 的 cache 装饰器需要手动用 Recordstring, number 实现key 用字符串拼接4. 偶数位/奇数位定义索引从 0 开始所以偶数位索引 0,2,4...个数是 n/2奇数位索引 1,3,5...个数是 (n1)/2
Kimi LeetCode 3343. 统计平衡排列的数目 TypeScript实现
以下是 LeetCode 3343. 统计平衡排列的数目的 TypeScript 实现。这道题的核心思路是记忆化搜索 组合数学。思路分析- 平衡排列定义偶数位0,2,4...数字之和等于奇数位1,3,5...数字之和- 设字符串长度为 n偶数位有 n/2 个奇数位有 (n1)/2 个索引从 0 开始0 是偶数- 先统计每个数字出现次数计算总和。如果总和为奇数直接返回 0- 目标从每个数字的出现次数中分配一部分到偶数位一部分到奇数位使得偶数位数字之和等于总和的一半TypeScript 代码typescriptconst MX 80;const MOD 10 ** 9 7;// 预处理组合数 C[n][k]帕斯卡三角const c: number[][] Array.from({ length: MX }, () Array(MX).fill(0));(function init() {c[0][0] 1;for (let i 1; i MX; i) {c[i][0] 1;for (let j 1; j i; j) {c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % MOD;}}})();function countBalancedPermutations(num: string): number {const cnt Array(10).fill(0);let s 0;for (const ch of num) {const d ch;cnt[d];s d;}// 如果总和为奇数无法平衡if (s % 2 ! 0) {return 0;}const n num.length;const target s / 2;const evenSlots Math.floor(n / 2); // 偶数位个数索引 0,2,4...const oddSlots Math.floor((n 1) / 2); // 奇数位个数索引 1,3,5...// 记忆化缓存用 Record 实现key 为 i,j,a,bconst memo: Recordstring, number {};const dfs (i: number, j: number, a: number, b: number): number {// i: 当前处理的数字(0-9)// j: 偶数位还需要凑的和// a: 偶数位还剩下的空位// b: 奇数位还剩下的空位if (i 9) {// 所有数字处理完毕检查是否满足条件return (j | a | b) 0 ? 1 : 0;}if (a 0 j 0) {// 偶数位没位置了但还需要凑和不可能return 0;}const key ${i},${j},${a},${b};if (key in memo) {return memo[key];}let ans 0;// 枚举当前数字 i 放到偶数位的个数 lfor (let l 0; l Math.min(cnt[i], a); l) {const r cnt[i] - l; // 放到奇数位的个数// 需要满足奇数位放得下且偶数位凑的和不超过目标if (r 0 r b l * i j) {// 从偶数位 a 个位置选 l 个放数字 i: C(a, l)// 从奇数位 b 个位置选 r 个放数字 i: C(b, r)const t Number((((BigInt(c[a][l]) * BigInt(c[b][r])) % BigInt(MOD)) *BigInt(dfs(i 1, j - l * i, a - l, b - r))) %BigInt(MOD));ans (ans t) % MOD;}}memo[key] ans;return ans;};return dfs(0, target, evenSlots, oddSlots);}核心思路说明要点 说明状态定义 dfs(i, j, a, b) 表示处理到数字 i 时偶数位还需凑 j 的和还剩 a 个偶数位空位和 b 个奇数位空位转移 枚举数字 i 放到偶数位的个数 l奇数位自动放 cnt[i]-l 个组合数 用 C(a, l) * C(b, r) 计算当前数字的放置方案数TypeScript 中需要 BigInt 防止中间结果溢出边界 处理完 0-9 所有数字后检查 j0 a0 b0复杂度- 时间复杂度: O(10 \times n^2 \times (n 10)) — 其中 10 是数字种类数- 空间复杂度: O(10 \times n^2 \times (n/21)) — 记忆化缓存大小参考来源- (Doocs LeetCode 官方题解提供了标准 TypeScript 实现)- (Algo Monster提供了带详细注释的 TypeScript 实现)注意事项1. BigInt 的使用TypeScript 中 number 类型在计算组合数乘积时可能溢出需要用 BigInt 进行中间计算最后转回 number2. 组合数预处理使用帕斯卡三角在模块初始化时一次性预处理避免重复计算3. 记忆化 keyTypeScript 没有 Python 的 cache 装饰器需要手动用 Recordstring, number 实现key 用字符串拼接4. 偶数位/奇数位定义索引从 0 开始所以偶数位索引 0,2,4...个数是 n/2奇数位索引 1,3,5...个数是 (n1)/2
