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

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

一个非常简单的优化方法是简单地从最高的3位数字开始，而不是最小的数字。由于解决方案最可能接近成对（999,999）而不是（100,100）。

Answer 2

该程序看起来非常好，给我。我会让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); 
} 

Answer 3

一个有用的机制是注意产品a * b的最高位不经常更改。例如。

a = 111; b = 112 a*b = 12432 
     ; b = 113 a*b = 12543 
     ; b = 114 a*b = 12654 
     ; ... 
     ; b = 180 a*b = 19980 
     ; b = 181 a*b = 20091 = (19980 + a) 

因此，对于所有的值之间（= 111，一个< b < 181），一个已经知道的MSB，其必须等于LSB或（a％10）*（B％10 ）％10 == MSB。

e.g. 
LSB = 1 --> a % 10 == 1, b % 10 == 1 
      OR a % 10 == 3, b % 10 == 7 
      OR a % 10 == 7, b % 10 == 3 
      OR a % 10 == 9, b % 10 == 9 

大多数有任何没有，或者只是一个候选人一套“B”的任何一对MSB中，％10

Answer 4

的步骤，我能得到的最少数量是要检查的时间375.考虑乘以三位数字，a1a2a3，由三位数字，b1b2b3：

JavaScript代码：

var modHash = new Array(10); 
var iterations = 0; 

for (var i=1; i<10; i++){ 
    modHash[i] = {0: [0]} 
    for (var j=1; j<10; j++){ 
    iterations ++; 
    var r = i * j % 10; 
    if (modHash[i][r]) 
     modHash[i][r].push(j); 
    else 
     modHash[i][r] = [j]; 
    } 
} 

var highest = 0; 

function multiples(x,y,carry,mod){ 

    for (var i in modHash[x]){ 
    var m = (10 + mod - i - carry) % 10; 

    if (modHash[y][m]){ 
     for (var j in modHash[x][i]){ 
     for (var k in modHash[y][m]){ 
      iterations ++; 
      var palindrome = num(9,modHash[y][m][k],x,9,modHash[x][i][k],y); 

      if (x == 3 && mod == 0){ 
      console.log(x + " * " + modHash[x][i][j] + " + " 
         + y + " * " + modHash[y][m][k] + ": " + palindrome); 
      } 

      var str = String(palindrome); 

      if (str == str.split("").reverse().join("") && palindrome > highest){ 
      highest = palindrome; 
      } 
     } 
     } 
    } 
    } 
} 

function num(a1,a2,a3,b1,b2,b3){ 
    return (100*a1 + 10*a2 + a3) 
     * (100*b1 + 10*b2 + b3); 
} 

var a3b3s = [[7,7,4],[9,1,0],[3,3,0]]; 

for (var i in a3b3s){ 
    for (var mod=0; mod<10; mod++){ 
    var x = a3b3s[i][0], 
     y = a3b3s[i][1], 
     carry = a3b3s[i][2]; 
    multiples(x,y,carry,mod); 
    } 
} 

console.log(highest); 
console.log("iterations: " + iterations); 

输出：

3 * 0 + 3 * 0: 815409 
3 * 7 + 3 * 3: 907809 
3 * 4 + 3 * 6: 908109 
3 * 1 + 3 * 9: 906609 
3 * 8 + 3 * 2: 907309 
3 * 5 + 3 * 5: 908209 
3 * 2 + 3 * 8: 907309 
3 * 9 + 3 * 1: 906609 
3 * 6 + 3 * 4: 908109 
3 * 3 + 3 * 7: 907809 
906609 
iterations: 375 

Answer 5

首先通过将6位数字分为3位来优化isPalindrome。即N = ABCDEF => a = ABC = N/1000，b = DEF = N％1000;然后反转b并返回== reverse_b;

其次，当生成回文循环直到max_palindrome_so_far/999这是您将使用的最小值。 max_palindrome_so_far最初等于N.

public class Solution { 

    public static boolean isPalindrome(int n){ 
     int a = n/1000; 
     int b = n%1000; 
     int d, r = 0, i = 3; 
     while(i-- > 0){ 
      d = b%10; 
      r = r*10 + d; 
      b = b/10; 
     } 
     if (a == r) 
      return true; 
     return false; 
    } 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int t = in.nextInt(); 
     for(int a0 = 0; a0 < t; a0++){ 
      int n = in.nextInt(); 
      int r=0, m=n; 
      int i,j; 
      for(i = 999;i>=100;i--){ 
       for(j = 999;j>=m/999;j--){ 
        if (i*j < n && i*j > 100000 && isPalindrome(i*j)){ 
         r = Math.max(i*j, r); 
         m = r; 
        } 
       } 
      } 

      // System.out.println(i + " * " + j + " = " + i*j); 

      System.out.println(r); 
     } 
    } 
}