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次

在检查回文函数中，您可以使用类似的superflous函数：

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

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

运行时性能的最后一点是，一旦到达小于当前候选回文的乘积maybe，就停止计算行。由于您倒数，这一行将丢失：您将无法使用较小的数字获得较高的产品

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

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

谢谢你的提问：-）

Answer 2

@thst已经指出了一些很好的优化。我试过他的解决方案，但在n=5时仍然运行得很慢

如果分析显示使用字符串很慢（或者您只是不想这么做），那么您可以修改is_Palindrome（）以使用整数操作。我不会展示所有代码，只展示大纲和提示：

public boolean is_Palindrome(long toCheck)
{
    // TODO
    // Figure out how many digits toCheck has and the value of the
    // most significant. e.g. "2345" has a length of 4 and the value 
    // of the most significant is 1000.
    // You may know these from your array and so can pass them in...

    while(length > 1)
    {
        // In example 2345: left = 2, right = 5.
        long left = toCheck / msdValue;
        long right = toCheck % 10;

        if (left != right)
        {
            return false;
        }

        // TODO
        // So they matched eh? You need to remove the digits already checked
        // from toCheck. Least significant is easy: / 10.
        // Most significant needs to use the msdValue (and something else)

        // You stripped out 2 digits, so your length and the size of
        // the msdValue need to change to reflect that.
        //
        length -= 2;
        msdValue /= 100;
    }

    // We've done early return as soon as we found a pair of digits that
    // didn't match, so if we get here all the digits matched and so we've
    // got a palindrome.
    //
    return true;
}

嗯。在回答中加入一些评论：

我用C实现了@thst的解决方案。对于使用sprintf的字符串版本，n=7的时间大约是45秒。当用我的实现替换字符串计算时，时间始终在16秒左右-我们称之为3倍加速

然后，我将计算长度的循环替换为执行表格查找的函数

int numDigits(long num, long* msdValue)
{
    if (num >= 1000000000000000) { *msdValue= 1000000000000000; return 16; }
    // and so on...

这将时间缩短到了7.5秒，是“普通数学”的两倍多，是朴素字符串实现的6倍多

将numDigits()替换为就地版本而不是函数调用会产生一个微小但可测量的差异：在5.9s中持续运行-让我们调用它6秒

记住：这是C语言，因此结果可能不适用于Java

总而言之，这是一个非常方便的提醒，提醒你做事情的方法不止一种，如果你经常做一些小事的话，它们可能会很重要