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

让我先搜索 LeetCode 3677 的题目详情。

这是可以直接提交到 LeetCode 的完整 Java 实现：

```java
class 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 本身（或其左半部分生成的回文数）是否 ≤ n
long 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"`，是回文数，直接返回 1
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)`