java - 从两个三位数的乘积中优化最大的回文数？

Question

我正在研究一个面试问题，我被问到这个问题，我应该编写一个程序来从两个三位数的乘积中找到最大的回文。

这是 question

我想出了这种从底部开始的蛮力方法。

public class LargestPalindromeQuestion {

    public static void main(String[] args) {
        int value = 0;
        for (int i = 100; i <= 999; i++) {
            for (int j = i; j <= 999; j++) {
                int value1 = i * j;
                if (isPalindrome(value1) && value < value1) {
                    value = value1;
                }
            }
        }
        System.out.println(value);
    }

    private static boolean isPalindrome(final int product) {
        int p = product;
        int reverse = 0;
        while (p != 0) {
            reverse *= 10;
            reverse += p % 10;
            p /= 10;
        }
        return reverse == product;
    }
}

他们问我这个程序可以做哪些优化？我提到我们可以尝试修剪搜索空间并优化搜索空间中每个项目的检查步骤，但我很困惑如何在我的上述解决方案中实现这项工作？

我们可以在这个程序中做哪些优化？现在它正在执行 810000 步来寻找最大的回文。

要找到两个三位数中最大的回文，我们最少可以执行多少步？

Answer 1

我觉得这个程序非常好。我将使 i 循环计数从 999 下降到 100，并且我只会检查 j 值实际上给出了比当前最大值更大的产品。

这个程序能够很快完成，准确地说是 i == 952。这样做的数学原因是，一旦找到解决方案 906609 (993 * 913)，将不再可能找到较大因子较小的较大回文比 906609 的平方根，即 952.160...。

public static void main(String[] args) {
    int value = 0;
    for (int i = 999; i >= 100; i--) {
        int r = value / i;
        if (r >= i) {
            System.out.println("We broke at i = " + i);
            break;
        }
        for (int j = i; j > r; j--) {
            int value1 = i * j;
            if (isPalindrome(value1)) {
                value = value1;
                break;
            }
        }
    }
    System.out.println(value);
}