479. 最大回文数乘积

 

你需要找到由两个 n 位数的乘积组成的最大回文数。

由于结果会很大,你只需返回最大回文数 mod 1337得到的结果。

示例:

输入: 2

输出: 987

解释: 99 x 91 = 9009, 9009 % 1337 = 987

说明:

n 的取值范围为 [1,8]。

 

class Solution {
    public int largestPalindrome(int n) {
        /**
        n位数乘n位数最大应该是2*n位数
         那么就构建一个回文数(通过前两位进行构建),然后判断他是否能由两个n位数相乘得来
         */

         long max=(long)(Math.pow(10,n)-1); //当前位数,能取到的最大值
         long min=(long)(Math.pow(10,n-1));//当前位数,能取到的最小值
         long cur=(long)(max*max/Math.pow(10,n));  //当前数从max开始,不断-- 最小是min

         if(n==1){
             return 9;
         }
        
            while(cur>=min){
                   long target=create(cur);
               for(long i=max;i>=min;i--){
                
                   if(i*i<target){//一定要有,否则比99*99大的数产生 比如9889 这种情况发生
                       break;
                   }
                   
                  
                   if(target%i==0){
                       //说明可以由两位数想乘而得
                       
                       return (int)(target%1337);
                   }
               }
                //没找到, cur--  99->98->97
                cur--;
            }
         
            return -1;

    }
    //根据当前数,生成回文串
    public long create(long n){
        
        StringBuilder sb=new StringBuilder(String.valueOf(n));
        String str1=sb.toString();
        String str2=sb.reverse().toString();
        return Long.parseLong(str1+str2);
    }
}

 

    原文作者:CaesarChang
    原文地址: https://blog.csdn.net/weixin_45434902/article/details/117394826
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