3.6　超级回文数

这是一道力扣（LeetCode）上难度级别为困难的题目，让我们一起来看一下。

题目描述（第906题）

如果一个正整数自身是回文数，而且它也是另一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数L和R（以字符串形式表示），返回包含在范围[L,R]中的超级回文数的数目。

示例

输入：L="4"，R="1000"

输出：4

解释：4、9、121和484是超级回文数。

注意：676不是超级回文数：26 * 26=676，但26不是回文数。

提示

●　1 ≤len(L)≤ 18。

●　1 ≤len(R)≤18。

●　L和R表示在[1,1018)范围内的整数的字符串。

●　int(L)≤int(R)。

思路

暴力地对math.floor()到math.ceil()范围内的数进行遍历，并逐个判断其是否为回文数，如果是，则继续判断其平方是否是回文即可。

上面代码的时间复杂度显然已经大于O(-)，代入题目给出的数据范围大概率会超时，需要考虑剪枝。关于如何根据题目数据范围判断算法是否可行可参考第20.1节的相关内容。

剪枝是一种非常重要的思想，本书会在第20章进行详细讲述。

为什么不直接构造一个回文数Q呢？这样就省去了判断Q是否是一个回文数的过程，直接判断Q的平方即可。

这样的话，问题被转化为如何构造回文数，其核心代码如下。

如果i是123，那么r就应该为321，Q就应该为123×100+321 % 100，即12300+21，即12321。

回文中心有两种，一种是回文中心为单个字符，一种是回文中心为两个字符，因此上面的算法并不完备，我们还需要考虑回文中心为两个字符的情况。拿上面的例子来说，就少考虑了123321这种情况。我们只需要补充这种情况即可。

代码如下所示。

这种算法的时间复杂度会比上面的稍微好一点，可以通过力扣（LeetCode）所有的测试用例，但是还有优化空间，读者不妨思考一下如何优化该算法。我也会在后面的章节带读者一步一步优化类似的题目，帮助读者打开思路。

代码

复杂度分析

●　时间复杂度：O()，其中W为R的上限，在这道题中就是1018，而18的1/4是4.5，因此代码中循环到105是足够的。

●　空间复杂度：用seen来存储所有出现过的超级质数，因此空间复杂度为，其中cnt为[L,R]间的超级回文数的个数，也就是问题的解。