0906：超级回文数（2140 分）

2018-09-16 约 301 字预计阅读 1 分钟次阅读

力扣第 102 场周赛第 4 题

题目

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

现在，给定两个正整数 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, 10^18) 范围的整数的字符串。
int(L) <= int(R)

分析

类似 0866，从小到大构造回文数，并判断其平方是否满足要求即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        l,r = int(left), int(right)
        res, base = 0, 1
        while True:
            for odd in [1,0]:
                for h in range(base,base*10):
                    x = int(str(h)+str(h)[::-1][odd:])
                    y = x*x
                    if y>r:
                        return res
                    if l<=y and str(y)==str(y)[::-1]:
                        res += 1
            base *= 10

351 ms

目录

0906：超级回文数（2140 分）

题目

分析

解答