java 中的超级回文

Question

此代码的运行时间为 269 毫秒，谁能帮助我降低此解决方案的复杂性？

输入：左=“4”，右=“1000”

输出：4

解释：4、9、121、484是超级回文。注意676不是超级回文：26 * 26 = 676，但是26不是回文。

class Solution {
    public int superpalindromesInRange(String left, String right) {     
        int FIX = 100000;
        int ans = 0;
        long L = Long.valueOf(left);
        long R = Long.valueOf(right);
        // Odd palindrome 1234321
        for(int i = 1; i < FIX; i++){
            StringBuilder str = new StringBuilder(Integer.toString(i));
             for (int j = str.length() - 2; j >= 0; j--)
                str.append(str.charAt(j));
            long p = Long.valueOf(str.toString());
            long p_square = p * p;
            if(p_square > R) break;
            if(p_square >= L && isPalindrome(p_square)) ans++;
        }
        //even palindrome 12344321
        for(int i = 1; i < FIX; i++){
            StringBuilder str = new StringBuilder(Integer.toString(i));
            for (int j = str.length() - 1; j >= 0; j--)
                str.append(str.charAt(j));
            long p = Long.valueOf(str.toString());            
            long p_square = p * p;
            if(p_square > R) break;
            if(p_square >= L && isPalindrome(p_square)) ans++;
        }
        return ans;
    }
    public boolean isPalindrome(long val){
        long res = 0;
        long temp = val;
        // System.out.println(val);
        while(temp > 0){
            res = 10 * res + temp % 10;
            temp = temp / 10;
        }
        return res == val;
    }
}

Answer 1

我不明白 super palindrome 部分。
但是，这是 isPalindrome:

的一个更简单的实现

public boolean isPalindrome(long val) {

    char[] buf = Long.toString(val).toCharArray();

    for (int i = 0, j = buf.length - 1, iMax = buf.length >> 1; i < iMax; ++i) {
        if (buf[i] != buf[j - i])
            return false;
    }

    return true;
}

顺便说一句，用Long.parseLong代替Long.valueOf。

Long.parseLong returns long（原始类型）
Long.valueOf returns Long (object)

编辑 1

我理解你的isPalindrome方法并做了一些性能测试。

start = System.currentTimeMillis();
for (long xx = 1L; xx < 100000000L; ++xx)
    isPalindrome(xx); // Your implementation
System.out.println((System.currentTimeMillis() - start) + " ms.");

start = System.currentTimeMillis();
for (long xx = 1L; xx < 100000000L; ++xx)
    isPalindrome_(xx); // My implementation
System.out.println((System.currentTimeMillis() - start) + " ms.");

结果：

1877 ms.
3805 ms.

你的实现比我的快。

编辑 2

你的算法很干净，我通过移出循环 for StringBuilder:

的实例化发现了一点改进

public int superpalindromesInRange(String left, String right) {

    StringBuilder str = new StringBuilder();

    int ans = 0;
    long L = Long.parseLong(left);
    long R = Long.parseLong(right);
    
    // Odd palindrome 1234321
    for (int i = 1; i < Integer.MAX_VALUE; i++) {
        str.setLength(0);
        str.append(i);
        for (int j = str.length() - 2; j >= 0; j--)
            str.append(str.charAt(j));
        long p = Long.parseLong(str.toString());
        long p_square = p * p;
        if (p_square > R)
            break;
        if (p_square >= L && isPalindrome(p_square))
            ans++;
    }
    
    // Even palindrome 12344321
    for (int i = 1; i < Integer.MAX_VALUE; i++) {
        str.setLength(0);
        str.append(i);
        for (int j = str.length() - 1; j >= 0; j--)
            str.append(str.charAt(j));
        long p = Long.parseLong(str.toString());
        long p_square = p * p;
        if (p_square > R)
            break;
        if (p_square >= L && isPalindrome(p_square))
            ans++;
    }
    return ans;
}

我进行了大值性能测试：

long left = 4L;
long right = 1000000000L;

System.out.println("Warmup:");
start = System.currentTimeMillis();
for (int xx = 0; xx < 10000; ++xx)
    superpalindromesInRange(Long.toString(left), Long.toString(right));
System.out.println((System.currentTimeMillis() - start) + " ms.");

