题目

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

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

示例：

1
2
3
4
5
输入：L = "4", R = "1000"
输出：4
解释：
4，9，121，以及 484 是超级回文数。
注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。

提示：

  1. 1 <= len(L) <= 18
  2. 1 <= len(R) <= 18
  3. L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
  4. int(L) <= int(R)

题解

第一层：暴力

简单地按照题目的解法，短短几行写出来,判断i是不是回文，再判断i开根号是不是整数，再判断i开根号是不是回文。
理所当然地，这肯定超时了。

1
2
3
4
5
6
7
8
9
10
import math
class Solution:
    def superpalindromesInRange(self, L: str, R: str) -> int:
        count = 0
        for i in range(int(L), int(R) + 1):
            if str(i)[::-1] == str(i):
                if int(math.sqrt(i))**2 == i:
                    if str(int(math.sqrt(i))) == str(int(math.sqrt(i)))[::-1]:
                        count += 1
        return count

第二层：优化循环

为什么要使得i从L遍历到R呢？如果我们从根号L遍历到根号R，不是就省了很多遍历次数了吗？说干就干！

这是很不错的进步，然而很遗憾的是，这样子遍历完还是超时了。

1
2
3
4
5
6
7
8
import math
class Solution:
    def superpalindromesInRange(self, L: str, R: str) -> int:
        count = 0
        for i in range(int(math.sqrt(int(L))), int(math.sqrt(int(R))) + 1):
            if str(i)[::-1] == str(i) and str(i**2)[::-1] == str(i**2):
                    count += 1
        return count

第三层：优化回文数判断

会不会我们对回文数的处理太暴力了呢？如果按照第九题的判断回文数的方法，会不会省掉很多时间呢？

然而，还是超时了。

方法是，对回文数的后半部分进行反转，比较前半部分和后半部分是否相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import math
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        revertedNumber = 0
        while x > revertedNumber:
            revertedNumber = revertedNumber * 10 + x % 10
            x //= 10
        return x == revertedNumber or x == revertedNumber//10
    
    def superpalindromesInRange(self, L: str, R: str) -> int:
        count = 0
        for i in range(int(math.sqrt(int(L))),int(math.sqrt(int(R)))+1):
            if self.isPalindrome(i) and self.isPalindrome(i**2):
                count += 1
        return count

第四层：找回文数规律

我们只好从回文数下手了。遍历寻找回文数始终是个累活儿，而且回文数毕竟不多。

回文数有没有规律呢？

有。

举个例子，比方说 12321 这个回文数，下一个回文数就是 12421 ，一直加中间这一项，直到加到 12921。再下一个呢？就是加中间项的隔壁两项，同时中间项从0开始。即13031,13131…重复这个规律，直到99999，此时下一个为1000001，如此反复。那么我们需要写一个函数，来计算给定了一个回文数，求下一个回文数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def nextPalindrome(x: int) -> int:
    # 如果全是9则返回x+2
    if len(str(x)) != len(str(x+1)):
        return x + 2
    # 把数放到list里方便操作
    list_x = []
    while x != 0:
        list_x.insert(0, x % 10)
        x //= 10
    # 找到中间两位数，记作left_index和right_index
    if len(list_x) % 2 == 1:
        left_index = right_index = len(list_x) // 2
    else:
        left_index = len(list_x) // 2 - 1
        right_index = len(list_x) // 2
    # 如果中间的数是9，那么向外扩散
    while list_x[left_index] == 9:
        left_index -= 1
        right_index += 1
    # 若left_index和right_index指向不同位，则它们各自加一
    # 若不是，则只要加一次一
    if left_index != right_index:
        list_x[left_index] += 1
        list_x[right_index] += 1
    else:
        list_x[left_index] += 1
    # 中间有9的情况下，要把9置0
    for i in range(left_index + 1, right_index):
        list_x[i] = 0
    next_palindrome = 0
    for i in list_x:
        next_palindrome = next_palindrome * 10 + i
    return next_palindrome

那就开始计算！
这里使用了双指针，第一个指针指向开根号后的第一个回文数，第二个指针指向原数列的第一个回文数。比较两个指针的大小，谁小了，那个指针往后移，即使用nextPalindrome。相等的时候，两个都移，同时count增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def superpalindromesInRange(self, L: str, R: str) -> int:
    count = 0
    sqrt = None
    itself = None
    # 开根号后找到第一个回文数
    i = int(math.sqrt(int(L)))
    while i <= int(math.sqrt(int(R))):
        if self.isPalindrome(i):
            sqrt = i
            break
        else:
            i += 1
    # 开根号前找到第一个回文数
    i = int(L)
    while i <= int(R):
        if self.isPalindrome(i):
            itself = i
            break
        else:
            i += 1
    # 指针开始遍历
    if sqrt is None or itself is None:
        return 0     
    while sqrt <= int(math.sqrt(int(R))) and itself <= int(R):
        if sqrt ** 2 < itself:
            sqrt = self.nextPalindrome(sqrt)
        elif sqrt ** 2 > itself:
            itself = self.nextPalindrome(itself)
        else:
            count += 1
            sqrt = self.nextPalindrome(sqrt)
            itself = self.nextPalindrome(itself)
    return count

