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
LandR(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) <= 181 <= len(R) <= 18LandRare strings representing integers in the range[1, 10^18).int(L) <= int(R)
Approach #1: Math. [Java]
class Solution {
public int superpalindromesInRange(String L, String R) {
Long l = Long.valueOf(L), r = Long.valueOf(R);
int result = 0;
for (long i = (long)Math.sqrt(l); i * i <= r;) {
long p = nextP(i);
if (p * p <= r && isP(p * p)) {
result++;
}
i = p + 1;
}
return result;
}
private long nextP(long l) {
String s = Long.toString(l);
int N = s.length();
String half = s.substring(0, (N + 1) / 2);
String reverse = new StringBuilder(half.substring(0, N/2)).reverse().toString();
long first = Long.valueOf(half + reverse);
if (first >= l) return first;
String nextHalf = Long.toString(Long.valueOf(half) + 1);
String reverseNextHalf = new StringBuilder(nextHalf.substring(0, N/2)).reverse().toString();
long second = Long.valueOf(nextHalf + reverseNextHalf);
return second;
}
private boolean isP(long l) {
String s = "" + l;
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
}
Reference:
Calculating the sqrt of nums from [L, R] (denote with ‘s‘)
finding the front half of ‘s‘ (denote with ‘half‘)
the combination of the front half and its reverse (denote with ‘p‘)
if p * p >= l and p * p <= r:
judge p * p is palindromes or not
else :
Calculating the combination of the front half + 1 and its reverse (denote with ‘p‘)
Reference:
https://leetcode.com/problems/super-palindromes/discuss/170774/Java-building-the-next-palindrome
原文：https://www.cnblogs.com/ruruozhenhao/p/10914667.html