start = System.currentTimeMillis();
for (int xx = 0; xx < 10000; ++xx)
    superpalindromesInRange2(Long.toString(left), Long.toString(right));
System.out.println((System.currentTimeMillis() - start) + " ms.");

System.out.println("Test:");
start = System.currentTimeMillis();
for (int xx = 0; xx < 10000; ++xx)
    superpalindromesInRange(Long.toString(left), Long.toString(right));
System.out.println((System.currentTimeMillis() - start) + " ms.");

start = System.currentTimeMillis();
for (int xx = 0; xx < 10000; ++xx)
    superpalindromesInRange2(Long.toString(left), Long.toString(right));
System.out.println((System.currentTimeMillis() - start) + " ms.");

结果：

Warmup:
675 ms.
335 ms.
Test:
372 ms.
204 ms.

通过在 for 循环之外实例化 StringBuilder，执行时间几乎减半。

Answer 2

先生成超级回文的平方根。然后平方，看这个平方是不是也是回文

要生成平方根，您首先需要一个下限和一个上限。使用左边的平方根的天花板和右边的平方根的地板。接下来尝试只生成确实是回文的数字。在您的示例中，界限是 2 和 31。所有一位数字都是回文，因此您需要检查 2 到 9 中的每一个。剩下的方式您只需要考虑 11 和 22，因为它们是唯一的两位数范围内的回文。你究竟是如何生成那些我不太清楚的。可能你只需要看33就可以确定它越界了。

推广到三位数、四位数等，将是一个单独的挑战，但我确信可以设计出一些非常优化的解决方案。

即使检查回文很方便，将数字作为字符串处理也可能效率低下。看看你是否可以在 int 数学中进行检查或至少你的生成。

Answer 3

好吧，这个运行只用了 13 毫秒（没有打印）。但我知道它可以通过生成一阶回文来改进，按顺序开始。但我会远离任何基于字符串的解决方案。

for (int i = 1; i < 100000; i++) {
    if (isPalindrome(i)) { 
        int k = i*i;
        if (isPalindrome(k)) {
           System.out.println(k);
        }
    }
}
        
public static boolean isPalindrome(int v) {
    int k = 0;
    int save = v;
    while (v > 0) {
        int d = v%10;
        k = k*10 +d;
        v/=10;
    }
    return k == save;
}

Answer 4

我认为你只需要一个 for 循环（除了将在该循环内的回文检查）从左到右的 sqrt。

    for(long i = L; i<Math.sqrt(R) ; i++){
      if(isPalidrome(i) && isPalindrom(i*i)){ans++;}

}

不知道我是否理解你的问题

Answer 5

终于找到了回文生成器的另一个优化
我使用与 isPalindrome:

相同的算法

long j = 0L;
long temp = i;

while (temp > 0L) {
    j = (10L * j) + (temp % 10L);
    temp /= 10L;
}

Math.floor(Math.log10(i)) + 1) 给出数字 class（位数）。
方法是：

public int superpalindromesInRange3(String left, String right) {

    // StringBuilder str = new StringBuilder();

    int ans = 0;
    long L = Long.parseLong(left);
    long R = Long.parseLong(right);

    // Odd palindrome 1234321
    for (long i = 1L; i < Long.MAX_VALUE; i++) {
        long p = i;
        if (i > 9) {

            long j = 0L;
            long temp = i / 10L;

            while (temp > 0L) {
                j = (10L * j) + (temp % 10L);
                temp /= 10L;
            }

            p = (long)(i * Math.pow(10, Math.floor(Math.log10(i / 10L)) + 1) + j);
        }
        long p_square = p * p;
        if (p_square > R)
            break;
        if (p_square >= L && isPalindrome(p_square))
            ans++;
    }

    // Even palindrome 12344321
    for (int i = 1; i < Integer.MAX_VALUE; i++) {

        long j = 0L;
        long temp = i;

        while (temp > 0L) {
            j = (10L * j) + (temp % 10L);
            temp /= 10L;
        }

        long p = (long)(i * Math.pow(10, Math.floor(Math.log10(i)) + 1) + j);

        long p_square = p * p;
        if (p_square > R)
            break;
        if (p_square >= L && isPalindrome(p_square))
            ans++;
    }
    return ans;
}

结果比使用 StringBuilder.

构造回文结构快两倍

java 中的超级回文

Super Palindromes in java

java

math

palindrome