子寒的博客
0%

leetcode906 Super Palindromes 解题报告

发表于 更新于 分类于

英文原题

Let’s say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

Example

1
2
3
4
Input: left = "4", right = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

分析

    这道题没想到好的方法，一开始用的是暴力破解，结果当然是超时，后来看来网上的方法。这题其实得找规律，在除了（1,4,9）之外的其他超级回文数的算数平方根都是有0,1,2组成，而且两头都是由1或者2构成。然后解法是用BFS。

python 代码

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
class Solution:
    def superpalindromesInRange(self, L, R):
        """
        :type L: str
        :type R: str
        :rtype: int
        """
        que = collections.deque(["11", "22"])
        candi = set()
        while que:
            size = len(que)
            for _ in range(size):
                p = que.popleft()
                candi.add(p)
                if int(p) ** 2 > int(R):
                    continue
                for j in ["0", "1", "2"]:
                    q = (p[:len(p)//2] + j + p[len(p)//2:])
                    que.append(q)
        candi.add("1")
        candi.add("2")
        candi.add("3")
        res = 0
        for cand in candi:
            if int(L) <= int(cand) ** 2 <= int(R) and self.isPalindromes(int(cand) ** 2):
                res += 1
        return res
                
            
    def isPalindromes(self, s):
        s = str(s)
        N = len(s)
        for l in range(1, N // 2):
            if s[l] != s[N - 1 - l]:
                return False
        return True