力扣周赛困难-3677. 统计二进制回文数字的数目（需要一定推理的经典二分）

Problem: 3677. 统计二进制回文数字的数目

参考资料:

1. 统计二进制回文数字的数目
2. deepseek
3. qwen-image

对题目的分析：

给你一个 非负 整数 n。

如果一个 非负 整数的二进制表示（不含前导零）正着读和倒着读都一样，则称该数为 二进制回文数。

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

注意： 数字 0 被认为是二进制回文数，其表示为 "0"。

首先, 我们自然的想要分析一下二进制回文数字的分布和性质, 于是我们可以尝试写出一些数字, 看看有没有什么明显的规律:

0       0b0     // 1bit(也可以看成0bit)
1       0b1     // 1bit
3       0b11    // 2bit
5       0b101   
7       0b111   // 3bit * 2
9       0b1001  
15      0b1111  // 4bit * 2
...             // 5bit * 4
...             // 6bit * 4

这里其实就很能看出来规律了, 回文数字如果由 $n$ 位, 那么可能的回文数字的个数就是: $2^{(n-1)/2}$, 0是特例;
为什么是这样的一个公式, 其实也比较显然, 我们使用 3bit 为例子, 因为不允许前导0, 那么3bit就一定是以1开头和1结尾的, 这个时候数字就变成了: 0b1?1, 要么是 0b101 要么是 0b111,也就形成了上面给出的式子;

有了这样的公式之后, 我们其实可以对数量级进行一个大体的评估, 本题中给出的最大是 $n\le 10^{15}$, 换算成大概是 $2^{10}\sim 10^3$ 所以 $10^{15}\sim 2^{50}$, 那么再带入我们这里的公式, 其实就是位数$n$最大为 50, 然后我们可以估算一下, $10^{15}$ 大概有多少符合条件的二进制回文数字:

$$\begin{gathered} (1+1+2+2+...+2^{25}) \\ =2\ast (1+2+...+2^{25}) \\ \sim 2^{26} \end{gathered}$$
显然, 这个数字用 int 也是可以覆盖住的

这个性质有什么用呢?

至少, 我们可以利用这个性质, 迅速定位不比$k$大的最大二进制回文数的位数$n$, 从而有利于后面的进一步遍历

于是我们可以得出一段代码:

long long bar[55], cnt[55]; // bar 是某个位数最小的二进制回文数字, 形如 101 1001 10001
bar[0] = 0, cnt[0] = 0;     // cnt 类似于前缀和, 存储前面位数的回文数数量
bar[1] = 1, cnt[1] = 1;
for (int i = 2; i < 52; i++) {
    bar[i] = (1LL << (i-1)) + 1;
    cnt[i] = cnt[i - 1] + numof(i - 1);
}

int numof(int x) {
    if (x == 0 || x == 1) {
        return 1;
    }
    return 1 << ((x - 1) / 2);
}

下一步, 问题实际上就变成了怎么遍历特定位数的二进制回文数字

实际上, 本人的第一反应就是暴力枚举, 甚至这里如何进行枚举也是有点复杂的一件事情…

暴力枚举的结果当然是超时, 但是在枚举的过程中, 如果我们按照特定的规律去生成二进制回文数字, 就会发现可以用绝对有序的方式来进行生成, 这里我们需要注意到这样一个事实:
举例来说, 一个5位的二进制回文数字, 我们规定首尾为1, 那么就可以得到:0b1???1, 这里实际上有两个变化的位(另一边直接回文), 比如 0b10001, 0b10101, 0b11011, 0b11111, 因为高位数比低位数在比较大小的时候更重要, 所以实际上对高位数的有序遍历, 就是对回文数字的有序遍历, 如果仔细看上面的 0b1abc1 这个数字的 ab 对应数字, 就会发现这里的遍历恰好是 00, 01, 10, 11, 有序!!

现在我们已经可以进行有序遍历了, 我们还有必要暴力枚举吗? 原问题当然就变成了一个二分问题!

更抽象的说, 我们已经将原问题变成了这样一个经典问题: 二分查找, 查找第一个不大于key的元素位置, 只不过这里我们并不是数组, 在比较的时候也需要手动生成一下二进制回文数字才可以进行比较, 除此之外没有任何差别, 这个经典问题的典型代码也一并贴出:

