Kimi LeetCode 3677. 统计二进制回文数字的数目 Rust实现

这是可以直接提交到 LeetCode 的完整 Rust 实现rustimpl Solution {pub fn count_binary_palindromes(n: i64) - i32 {if n 0 {return 1;}let mut count: i64 1; // 0 是回文数// 获取 n 的二进制位数不含前导零let m 64 - n.leading_zeros() as i32;// 1. 统计二进制位数小于 m 的所有回文数// 长度为 i 的二进制回文数个数 2^((i-1)/2)// 首位必须是 1左半部分含中间位有 (i-1)/2 个自由位for i in 1..m {count 1i64 ((i - 1) / 2);}// 2. 统计二进制位数等于 m 且不超过 n 的回文数let mid m / 2; // 左半部分的长度奇数时包含中间位// 从左半部分的最高位向中间遍历// 如果 n 的某一位是 1我们可以把它改成 0剩下的位可以任意填for i in (mid..m - 2).rev() {if (n i) 1 1 {// 当前位填 0比 n 小剩余可自由填的位数产生的回文数个数count 1i64 (i - mid);}}// 3. 检查 n 本身或其左半部分生成的回文数是否 nlet mut left n mid; // 提取左半部分含中间位如果是奇数长度let mut palindrome if m % 2 ! 0 { left 1 } else { left };// 将左半部分镜像到右边构造完整的回文数while left 0 {palindrome (palindrome 1) (left 1);left 1;}if palindrome n {count 1;}count as i32}}核心思路步骤 说明1. 特判 0 0 的二进制是 0是回文数2. 统计短位数回文 长度为 i 的二进制回文数首位必为 1左半部分含中间位有 (i-1)/2 个自由位共 2^((i-1)/2) 个3. 统计同位数回文 从高位到低位遍历 n 的左半部分。遇到 1 时将其改为 0剩余自由位可任意填累加方案数4. 检查 n 本身 用 n 的左半部分构造回文数若 ≤ n 则计数 1复杂度- 时间O(log n)只遍历 n 的二进制位- 空间O(1)