难度: Hard
如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。
示例：
输入：L = "4", R = "1000" 输出：4 解释： 4，9，121，以及 484 是超级回文数。 注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。
提示：
1 <= len(L) <= 181 <= len(R) <= 18L 和 R 是表示 [1, 10^18) 范围的整数的字符串。int(L) <= int(R)运行时间: 29 ms
内存: 16.1 MB
class Solution:
def superpalindromesInRange (self, L, R):
L, R = int(L), int(R)
MAGIC = 100000
ans = 0
# count odd length
for k in range(MAGIC):
s = str(k) # Eg. s = '1234'
t = s + s[-2::-1] # t = '1234321'
v = int(t) ** 2
if v > R: break
if v >= L and self.is_palindrome(v):
ans += 1
# count even length
for k in range(MAGIC):
s = str(k) # Eg. s = '1234'
t = s + s[::-1] # t = '12344321'
v = int(t) ** 2
if v > R: break
if v >= L and self.is_palindrome(v):
ans += 1
return ans
def is_palindrome(self, x):
return str(x) == str(x)[::-1]
解题思路是通过首先生成可能的回文数，然后检查这些回文数的平方是否仍然是回文数。考虑到生成回文数有两种形式：奇数长度和偶数长度的回文数，分别对这两种情况进行生成和检查。对于奇数长度的回文数，形如 'abc' + 'cba'（去掉中心的字符），例如 '123' + '21' = '12321'；对于偶数长度的回文数，形式是 'abc' + 'cba'，例如 '123' + '321' = '123321'。之后，将生成的回文数平方，并检查是否在给定的范围 [L, R] 内，如果在这个范围内，再检查其平方是否是回文数。
时间复杂度: O(100000)
空间复杂度: O(1)
class Solution:
def superpalindromesInRange(self, L, R):
L, R = int(L), int(R)
MAGIC = 100000
ans = 0
# count odd length palindromes
for k in range(MAGIC):
s = str(k) # convert number to string
t = s + s[-2::-1] # form the palindrome by mirroring and omitting the last digit
v = int(t) ** 2 # square the palindrome
if v > R: break # stop if square is beyond upper limit
if v >= L and self.is_palindrome(v): # check if square is a palindrome and within range
ans += 1
# count even length palindromes
for k in range(MAGIC):
s = str(k) # convert number to string
t = s + s[::-1] # form the palindrome by full mirroring
v = int(t) ** 2 # square the palindrome
if v > R: break # stop if square is beyond upper limit
if v >= L and self.is_palindrome(v): # check if square is a palindrome and within range
ans += 1
return ans
def is_palindrome(self, x):
return str(x) == str(x)[::-1] # check if string representation of number is a palindrome
MAGIC值的设定是基于平衡算法的运算时间和覆盖必要范围的考虑。由于需要生成足够多的回文数并检查它们的平方是否也是回文数，MAGIC值应该足够大以确保可以生成覆盖[L, R]范围内可能的所有超级回文数。100000是一个估计值，可以生成长度为6的回文数（例如，生成'999999'），其平方值达到999999999999，覆盖了广泛的数值范围。这个值的选择是实验性的，旨在在可接受的计算时间内尽可能减少遗漏正确结果的风险。
直接遍历所有数字进行平方和回文检查将非常低效，特别是在数字范围非常大的情况下。通过专门生成回文数，我们可以直接构造出可能的超级回文数候选，显著减少需要检查的数字数量。奇数长度和偶数长度的回文数覆盖了所有可能的回文形式，确保算法可以完整地检查所有潜在的超级回文数。这种方法更加高效，因为它直接针对问题的特性进行了优化。
此策略不会导致遗漏有效的超级回文数。因为生成的回文数是有序的，随着基数k的增加，生成的回文数及其平方将单调增加。一旦回文数的平方超过了R，随后生成的更大的回文数的平方也必然超过R，因此不会存在后面突然有一个平方数又落在[L, R]范围内的情况。这种策略是有效的，可以在确认超出上限后立即停止进一步无用的计算。