Kimi LeetCode 3463. 判断操作后字符串中的数字是否相等 II Rust实现

以下是 LeetCode 3463 的 Rust 实现核心思路与 Python 版本一致利用 Lucas 定理 分别计算组合数模 2 和模 5再通过查表合并得到模 10 的结果。完整代码rustimpl Solution {pub fn has_same_digits(s: String) - bool {let n s.len();let bytes s.as_bytes();let mut num1 0i64; // 对应 s[0..n-2] 的最终结果let mut num2 0i64; // 对应 s[1..n-1] 的最终结果for i in 0..n - 1 {let coefficient Self::n_ck_mod10((n - 2) as i32, i as i32);let digit1 (bytes[i] - b0) as i64;let digit2 (bytes[i 1] - b0) as i64;num1 (num1 coefficient * digit1) % 10;num2 (num2 coefficient * digit2) % 10;}num1 num2}/// 计算 C(n, k) mod 10fn n_ck_mod10(n: i32, k: i32) - i64 {let mod2 Self::lucas_theorem(n, k, 2);let mod5 Self::lucas_theorem(n, k, 5);// lookup[mod2][mod5] C(n,k) mod 10let lookup: [[i64; 5]; 2] [[0, 6, 2, 8, 4], // mod2 0[5, 1, 7, 3, 9], // mod2 1];lookup[mod2 as usize][mod5 as usize]}/// Lucas 定理计算 C(n, k) mod primeprime 为质数fn lucas_theorem(mut n: i32, mut k: i32, prime: i32) - i64 {let mut res 1i64;while n 0 || k 0 {let n_mod n % prime;let k_mod k % prime;if k_mod n_mod {return 0;}res (res * Self::small_comb(n_mod, k_mod)) % prime as i64;n / prime;k / prime;}res}/// 计算小组合数 C(n, k)其中 n, k 很小0 n, k 4fn small_comb(n: i32, k: i32) - i64 {if k 0 || k n {return 0;}// 预计算 0~4 的组合数let comb [[1, 0, 0, 0, 0],[1, 1, 0, 0, 0],[1, 2, 1, 0, 0],[1, 3, 3, 1, 0],[1, 4, 6, 4, 1],];comb[n as usize][k as usize] as i64}}关键点说明要点 说明Lucas 定理 将大组合数 C(n,k) 分解为 p 进制下各位小组合数的乘积分别计算模 2 和模 5small_comb Lucas 定理中每位数字最多为 4因为 prime 最大为 5直接预计算小组合数表避免依赖外部库lookup 表 通过中国剩余定理合并模 2 和模 5 的结果得到唯一的模 10 值时间复杂度 O(n \cdot \log_p n)其中 p \in \{2, 5\}对于 n \le 10^5 非常高效空间复杂度 O(1)仅使用常数额外空间算法原理简述最终剩下的两个数字分别是原字符串两个子串的加权和权重为组合数 C(n-2, i)。由于 n \le 10^5直接模拟 O(n^2) 会超时。利用 Lucas 定理可以在 O(\log n) 时间内计算每个组合数模 10从而将总复杂度降至 O(n \log n)轻松通过。