问题分析
如果直接枚举范围 [left, right] 中的每个数字，判断它是否为回文数以及其平方根是否为回文数，时间复杂度会非常高。
但是，如果一个数 x 是超级回文数，那么 x 的平方根必定是回文数。
因此，可以转换思路，不枚举 x，而是枚举 x 的平方根。
由于 x 最大为 $10^{18}$，那么 x 的平方根最大为 $10^9$。
这里还有一个优化：
回文数具有对称性，不需要直接枚举所有 $10^{9}$以内的数字来判断哪些是回文数。
可以用一个"种子"数来构造回文数。
具体来说的话就是：
一个 9 位的回文数（如 123454321）可以由前 5 位（12345）确定，因为后 4 位是前 4 位的镜像；
一个 8 位的回文数（如 12344321）可以由前 4 位（1234）确定。
因此，对于最大 $10^9$（10 位数）的回文数，只需要枚举 1 到 $10^5$（5 位数）的种子，就能构造出所有可能的回文数。
每个种子生成两种回文数：
偶数长度（种子完整镜像，如 123→123321）和奇数长度（种子去掉最后一位后镜像，如 123→12321）。
这样，问题规模就从枚举 $10^9$ 个数降到只需枚举 $10^5$ 个种子，大幅降低了时间复杂度。
求解思路
通过枚举种子数来生成回文数，每个种子可以生成两种回文数：奇数长度的回文数和偶数长度的回文数。
对于每个生成的回文数 num，计算其平方 num²，判断 num² 是否在给定范围 [left, right] 内，并且 num² 本身也是回文数。
如果满足条件，计数器加一。从种子 1 开始递增枚举，直到生成的回文数 num 超过了 right 的平方根为止。
完整代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
public class Solution {
public static int superpalindromesInRange(String left, String right) {
long l = Long.valueOf(left);
long r = Long.valueOf(right);
// 计算右边界的平方根，作为枚举回文数的上限
long limit = (long) Math.sqrt((double) r);
// seed: 种子数，用于生成回文数
// 从1开始枚举，每个种子可以生成奇数长度和偶数长度两种回文数
long seed = 1;
// num: 根据种子生成的回文数（即超级回文数的平方根）
long num = 0;
// 统计符合条件的超级回文数数量
int ans = 0;
do {
// 用seed生成偶数长度的回文数
// 例如: 123 -> 123321
num = evenEnlarge(seed);
// 检查 num² 是否在范围内且为回文数
if (check(num * num, l, r)) {
ans++;
}
// 用seed生成奇数长度的回文数
// 例如: 123 -> 12321
num = oddEnlarge(seed);
// 检查 num² 是否在范围内且为回文数
if (check(num * num, l, r)) {
ans++;
}
// 种子递增，继续枚举
seed++;
} while (num < limit); // 当生成的回文数超过limit时停止
return ans;
}
public static long evenEnlarge(long seed) {
long ans = seed;
// 将seed的每一位依次添加到ans末尾
while (seed != 0) {
ans = ans * 10 + seed % 10; // 取seed最后一位拼接到ans
seed /= 10; // 去掉seed的最后一位
}
return ans;
}
public static long oddEnlarge(long seed) {
long ans = seed;
seed /= 10; // 先去掉最后一位，避免中间数字重复
// 将剩余部分翻转后拼接
while (seed != 0) {
ans = ans * 10 + seed % 10;
seed /= 10;
}
return ans;
}
public static boolean check(long ans, long l, long r) {
return ans >= l && ans <= r && isPalindrome(ans);
}
public static boolean isPalindrome(long num) {
// offset用于定位最高位，例如52725，offset为10000
long offset = 1;
// 计算offset的值，使其等于10^(位数-1)
// 注意这里用 num/offset >= 10 而不是 num >= offset*10，防止溢出
while (num / offset >= 10) {
offset *= 10;
}
// 首尾对比判断是否回文
while (num != 0) {
// 比较最高位和最低位
if (num / offset != num % 10) {
return false;
}
// 去掉最高位和最低位，继续判断内部数字
num = (num % offset) / 10; // 去掉最高位后再去掉最低位
offset /= 100; // 因为去掉了两位，所以offset除以100
}
return true;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~