1. 题目
906. 超级回文数
2. 解题思路
题目意思很简单，在给定范围中找到所有满足，它本身是回文，且它的平方也是回文的数字个数。
这题需要注意题目给定的范围，后面很有用：
因为回文范围是有限的，那么我们可以先初始化基础情况，也就是枚举出单个数字，和两位数字的回文。
题目要求范围大于1，那么我们枚举的基础数字就是1-9，通过下面的代码就可以初始化好基础的回文。
然后我们针对每个回文进行判断，它的平方是不是回文，如果是就给结果加一。
如果当前回文数的长度是偶数，继续通过在中间插入一个或两个字符（从’0’到’9’）来生成新的、更长的回文数，并将它们加入队列。这样能够递归生成长度更长的回文数。
如果当前回文数的平方已经超出了范围 [left, right]，则停止处理该回文数。
最后统计结果就好了。
3. 代码
3.1. 注意点
[!NOTE] 1、19行的
tmp.length() > 10这个判断条件是啥意思
[1, 10^18)是题目给定的整数范围，超过这个范围的数值不需要再检查。而数字的长度超过10位的平方肯定超过了这个范围。
回文数长度达到11位，那么它的平方就会超过10^22，远远超出题目要求的范围10^18
[!NOTE] 2、24行的
if (tmpNum * tmpNum < 0)这个判断条件是啥意思
我们的tmpNum类型为Long，当tmpNum * tmpNum 的结果超过Long的最大值，那么就会溢出成负数，这种情况也没必要处理了。
[!NOTE] 3、为什么在处理当前数字为偶数的时候要插入字符，并且只插入1、2个字符，不插入3、4、5…个
因为回文是数字对称的，它往往可以直接在当前回文上进行插入来得到新回文，处理代码会尝试在当前偶数长度的回文数中间插入一个或两个数字，生成更长的回文数。这样做的目的是生成可能符合条件的下一个更长的回文数，并且保持回文数的对称性。
- 插入一个
字符：生成奇数长度的回文数。例如从"1221"生成"12321"，这个新回文数的长度是奇数。- 插入两个相同的
字符：生成偶数长度的回文数。例如从"1221"生成"123321"，这个新回文数的长度是偶数。
这种方式已经覆盖了常见的奇数和偶数长度回文数的情况，不需要再增加额外的插入方式。
3.2. 完整代码
class Solution {public int superpalindromesInRange(String left, String right) {Long l = Long.parseLong(left);Long r = Long.parseLong(right);int res = 0;String[] strs = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};Queue < String > queue = new LinkedList < > ();//L 和 R 是表示 [1, 10^18) 范围的整数的字符串。 所以i从1开始for (int i = 1; i < 10; i++) {queue.offer(strs[i]);queue.offer(strs[i] + strs[i]);}while (!queue.isEmpty()) {String tmp = queue.poll();if (tmp.length() > 10) {continue;}Long tmpNum = Long.parseLong(tmp);//处理溢出情况，tmp的平方有可能会大于Long的最大值if (tmpNum * tmpNum < 0) {continue;}if (tmpNum * tmpNum <= r) {StringBuilder sb = new StringBuilder();sb.append(tmpNum * tmpNum);//判断当前数字的平方是不是回文if (tmpNum * tmpNum >= l && sb.toString().equals(sb.reverse().toString())) {res++;}if (tmp.length() % 2 == 0) {//向当前回文数插入数字构造新的更长的回文数for (String c: strs) {queue.offer(tmp.substring(0, tmp.length() / 2) + c + tmp.substring(tmp.length() / 2));queue.offer(tmp.substring(0, tmp.length() / 2) + c + c + tmp.substring(tmp.length() / 2));}}}}return res;}
}