int findFirstNotGreater(const vector<int>& arr, int key) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1; // 用于记录最后一个不大于key的元素位置
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止整数溢出
        
        if (arr[mid] <= key) {
            // 找到不大于key的元素，记录位置并在右侧继续查找
            result = mid;
            left = mid + 1;
        } else {
            // 当前元素大于key，在左侧继续查找
            right = mid - 1;
        }
    }
    
    return result + 1; // 返回第几位（从1开始计数）
}

最后, 贴出本人写的比较冗长的代码, 还请各位读者多多批评指正

#include<iostream>

using namespace std;
#define ll long long 

class Solution {
    public:
        int countBinaryPalindromes(long long n) {
            long long bar[55], cnt[55];
            bar[0] = 0, cnt[0] = 0;
            bar[1] = 1, cnt[1] = 1;
            for (int i = 2; i < 52; i++) {
                bar[i] = (1LL << (i-1)) + 1;
                cnt[i] = cnt[i - 1] + numof(i - 1);
            }
            // 根据 bar 可以得到bar_index，
            int bar_index = 0;
            for (int i = 0; i < 52; i++) {
                if (n == bar[i]) {
                    return (cnt[i] + 1);
                } else if(n < bar[i]) {
                    bar_index = i - 1;
                    break;
                }
            }

            int ans = cnt[bar_index];
            int index = getIndex(bar_index, n);

            return ans + index;
        }

        int numof(int x) {
            if (x == 0 || x == 1) {
                return 1;
            }
            return 1 << ((x + 1) / 2 - 1);
        }

        int getIndex(int bits, ll n) {
            if (bits == 1) {
                // (0b1); // 1 位数，只有 1
                return n >= 0b1;
            } else if (bits == 2) {
                // (0b11); // 2 位数，只有 11
                return n >= 0b11;
            } else {
                if (bits % 2 == 0) {
                    // 偶数位：前后对称
                    int changeBits = bits / 2 - 1;
                    // 2*changebit-1 ... changebit, changebit-1 ... 0
                    ll low = 0, high = (1 << changeBits) - 1;
                    ll mid = (low +  high) / 2;
                    ll result = -1;
                    while (low <= high) {
                        mid = (low +  high) / 2;                      
                        string left = ten2bistr(mid, changeBits);
                        string right = string(left);
                        reverse(right.begin(), right.end());
                        string s = "1" + left + right + "1";
                        ll this_num = bistr2ten(s);
                        if (n >= this_num) {
                            result = mid;
                            low = mid + 1;
                        } else if (n < this_num) {
                            high = mid - 1;
                        }
                    }
                    return result + 1;
                } else {
                    // 奇数位, 中间特殊
                    int changeBits = (bits + 1) / 2 - 1;
                    ll low = 0, high = (1 << changeBits) - 1;
                    ll mid = (low +  high) / 2;
                    ll result = -1;
                    while (low <= high) {
                        mid = (low + high) / 2;
                        string left = ten2bistr(mid, changeBits);
                        string midstr = left.substr(left.size()-1);
                        left = left.substr(0, left.size()-1);
                        string right = string(left);
                        reverse(right.begin(), right.end());
                        string s = "1" + left + midstr + right + "1";
                        ll this_num = bistr2ten(s);
                        if (n >= this_num) {
                            result = mid;
                            low = mid + 1;
                        } else if (n < this_num) {
                            high = mid - 1;
                        }
                    }
                    return result + 1;
                }
            }
            return -1;
        }

        string ten2bistr(long long a, int len) {
            string result = "";
            while (a > 0) {
                result = (a % 2 == 0 ? "0" : "1") + result;
                a /= 2;
            }
            // 如果结果长度不足 len，则在前面补 0
            while (result.size() < len) {
                result = "0" + result;
            }
            return result;
        }

        long long bistr2ten(string s) {
            long long result = 0;
            for (char c : s) {
                result = result * 2 + (c - '0');
            }
            return result;
        }
    };

复杂度

时间复杂度: $O(log(2^{26}))\sim O(1)$
空间复杂度: $O(1)$