479. 最大回文数乘积

「爱情、让人受尽委屈。」 2022-10-16 12:23 154阅读 0赞

> 你需要找到由两个 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);
        }
    }