如果一个数从左往右读和从右往左读都是一样,那么这个数就叫做“回文数”。例 如,12321 就是一个回文数,而 77778 就不是。当然,回文数的首和尾都应是非零的, 因此 0220 就不是回文数。事实上,有一些数(如 33 ),在十进制时是回文数,在二 进制时( 100001 )时也是回文数,我们姑且将这样的数叫做双重回文数,请你找出两 个整数之间的所有双重回文数。
时间: 2024-03-23 09:38:02 浏览: 36
好的,这是一个有趣的问题!首先,我们可以想到一个朴素的算法:枚举所有的数,判断它们是否为双重回文数。具体来说,我们可以从 1 开始,依次判断每个数字,如果它是双重回文数,就加入到结果中。这种算法的时间复杂度是 $O(N^2\log N)$,其中 $N$ 是数的最大值,因为我们需要对每个数都进行一次回文判断,而回文判断的时间复杂度是 $O(\log N)$。
不过,我们可以发现,双重回文数有一个比较特殊的性质:它们一定是奇数!这是因为如果一个偶数是回文数,那么它的最后一位一定是 0,而双重回文数的首位和尾位都不能是 0,因此它们一定是奇数。这个性质为我们的算法提供了一个很好的优化:我们只需要枚举所有的奇数,判断它们是否为双重回文数即可。
接下来,我们需要判断一个数是否为双重回文数。我们可以分别判断它在十进制和二进制下是否为回文数。具体来说,我们可以编写一个函数,输入一个数 $x$,判断它是否为回文数。这个函数的实现方法有很多种,比如可以将 $x$ 转换成字符串,然后利用字符串的反转操作判断它是否与原来的字符串相等。对于二进制回文数的判断,我们可以先将 $x$ 转换成二进制字符串,然后再进行判断。
最后,我们将所有的双重回文数输出即可。下面是一个简单的 C++ 代码实现:
```cpp
#include <iostream>
#include <string>
using namespace std;
bool is_palindrome(int x) {
string s = to_string(x);
return equal(s.begin(), s.end(), s.rbegin());
}
bool is_double_palindrome(int x) {
string s = bitset<32>(x).to_string();
s.erase(0, s.find_first_not_of('0'));
return is_palindrome(x) && is_palindrome(stoi(s));
}
void find_double_palindromes(int left, int right) {
for (int i = left; i <= right; i += 2) {
if (is_double_palindrome(i)) {
cout << i << " ";
}
}
cout << endl;
}
int main() {
int left, right;
cin >> left >> right;
find_double_palindromes(left, right);
return 0;
}
```
这个算法的时间复杂度为 $O(N\log N)$,其中 $N$ 是数的最大值。实际上,由于双重回文数非常稀疏,因此这个算法的实际运行时间会大大小于 $O(N\log N)$,在本题的数据范围内可以轻松通过。