0906. Super Palindromes

题目信息

题号:

0906

难度:

Hard

主题:

数值区间、回文数、完全平方数

原题:

LeetCode 0906

重点:

超级回文数本身必须是回文完全平方数,并且它的非负整数平方根也必须是回文数;区间端点以十进制字符串给出且两端都包含

题目重述

给定两个十进制字符串 left 和 right,表示整数闭区间 [left, right]。若整数 x 是回文数,并且存在一个回文整数 y 满足 y * y = x,则称 x 为超级回文数。

请返回闭区间内超级回文数的数量。这里的平方根必须是整数;普通回文数若不是回文整数的平方,不计入答案。

1 <= int(left) <= int(right) <= 10^18,两个字符串都不含前导零。

自建示例

区间内含两个两位平方根:

输入:left = "10", right = "500"
输出:2
解释:121 = 11^2,且 121 与 11 都是回文数;484 = 22^2,且 484 与 22 也都是回文数。区间内没有其他超级回文数。

小区间包含两个单位数平方:

输入:left = "1", right = "8"
输出:2
解释:1 = 1^2、4 = 2^2,平方数和平方根都为回文;9 超出右端点,因此区间内共有两个超级回文数。