让我先搜索 LeetCode 3677 的题目详情。这是可以直接提交到 LeetCode 的完整 Java 实现javaclass Solution {public int countBinaryPalindromes(long n) {if (n 0) {return 1;}int count 1; // 0 是回文数int m getBinaryLength(n); // n 的二进制位数// 1. 统计二进制位数小于 m 的所有回文数// 长度为 i 的二进制回文数个数 2^((i-1)/2)for (int i 1; i m; i) {count 1 ((i - 1) / 2);}// 2. 统计二进制位数等于 m 且不超过 n 的回文数int mid m / 2; // 左半部分的长度奇数时包含中间位// 从左半部分的最高位向中间遍历// 如果 n 的某一位是 1我们可以把它改成 0剩下的位可以任意填for (int i m - 2; i mid; i--) {if ((n (1L i)) ! 0) {// 当前位填 0比 n 小剩余可自由填的位数产生的回文数个数count 1 (i - mid);}}// 3. 检查 n 本身或其左半部分生成的回文数是否 ≤ nlong left n mid; // 提取左半部分含中间位如果是奇数长度long palindrome (m % 2 ! 0) ? (left 1) : left; // 构造回文数的左半镜像基础// 将左半部分镜像到右边构造完整的回文数while (left 0) {palindrome (palindrome 1) (left 1);left 1;}if (palindrome n) {count;}return count;}// 计算 n 的二进制表示长度不含前导零private int getBinaryLength(long n) {int length 0;while (n 0) {n 1;length;}return length;}}核心思路步骤 说明1. 特判 0 0 的二进制是 0是回文数直接返回 12. 统计短位数回文 长度为 i 的二进制回文数首位必为 1左半部分含中间位有 (i-1)/2 个自由位共 2^((i-1)/2) 个3. 统计同位数回文 从高位到低位遍历 n 的左半部分。遇到 1 时将其改为 0剩余自由位可任意填累加方案数4. 检查 n 本身 用 n 的左半部分构造回文数若 ≤ n 则计数 1复杂度- 时间O(log n)只遍历 n 的二进制位- 空间O(1)
