以下是 LeetCode 3463「判断操作后字符串中的数字是否相等 II」的 Java 实现。解题思路为什么不能直接模拟字符串长度 n 最大可达 10^5直接模拟每次操作的时间复杂度是 O(n^2)会超时。核心洞察杨辉三角 组合数每次操作相当于对相邻数字求和模 10这本质上是杨辉三角的构造过程。经过 n-2 次操作后最终的两个数字可以表示为原字符串的加权和- num1 Σ C(n-2, i) × s[i] (i 0 n-2)- num2 Σ C(n-2, i) × s[i1] (i 0 n-2)其中 C(n-2, i) 是二项式系数。问题转化为判断 num1 % 10 num2 % 10。如何高效计算 C(n, k) mod 10利用 Lucas 定理 中国剩余定理- 10 2 × 5互质- 分别用 Lucas 定理计算 C(n, k) mod 2 和 C(n, k) mod 5- 通过预计算的 lookup 表合并得到 C(n, k) mod 10---Java 代码javaclass Solution {/*** LeetCode 3463. 判断操作后字符串中的数字是否相等 II** 思路组合数学 Lucas 定理** 每次操作相当于对相邻数字求和模10这类似于杨辉三角的构造。* 经过 n-2 次操作后最终的两个数字可以表示为* num1 Σ C(n-2, i) * s[i] (i 0 ~ n-2)* num2 Σ C(n-2, i) * s[i1] (i 0 ~ n-2)* 其中 C(n-2, i) 是二项式系数。** 由于 n 最大 10^5需要高效计算 C(n, k) mod 10。* 利用 Lucas 定理分别计算 mod 2 和 mod 5再用中国剩余定理合并。** 时间复杂度O(n * log(n))主要由 Lucas 定理的循环决定* 空间复杂度O(1)*/public boolean hasSameDigits(String s) {final int n s.length();int num1 0;int num2 0;// 遍历所有位置计算加权和for (int i 0; i 1 n; i) {final int coefficient nCkMod10(n - 2, i);num1 (num1 coefficient * (s.charAt(i) - 0)) % 10;num2 (num2 coefficient * (s.charAt(i 1) - 0)) % 10;}return num1 num2;}/*** 计算组合数 C(n, k) mod 10* 利用中国剩余定理10 2 * 5* 分别计算 mod 2 和 mod 5再查表合并*/private int nCkMod10(int n, int k) {if (k 0 || k n) return 0;final int mod2 lucasTheorem(n, k, 2);final int mod5 lucasTheorem(n, k, 5);// lookup[mod2][mod5] C(n,k) mod 10// 通过中国剩余定理预计算得到final int[][] lookup {{0, 6, 2, 8, 4}, // mod2 0{5, 1, 7, 3, 9} // mod2 1};return lookup[mod2][mod5];}/*** Lucas 定理计算 C(n, k) mod prime* 将 n 和 k 表示为 prime 进制然后逐位相乘*/private int lucasTheorem(int n, int k, int prime) {int res 1;while (n 0 || k 0) {final int nMod n % prime;final int kMod k % prime;// 如果 kMod nMod则 C(nMod, kMod) 0if (kMod nMod) {return 0;}res (res * nCkSmall(nMod, kMod)) % prime;n / prime;k / prime;}return res;}/*** 计算小规模的组合数 C(n, k)其中 n, k prime (prime 为 2 或 5)* 由于 prime 很小直接用公式计算即可*/private int nCkSmall(int n, int k) {if (k 0 || k n) return 0;if (k 0 || k n) return 1;// C(n, k) n! / (k! * (n-k)!)int res 1;for (int i 0; i k; i) {res res * (n - i) / (i 1);}return res;}}---关键要点要点 说明核心公式 最终两个数字 原字符串与二项式系数的加权和模 10Lucas 定理 将大组合数 C(n,k) 分解为 prime 进制下各位小组合数的乘积中国剩余定理 mod 10 通过 mod 2 和 mod 5 合并用预计算 lookup 表实现复杂度 时间 O(n log n)空间 O(1)下载文件[leetcode_3463.java](sandbox:///mnt/agents/output/leetcode_3463.java)
