0906. Super Palindromes

---

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:

Input: left = "4", right = "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.

Example 2:

Input: left = "1", right = "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.

---

解法1

蛮力.超时.

class Solution {
    public int superpalindromesInRange(String left, String right) {
        long l = Long.parseLong(left), r = Long.parseLong(right);
        int res = 0;
        for(long i = new Double(Math.sqrt(new Long(l).doubleValue())).longValue(); i * i < r; i++){
            if(helper(i) && helper(i * i))
                res++;
        }
        return res;
    }
    
    private boolean helper(long val){
        String str = Long.toString(val);
        for(int i = 0; i < str.length() / 2; i++)
            if(str.charAt(i) != str.charAt(str.length() - 1 - i))
                return false;
        
        return true;
    }
}

---

解法2

官方推荐的解法. 其实也是蛮力, 只不过没有我自己的那么蛮.

class Solution {
    public int superpalindromesInRange(String left, String right) {
        long l = Long.valueOf(left), r = Long.valueOf(right);
        // 最大长度10^18, 开方之后再长度减半的上限就是10^5
        int MAGIC = 100000;
        int res = 0;

        // count odd length;
        for (int k = 1; k < MAGIC; k++) {
            // 从k得到回文v
            StringBuilder sb = new StringBuilder(Integer.toString(k));
            for (int i = sb.length() - 2; i >= 0; --i)
                sb.append(sb.charAt(i));
            long v = Long.valueOf(sb.toString());
            
            // 回文v 平方运算之后判断是否符合范围条件
            v *= v;
            if (v > r) break;
            if (v >= l && isPalindrome(v)) res++;
        }

        // count even length;
        for (int k = 1; k < MAGIC; k++) {
            // 从k得到回文v
            StringBuilder sb = new StringBuilder(Integer.toString(k));
            for (int i = sb.length() - 1; i >= 0; --i)
                sb.append(sb.charAt(i));
            long v = Long.valueOf(sb.toString());
            
            // 回文v 平方运算之后判断是否符合范围条件
            v *= v;
            if (v > r) break;
            if (v >= l && isPalindrome(v)) res++;
        }

        return res;
    }

    public boolean isPalindrome(long x) {
        return x == reverse(x);
    }

    public long reverse(long x) {
        long ans = 0;
        while (x > 0) {
            ans = 10 * ans + x % 10;
            x /= 10;
        }

        return ans;
    }
}