Project Euler #4 最大回文数Java代码输出结果错误求解

代码问题说明 #

你的代码存在两个核心逻辑错误：

• 未做回文数大小比对，只要检测到回文就直接返回，无法保证返回值是最大值
• 提前终止遍历流程，第一个回文命中后就结束了所有循环，没有覆盖所有三位数乘积的组合

你当前的遍历顺序下，第一个命中的回文是999 * 581 = 580085，直接返回自然无法得到更大的正确结果906609。

修正后代码 #

修正思路为新增变量存储当前最大回文数，遍历所有组合时仅在找到更大的回文时更新存储值，全部遍历完成后再返回结果，还额外增加了剪枝逻辑提升运行效率：

public class Problem4 {

    public static void main(String[] args) {
        System.out.print(largestPalindrome());
    }
    
    static String largestPalindrome () {
        int maxPalindrome = 0;
        for (int j = 999; j > 99; j--) {
            for (int k = 999; k > 99; k--) {
                int product = j * k;
                // 剪枝：当前乘积已小于已知最大回文，后续k更小乘积只会更小，直接结束内层循环
                if (product <= maxPalindrome) {
                    break;
                }
                String s = String.valueOf(product);
                if (palindrome(s)) {
                    maxPalindrome = product;
                }
            }
        }
        return String.valueOf(maxPalindrome);
    }
    
    static boolean palindrome (String s) {
        for(int i = 0; i <= (s.length() / 2); i++) {
            if (s.charAt(i) != s.charAt(s.length()-i-1)) {
                return false;
            }
        }
        return true;
    }
}

内容的提问来源于stack exchange，提问作者Ayoub