Skip to content

906. Super Palindromes

906. Super Palindromes

题目: https://leetcode.com/problems/super-palindromes/

难度: Hard

题意：

  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;
    }

    private void judgeAndAdd(int x) {
        long t = (long)x * x;
        if (isPalindrome(split(t))) {
            allSuper.add(t);
        }
    }

    private void init() {
        allSuper = new ArrayList<Long>();
        allSuper.add(1L);
        allSuper.add(4L);
        allSuper.add(9L);
        for (int i = 1;i <= 9999;i++) {
            int[] a = split(i);
            a = reverse(a);
            judgeAndAdd(join(a));

            for (int j = 0;j <= 9;j++) {
                judgeAndAdd(join(a, 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;
    }
}
回到顶部