# 906. Super Palindromes

### 906. Super Palindromes

1. 定义超级回文数为，是回文数，并且是回文数的平方
2. 给定范围[L,R]，求出超级回文数的个数

• 看数据范围，L和R都在10^18内
• 令a为其中一个超级回文数，那么a=b*b，b也是一个回文数，由于超级回文数在10^18以内，b的取值范围是10^9以内
• 由于b是回文数，只有两种情况，如果长度为奇数的话，那么b就是(abcd)x(dcba)，如果长度为偶数的话，那么b就是(abcd)(dcba)，那么小于10^9的回文数个数，不超过11w个
• 那么这个题的解题方案就是把所有的超级回文数枚举出来
• 当然要挑战速度的话，注意到超级回文数才70个，写死在代码里面绝对秒杀各种预处理代码

class Solution {
private static List<Long> allSuper;

private int[] split(int a) {
int[] ret = new int[10];
int idx = 0;
while (a != 0) {
ret[idx++] = a % 10;
a /= 10;
}
return Arrays.copyOf(ret, idx);
}

private int[] split(long a) {
int[] ret = new int[20];
int idx = 0;
while (a != 0) {
ret[idx++] = (int) (a % 10);
a /= 10;
}
return Arrays.copyOf(ret, idx);
}

private int joinToInt(int[] a) {
int ret = 0;
for (int i = a.length - 1;i >= 0;i--) {
ret = ret * 10 + a[i];
}
return ret;
}

private long joinToLong(int[] a) {
long ret = 0;
for (int i = a.length - 1;i >= 0;i--) {
ret = ret * 10 + a[i];
}
return ret;
}

private int[] reverse(int[] a) {
int[] ret = new int[a.length];
for (int i = 0;i < ret.length;i++) {
ret[i] = a[ret.length - i - 1];
}
return ret;
}

private int join(int[] a, int e) {
int[] ret = new int[a.length * 2 + 1];
for (int i = 0;i < a.length;i++) {
ret[i] = a[i];
}
ret[a.length] = e;
a = reverse(a);
for (int i = 0;i < a.length;i++) {
ret[a.length + i + 1] = a[i];
}
return joinToInt(ret);
}

private int join(int[] a) {
int[] ret = new int[a.length * 2];
for (int i = 0;i < a.length;i++) {
ret[i] = a[i];
}
a = reverse(a);
for (int i = 0;i < a.length;i++) {
ret[a.length + i] = a[i];
}
return joinToInt(ret);
}

private boolean isPalindrome(int[] a) {
int left = 0;
int right = a.length - 1;
while (right > left) {
if (a[right] != a[left]) {
return false;
}
right--;
left++;
}
return true;
}

long t = (long)x * x;
if (isPalindrome(split(t))) {
}
}

private void init() {
allSuper = new ArrayList<Long>();
for (int i = 1;i <= 9999;i++) {
int[] a = split(i);
a = reverse(a);

for (int j = 0;j <= 9;j++) {
}
}
}

public int superpalindromesInRange(String L, String R) {
init();

long l = Long.valueOf(L);
long r = Long.valueOf(R);

int count = 0;
for (int i = 0;i < allSuper.size();i++) {
if (allSuper.get(i) >= l && allSuper.get(i) <= r) {
count++;
}
}
return count;
}
}