难度: Hard
原题连接
内容描述
Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.
Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].
Example 1:
Input: L = "4", R = "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.
Note:
1 <= len(L) <= 18
1 <= len(R) <= 18
L and R are strings representing integers in the range [1, 10^18).
int(L) <= int(R)
思路 1 - 时间复杂度: O(lgR - lgL)- 空间复杂度: O(1)******
开始照着leetcode 564 改了改，超时了
class Solution(object):
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
def nearestPalindromic(n):
prefix = int(n[:(len(n)+1)//2])
candidates = set(['1' + '0' * (len(n)-1) + '1']) # 进位减位可能性
for i in map(str, [prefix, prefix+1]): # 前半部分+1，+0可能性
candidates.add(i + [i, i[:-1]][len(n) & 1][::-1])
candidates.discard(n)
candidates.discard('')
res = sys.maxsize
for cand in candidates:
if int(cand) > int(n):
res = min(res, int(cand))
return res
def isPalindrome(x):
return str(x) == str(x)[::-1]
res = 0
start = int(sqrt(int(L)))
start = start + 1 if start ** 2 < int(L) else start
while start ** 2 <= int(R):
if isPalindrome(start):
if isPalindrome(start ** 2):
res += 1
start = int(nearestPalindromic(str(start)))
return res
思路 2 - 时间复杂度: O(lglgR - lglgL)- 空间复杂度: O(1)******
参考wnmmxy
首先我们知道一个数字在L和R之间，然后它同时还是parlindrome，然后它的开方也是parlindrome，又由于一个parlindrome是可以由一个更小的数字build出来的
例如1001是由 10 + 01 build出来的， 10101 是由 10 + 1 + 01 build出来的
所以对于L和R，我们可以先拿到它们的sqrt 即left与right的范围，然后得到可以build出它们的sqrt的数字范围start和end
对于start和end中间的任何一个数字我们都可以build出两个parlindrome：
- num1 = int(x + x[::-1])
- num2 = int(x + x[:-1][::-1])
然后我们只需要判断这两个数字的平方是否是parlindrome且在L和R之间即可，满足的话res就加1
beats 38.36%
class Solution(object):
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
L, R = int(L), int(R)
left = int(math.floor(math.sqrt(L)))
right = int(math.ceil(math.sqrt(R)))
n1, n2 = len(str(left)), len(str(right))
n1 = n1 // 2 + 1 if n1 & 1 else n1 // 2
n2 = n2 // 2 + 1 if n2 & 1 else n2 // 2
start = int('1'+'0'*(n1-1))
end = int('9'*n2) + 1
res = 0
for i in range(start, end):
x = str(i)
num1 = int(x + x[::-1])
num2 = int(x + x[:-1][::-1])
for num in [num1, num2]:
cand = num * num
if L <= cand <= R and str(cand) == str(cand)[::-1]:
res += 1
return res思路 3 - 时间复杂度: O(lglgR - lglgL)- 空间复杂度: O(1)******
参考tell you how to get all super palindrome(detailed explanation)
we can construct in two steps:
1. Get all palindrome number < 10^9 in res(because the input < 10^18)
2. Traverse each number in res,determin whether the square is a palindrome
The first question is how to approach the first step, apparently we cannot traverse all number because 10^9 is too large.
The key is 'construct it' instead of 'judge it one by one'.
Every palindrome number can be divided into 3 part, I call it left part, middle part and right part.
For instance, 12121 can be divided into '12', '1', '21', corresponding left part, middle part, right part.
As for 123321, it can be divided into '123', '', '321'.
For each single number x, we can construct 11 palindrome number, which are xx,x0x,x1x,..,x9x, and that is what we need.
res = [1,2,3,4,5,6,7,8,9] # initial
for i in range(1,10000): # we only need at most four digits to consturct nine digits
s1 = str(i) + str(i)[::-1]
res.append(s1)
for j in range(10):
s2 = str(i) + str(j) + str(i)[::-1]
res.append(s2)
so, the total number in res is 11*10000. Apparently we can easily implement the second step by traversing the res!
def isPalin(s):
return s == s[::-1]
res = list(map(int, res))
res.sort()
ans = []
for val in res:
s = str(val**2)
if isPalin(s):
ans.append(int(s))
print(ans)
我们可以事先算出1到10^18次方之间(inclusive)所有的super parlindrome，然后算出其中在L和R之间的个数即可
然后1到10^18次方之间(inclusive)所有的super parlindrome就是:
[1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001,
1234321, 4008004, 100020001, 102030201, 104060401, 121242121,
123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201,
12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001,
1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121,
1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004,
4004009004004, 100000020000001, 100220141022001, 102012040210201,
102234363432201, 121000242000121, 121242363242121, 123212464212321,
123456787654321, 400000080000004, 10000000200000001, 10002000300020001,
10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001,
10201020402010201, 10203040504030201, 10205060806050201, 10221432623412201,
10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121,
12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321,
12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004]
beats 100%
class Solution(object):
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
self.supers = [1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001,
1234321, 4008004, 100020001, 102030201, 104060401, 121242121,
123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201,
12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001,
1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121,
1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004,
4004009004004, 100000020000001, 100220141022001, 102012040210201,
102234363432201, 121000242000121, 121242363242121, 123212464212321,
123456787654321, 400000080000004, 10000000200000001, 10002000300020001,
10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001,
10201020402010201, 10203040504030201, 10205060806050201, 10221432623412201,
10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121,
12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321,
12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004]
res = 0
for num in self.supers:
if num >= int(L) and num <= int(R):
res += 1
return res