这是可以直接提交到 LeetCode 的完整 Go 实现gofunc countBinaryPalindromes(n int64) int {if n 0 {return 1}var count int64 1 // 0 是回文数// 获取 n 的二进制位数不含前导零m : 0tmp : nfor tmp 0 {tmp 1m}// 1. 统计二进制位数小于 m 的所有回文数// 长度为 i 的二进制回文数个数 2^((i-1)/2)// 首位必须是 1左半部分含中间位有 (i-1)/2 个自由位for i : 1; i m; i {count 1 ((i - 1) / 2)}// 2. 统计二进制位数等于 m 且不超过 n 的回文数mid : m / 2 // 左半部分的长度奇数时包含中间位// 从左半部分的最高位向中间遍历// 如果 n 的某一位是 1我们可以把它改成 0剩下的位可以任意填for i : m - 2; i mid; i-- {if (ni)1 1 {// 当前位填 0比 n 小剩余可自由填的位数产生的回文数个数count 1 (i - mid)}}// 3. 检查 n 本身或其左半部分生成的回文数是否 nleft : n mid // 提取左半部分含中间位如果是奇数长度var palindrome int64if m%2 ! 0 {palindrome left 1} else {palindrome left}// 将左半部分镜像到右边构造完整的回文数for left 0 {palindrome (palindrome 1) (left 1)left 1}if palindrome n {count}return int(count)}核心思路步骤 说明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)
