题目描述
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
andR
are strings representing integers in the range[1, 10^18)
.int(L) <= int(R)
题意:如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为超级回文数。现在,给定两个正整数L
和R
(以字符串形式表示),返回包含在范围 [L, R]
中的超级回文数的数目。
算法1
题解:首先如果一个数字数字是超级回文数,那么他的平方根也是回文数。我们枚举其平方根即可,那么搜索范围就会降到$10^9$之内,但这仍然是一个非常大的数字。我们观察到回文数只是其中的很小的一部分,那么我们可以使用某种方法来构造所有的回文数。我们可以发现一个回文数的数值只由前面的一半确定,那么我们进一步只需要枚举前面这一半即可。那么时间复杂度降低到$10^5$,这是一个可以接受的时间复杂度了。
如何构造回文数呢?我们只需要枚举1-10000,作为回文数的前面一半,然后根据回文数的位数是奇数还是偶数可以生成两种情况:比如123,当是奇数的时候,我们生成12321,如果是偶数,我们生成123321。我们分别枚举奇数和偶数,那么我们生成的回文数也是分别单调递增的。因此,一旦我们生成的回文数超过了平方根的上界,直接跳出即可。
我们可以进一步的压缩枚举的下界,因为对于任何一个N
位的数字,第一个大于等于它的回文数的前面一半不小于该数字的前一半,所以我们可以把sqrt(L)
的前一半数字拿出来当作下界即可。
总的时间复杂度约为$O(L)^{\frac{1}{4}}$
C++ 代码
class Solution {
public:
typedef long long LL;
// 根据数字的前一半,生成奇数或者偶数的回文数字
LL genpalindrome(LL val,bool odd)
{
LL temp = val;
if(odd) temp = temp / 10;
while(temp > 0)
{
val = 10 * val + temp % 10;
temp = temp / 10;
}
return val;
}
// 获取搜索的下界
LL getLowerBound(LL l)
{
int digit = 0;
LL temp = l;
while(temp > 0)
{
temp = temp / 10;
digit ++;
}
digit = (digit + 1) / 2;
while(digit --)
l = l / 10;
return l;
}
// 判断是否是回文数字
bool ispalindrome(LL val)
{
string s = to_string(val);
int n = s.length();
for(int i = 0 , j = n - 1 ; i < j ; i ++ , j --)
if(s[i] != s[j])
return false;
return true;
}
int superpalindromesInRange(string L, string R) {
LL left = stol(L),right = stol(R);
LL l = (LL)sqrt(left),r = (LL)sqrt(right);
LL lower = getLowerBound(l),i = lower;
int res = 0;
// 分别枚举奇数和偶数
while(true)
{
LL cur = genpalindrome(i ++,true);
if(cur < l) continue;
if(cur > r) break;
LL super_cur = cur * cur;
if(ispalindrome(super_cur))
res ++;
}
i = lower;
while(true)
{
LL cur = genpalindrome(i ++,false);
if(cur < l) continue;
if(cur > r) break;
LL super_cur = cur * cur;
if(ispalindrome(super_cur))
res ++;
}
return res;
}
};