这下好了吧？然而还是超过了时间限制……陷入了深深的思考。

终极大招

首先恭喜也感谢你看到这里。

现在我们唯一没有做过手脚的，是探讨回文数和它的平方的关系。

什么样的回文数的平方仍然是回文数？或者说，什么样的回文数开根号后也是回文数？这其中是不是有些规律？

有。

如果我们将符号要求开根号后的回文数列出来，我们不难发现前几个是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
1
2
3
11
22
101
111
121
202
212
1001
1111
2002
10001
10101
10201
11011
11111
11211
20002
20102
100001
101101
110011
111111
200002
1000001
1001001
1002001
1010101
1011101
1012101
1100011
1101011
1102011
1110111
1111111
2000002
2001002
10000001
10011001
10100101
10111101
11000011
11011011
11100111
11111111

很长也很有规律是不是？那我们照着这个来写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Solution:
    # 判断是否是回文
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        revertedNumber = 0
        while x > revertedNumber:
            revertedNumber = revertedNumber * 10 + x % 10
            x //= 10
        return x == revertedNumber or x == revertedNumber // 10

    # 给定上一个回文计算下一个回文
    def nextPalindrome(self, x: int) -> int:
        if x == 1111111:
            return 2000002
        if x == 101111101:
            return 110000011
        if x == 110111011:
            return 111000111
        if x == 111010111:
            return 111101111
        if x == 111111111:
            return 200000002
        if x // 10 == 0:
            if x == 1:
                return 2
            elif x == 2:
                return 3
            else:
                return 11
        # 把数放到list里方便操作
        list_x = []
        tmp = x
        while tmp != 0:
            list_x.insert(0, tmp % 10)
            tmp //= 10

        # 针对结尾是2的情况处理
        if x % 10 == 2:
            if len(list_x) % 2 == 0:
                if (x - 2) // 2 == 10 ** (len(list_x) - 1):
                    return 10 ** len(list_x) + 1
            else:
                if list_x[len(list_x) // 2] == 0:
                    return x + 10 ** (len(list_x) // 2)
                else:
                    return 10 ** len(list_x) + 1

        # 在字符串长度是奇数的情况下
        if len(list_x) % 2 == 1:
            mid_index = len(list_x) // 2
            if list_x[mid_index] != 2:
                list_x[mid_index] += 1
            else:
                mid_index -= 1
                while list_x[mid_index] != 0 and mid_index > 0:
                    mid_index -= 1
                if mid_index == 0:
                    return 2 * 10 ** (len(list_x) - 1) + 2
                else:
                    for i in range(mid_index + 1, len(list_x) - mid_index - 1):
                        list_x[i] = 0
                    list_x[mid_index] += 1
                    list_x[-mid_index - 1] += 1

        # 在字符串长度是偶数的情况下
        # 找到中间两位数，记作left_index和right_index
        else:
            left_index = len(list_x) // 2 - 1
            right_index = len(list_x) // 2
            while list_x[left_index] == 1 and left_index > 0:
                left_index -= 1
                right_index += 1
            if left_index == 0:
                return 2 * 10 ** (len(list_x) - 1) + 2
            else:
                for i in range(left_index + 1, right_index):
                    list_x[i] = 0
                list_x[left_index] += 1
                list_x[right_index] += 1

        # 把list转成int
        next_palindrome = 0
        for i in list_x:
            next_palindrome = next_palindrome * 10 + i
        return next_palindrome

    # 给定任意数，计算下一个比它大的回文
    def firstPalindrome(self, x):
        if x == 1:
            return 1
        length = len(str(x))
        i = 10 ** (length - 1) + 1
        while i < x:
            i = self.nextPalindrome(i)
        return i

    def superpalindromesInRange(self, L: str, R: str) -> int:
        count = 0
        sqrt = self.firstPalindrome(int(math.sqrt(int(L))))
        while sqrt <= int(math.sqrt(int(R))):
            print(sqrt)
            count += 1
            sqrt = self.nextPalindrome(sqrt)
        return count

这样按照基本规律可以完成，通过所有检测点，并且打败95%的选手（估计剩下的都是打表把哈哈哈）。但是这个方法有五个特殊值，不是很优雅，怎么样消除这些得到更普遍的规律呢？有时间再更。