题目

Let’s say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

Example 1:

  1. Input: left = "4", right = "1000"
  2. Output: 4
  3. Explanation: 4, 9, 121, and 484 are superpalindromes.
  4. Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Example 2:

  1. Input: left = "1", right = "2"
  2. Output: 1

Constraints:

  • 1 <= left.length, right.length <= 18
  • left and right consist of only digits.
  • left and right cannot have leading zeros.
  • left and right represent integers in the range [1, 10^18].
  • left is less than or equal to right.

题意

定义一个超级回文数n，具有如下性质：n本身是回文数，n的平方根同样是回文数。找到指定范围内所有的超级回文数。

题意

直接构造所有的1e10之内的回文数，判断它们的平方是否在范围内且同样为回文数。注意回文数的长度既可能是奇数也可能是偶数。

思路

Java

  1. class Solution {
  2.     private int count = 0;
  4.     public int superpalindromesInRange(String left, String right) {
  5.         long a = Long.parseLong(left), b = Long.parseLong(right);
  6.         count = 0;
  8.         dfs("", a, b);
  9.         for (int i = 0; i <= 9; i++) {
  10.             dfs(String.valueOf(i), a, b);
  11.         }
  13.         return count;
  14.     }
  16.     private void dfs(String s, long left, long right) {
  17.         if (s.length() > 9) return;
  20.         if (s.length() > 0) {
  21.             long x = Long.parseLong(s);
  22.             if (x * x > right) return;
  23.             if (s.charAt(0) != '0' && x * x >= left && isPalindrome(x) && isPalindrome(x * x)) count++;
  24.         }
  26.         for (int i = 0; i <= 9; i++) {
  27.             dfs(i + s + i, left, right);
  28.         }
  29.     }
  31.     private boolean isPalindrome(long x) {
  32.         char[] s = String.valueOf(x).toCharArray();
  33.         int i = 0, j = s.length - 1;
  34.         while (i < j) {
  35.             if (s[i++] != s[j--]) return false;
  36.         }
  37.         return true;
  38.     }
  40.     public static void main(String[] args) {
  41.         Solution s = new Solution();
  42.         s.superpalindromesInRange("4", "1000");
  43.     }
  44. }