Hard

题目描述

给你一个非负整数 n。

如果一个非负整数的二进制表示（不含前导零）从前往后读和从后往前读是一样的，那么这个整数被称为二进制回文数。

返回满足 0 <= k <= n 且 k 的二进制表示是回文的整数 k 的个数。

注意：数字 0 被认为是二进制回文数，它的表示是 “0”。

示例 1：

输入：n = 9
输出：6
解释：
在 [0, 9] 范围内，二进制表示是回文的整数 k 有：
0 → "0"
1 → "1"
3 → "11"
5 → "101"
7 → "111"
9 → "1001"
[0, 9] 中的其他值的二进制形式都不是回文。因此，答案是 6。

示例 2：

输入：n = 0
输出：1
解释：
由于 "0" 是回文，所以答案是 1。

约束：

  • 0 <= n <= 10^15

提示：

  • 尝试从二进制字符串长度的角度思考，而不是暴力枚举所有 <= n 的数字。
  • 对于给定长度 L，存在多少个二进制回文数？（只有前半部分决定整个数字。）
  • 你可以直接使用 2 的幂来预先计算所有长度 < len(n) 的回文数。
  • 对于长度 = len(n) 的回文数，提取 n 的前缀，镜像它，并检查它是否超过 n。

解题思路

这道题要求统计不超过 n 的二进制回文数个数。关键思路是按照二进制位数进行分类计算。

核心观察：

  1. 对于长度为 L 的二进制回文数，只需要确定前半部分，后半部分由对称性唯一确定
  2. 长度为 L 的二进制回文数个数：
    • 奇数长度：2^((L-1)/2) 个（中间位可以是0或1，前半部分可以任意组合）
    • 偶数长度：2^(L/2-1) 个（首位必须是1，其余前半部分位可以任意组合）

算法步骤：

  1. 计算 n 的二进制位数 len_n
  2. 累加所有长度 < len_n 的回文数个数
  3. 对于长度 = len_n 的情况，枚举所有可能的前半部分，构造对应的回文数，判断是否 ≤ n

优化技巧：

  • 对于长度小于 n 的位数，可以直接用公式计算，无需枚举
  • 只有最高位数的回文数需要逐个检查是否超过 n

时间复杂度主要取决于 n 的二进制位数，而不是 n 的大小，因此即使 n 很大也能高效求解。

代码实现

