题目链接

最大回文数乘积

题目描述

image.png

实现代码

个人实现代码(超时):

  1. class Solution {
  2. public int largestPalindrome(int n) {
  3. int start = 1;
  4. int end = 9;
  5. for(int i=2; i<=n; i++) {
  6. start = start*10 + 1;
  7. end = end*10 + 9;
  8. }
  9. long result = 0;
  10. long longRes = 0;
  11. for(int i=end; i>=start; i--) {
  12. for(int j = end; j >= start ;j--) {
  13. longRes = i * j;
  14. if(isHuiwen(longRes)) {
  15. result = result < longRes ? longRes : result;
  16. }
  17. }
  18. }
  19. return (int)(result % 1337);
  20. }
  21. private boolean isHuiwen(long x) {
  22. long temp = x % 10;
  23. long origin = x;
  24. x /= 10;
  25. if(temp == 0) {
  26. if(x > 0) {
  27. return false;
  28. }
  29. return true;
  30. }
  31. while(x != 0) {
  32. temp = temp * 10 + x % 10;
  33. x /= 10;
  34. }
  35. return temp == origin;
  36. }
  37. }

参考官方思路:

  1. 首先构造回文数;
  2. 然后判断该回文数是否可以拆分为两个n位的数

思想原理:对于两个n位数的乘积,最大值的位数为2n;
实现代码:

  1. class Solution {
  2. public int largestPalindrome(int n) {
  3. if (n == 1) {
  4. return 9;
  5. }
  6. int upper = (int) Math.pow(10, n) - 1;
  7. int ans = 0;
  8. for (int left = upper; ans == 0; --left) { // 枚举回文数的左半部分
  9. long p = left;
  10. for (int x = left; x > 0; x /= 10) {
  11. p = p * 10 + x % 10; // 翻转左半部分到其自身末尾,构造回文数 p
  12. }
  13. for (long x = upper; x * x >= p; --x) {
  14. if (p % x == 0) { // x 是 p 的因子
  15. ans = (int) (p % 1337);
  16. break;
  17. }
  18. }
  19. }
  20. return ans;
  21. }
  22. }