java - 寻找回文的低效解决方案

Question

找出由两个n位数字的乘积构成的最大回文并返回mod 1337

从 n=1 到 n=8 的输入

public class Solution {
    public int largestPalindrome(int n) {
    int[] arr = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
    int max_palindrome = 0;
    for(int x = arr[n] - 1; x >= arr[n - 1]; x--){
        for(int y = arr[n] -1; y >= arr[n - 1]; y--){
            int maybe = x*y;
            if(is_Palindrome(maybe)){
                if(maybe > max_palindrome){
                    max_palindrome = maybe;
                }
            }
        }
    }
    return max_palindrome%1337;
    }

    public boolean is_Palindrome(int toCheck){
        char[] charArr = String.valueOf(toCheck).toCharArray();
        for(int i = 0; i < charArr.length; i++){
            if(charArr[i] != charArr[charArr.length - 1 - i]){
                return false;
            }
        }
        return true;
    }
}

由于时间问题，这在 n=4 处失败。我能做什么？

Answer 1

您可以减少内循环以从当前外循环值开始:

 01234
0*****
1 ****
2  ***
3   **
4    *

这将为您提供所有可能的对。那就是你需要运行 (n * (n+1))/2 而不是 n^2。

在你的检查回文函数中，你做了一个类似的多余工作:

您从右到左检查所有字符是否与对应字符相等，但您可以停在中间。因此，您只需要现在所需的一半比较操作。

如果 maybe 小于当前找到的最大回文数，您也可以完全跳过检查数字。目前您先检查，然后再决定它是否更大。

运行时性能的最后一击是，一旦到达小于当前候选回文的产品maybe 就停止计算行。由于您倒数，因此这一行丢失了:您不会用较小的数字获得更高的产品。

您的代码也有缺陷。高 n 值的乘积大于最大整数，将产生负值。您必须将代码切换为多头。

public class Solution {
    public long largestPalindrome(int n) {
        if( n==0 ) return 1;

        int[] arr = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
        long max_palindrome = 0;
        for (long x = arr[n] - 1; x >= arr[n - 1]; x--) {
            for (long y = x; y >= arr[n - 1]; y--) {
                long maybe = x * y;
                if (maybe <= max_palindrome) {
                    break;
                }

                if (is_Palindrome(maybe)) {
                    max_palindrome = maybe;
                    System.out.printf("Palindrome: %dx: %d, y: %d%n", max_palindrome, x, y);
                }
            }
        }
        return max_palindrome % 1337;
    }

    public boolean is_Palindrome(long toCheck) {
        String cand = String.valueOf(toCheck);
        final int len = cand.length() - 1;
        final int maxIdx = len >> 1;
        for (int i = 0; i <= maxIdx; i++) {
            if (cand.charAt(i) != cand.charAt(len - i))
                return false;
        }
        return true;
    }
}

谢谢你的问题:-)