class Solution {
public:
    int countBinaryPalindromes(long long n) {
        if (n == 0) return 1;
        
        // 获取 n 的二进制位数
        string binary = "";
        long long temp = n;
        while (temp > 0) {
            binary = (char)('0' + temp % 2) + binary;
            temp /= 2;
        }
        int len = binary.length();
        
        int count = 0;
        
        // 计算所有长度 < len 的回文数
        for (int i = 1; i < len; i++) {
            if (i % 2 == 1) {
                // 奇数长度：2^((i-1)/2)
                count += 1 << ((i - 1) / 2);
            } else {
                // 偶数长度：2^(i/2-1)
                count += 1 << (i / 2 - 1);
            }
        }
        
        // 计算长度 = len 的回文数
        int half_len = (len + 1) / 2;
        for (int i = 0; i < (1 << (half_len - 1)); i++) {
            string half = "";
            int num = (1 << (half_len - 1)) | i; // 确保最高位为1
            
            // 构造前半部分
            for (int j = half_len - 1; j >= 0; j--) {
                half += (char)('0' + ((num >> j) & 1));
            }
            
            // 构造完整回文
            string palindrome = half;
            for (int j = (len % 2 == 0 ? half_len - 1 : half_len - 2); j >= 0; j--) {
                palindrome += half[j];
            }
            
            // 转换为数字并比较
            long long val = 0;
            for (char c : palindrome) {
                val = val * 2 + (c - '0');
            }
            
            if (val <= n) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countBinaryPalindromes(self, n: int) -> int:
        if n == 0:
            return 1
        
        # 获取 n 的二进制表示
        binary = bin(n)[2:]  # 去掉 '0b' 前缀
        length = len(binary)
        
        count = 0
        
        # 计算所有长度 < length 的回文数
        for i in range(1, length):
            if i % 2 == 1:
                # 奇数长度：2^((i-1)/2)
                count += 1 << ((i - 1) // 2)
            else:
                # 偶数长度：2^(i/2-1)
                count += 1 << (i // 2 - 1)
        
        # 计算长度 = length 的回文数
        half_len = (length + 1) // 2
        
        # 枚举所有可能的前半部分
        for i in range(1 << (half_len - 1)):
            # 构造前半部分（确保最高位为1）
            half_num = (1 << (half_len - 1)) | i
            half_str = format(half_num, f'0{half_len}b')
            
            # 构造完整的回文字符串
            if length % 2 == 0:
                palindrome = half_str + half_str[::-1]
            else:
                palindrome = half_str + half_str[-2::-1]
            
            # 转换为整数并比较
            palindrome_val = int(palindrome, 2)
            
            if palindrome_val <= n:
                count += 1
        
        return count

public class Solution {
    public int CountBinaryPalindromes(long n) {
        if (n == 0) return 1;
        
        // 获取 n 的二进制位数
        string binary = Convert.ToString((long)n, 2);
        int length = binary.Length;
        
        int count = 0;
        
        // 计算所有长度 < length 的回文数
        for (int i = 1; i < length; i++) {
            if (i % 2 == 1) {
                // 奇数长度：2^((i-1)/2)
                count += 1 << ((i - 1) / 2);
            } else {
                // 偶数长度：2^(i/2-1)
                count += 1 << (i / 2 - 1);
            }
        }
        
        // 计算长度 = length 的回文数
        int halfLen = (length + 1) / 2;
        
        // 枚举所有可能的前半部分
        for (int i = 0; i < (1 << (halfLen - 1)); i++) {
            // 构造前半部分（确保最高位为1）
            int halfNum = (1 << (halfLen - 1)) | i;
            string halfStr = Convert.ToString(halfNum, 2).PadLeft(halfLen, '0');
            
            // 构造完整的回文字符串
            string palindrome;
            if (length % 2 == 0) {
                palindrome = halfStr + new string(halfStr.Reverse().ToArray());
            } else {
                palindrome = halfStr + new string(halfStr.Substring(0, halfLen - 1).Reverse().ToArray());
            }
            
            // 转换为整数并比较
            long palindromeVal = Convert.ToInt64(palindrome, 2);
            
            if (palindromeVal <= n) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countBinaryPalindromes = function(n) {
    if (n === 0) return 1;
    
    const nBinary = n.toString(2);
    const nLength = nBinary.length;
    let count = 0;
    
    // Count palindromes with fewer digits than n
    for (let len = 1; len < nLength; len++) {
        if (len === 1) {
            count += 2; // "0" and "1"
        } else {
            count += Math.pow(2, Math.floor((len - 1) / 2));
        }
    }
    
    // Count palindromes with same number of digits as n
    function generatePalindromes(length, prefix, isOddLength) {
        if (prefix.length === Math.ceil(length / 2)) {
            let palindrome = prefix;
            let suffix = prefix.split('').reverse().join('');
            if (isOddLength) {
                suffix = suffix.substring(1);
            }
            palindrome += suffix;
            
            if (palindrome.length === length && parseInt(palindrome, 2) <= n) {
                count++;
            }
            return;
        }
        
        if (prefix.length === 0) {
            generatePalindromes(length, "1", isOddLength);
        } else {
            generatePalindromes(length, prefix + "0", isOddLength);
            generatePalindromes(length, prefix + "1", isOddLength);
        }
    }
    
    generatePalindromes(nLength, "", nLength % 2 === 1);
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^(log₂n/2))主要是枚举最高位数的所有可能前半部分
空间复杂度O(log n)存储二进制字符串和临时变量