java - spoj 下一个回文中的时间限制超出错误

Question

我正在尝试解决 SPOJ 中的下一个回文问题。我在下面的 Java 代码中收到超出时间限制的错误。

“如果一个正整数在十进制中从左到右和从右到左读的表示相同，则称为回文。对于给定不超过 1000000 位的正整数 K，写出以下值输出大于 K 的最小回文。数字始终显示，不带前导零。"

import java.math.BigInteger;
import java.util.Scanner;

public class Nextpalindrome {
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner in =new Scanner(System.in);
        int t=in.nextInt();

        for (int i=1;i<=t;i++)
        {
            BigInteger bi = in.nextBigInteger();    
            String str=bi.toString();
            String str1=new String();
            String str2=new String();
            String str3=new String();
            String str4=new String();
            int l=str.length();
            int comp=0;
            if (l==2)
            {
                str1=str.substring(0,1);
                str2=str.substring(1,2);

                if (Integer.parseInt(str1)>Integer.parseInt(str2))
                str1=str1.concat(str1); 
                else if (Integer.parseInt(str2)>Integer.parseInt(str1))
                {
                str2=str2.concat(str2);             
                str1=str2;
                }
                else if (Integer.parseInt(str1)==Integer.parseInt(str2))
                {
                    int x=Integer.parseInt(str1)+1;
                    str1=Integer.toString(x);
                    str1=str1.concat(str1); 
                    }
            }

            if (l%2>0)
            {
                str1=str.substring(0,l/2);
                str2=str.substring((l/2)+1,l);
                str3 =str.substring(l/2,(l/2)+1);
                str4=new StringBuffer(str1).reverse().toString();
                BigInteger bi1 = new BigInteger(str1);
                BigInteger bi2 = new BigInteger(str2);

                comp= bi1.compareTo(bi2);

                int mid=Integer.parseInt(str3);
                if (comp==-1)
                {
                mid+=1;
                String str5=Integer.toString(mid);
                str1=str1.concat(str5);
                str1=str1.concat(str4);
                }
                else if (comp==1)
                {
                String str5=Integer.toString(mid);
                str1=str1.concat(str5);
                str1=str1.concat(str4);
                }
                else if (comp==0)
                {
                    mid+=1;
                String str5=Integer.toString(mid);
                str1=str1.concat(str5);
                str1=str1.concat(str4);
                }
            }
            if ((l>2)&&(l%2==0))
            {
                str1=str.substring(0,l/2);
                str2=str.substring(l/2,l);

                BigInteger bi1 = new BigInteger(str1);
                BigInteger bi2 = new BigInteger(str2);
                BigInteger bi3=new BigInteger("1");
                comp= bi1.compareTo(bi2);
                if (comp==-1)
                {
                bi1=bi1.add(bi3);
                str1=bi1.toString();
                str4=new StringBuffer(str1).reverse().toString();
                str1=str1.concat(str4);
                }
                else if ((comp==1)||(comp==0))
                {
               str4=new StringBuffer(str1).reverse().toString();
                str1=str1.concat(str4);
                }
            }



        System.out.println(str1);

        }

        in.close();     

    }

}

Answer 1

由于您想要找到大于 K 的最小回文，请考虑以下规则和逻辑:

• 为了使最小回文数大于 K，您必须使用所有数字。 (即 1122 => 1221 就是答案)。
• 奇数长度的数字只能有一位位且频率为 1，该数字将是中心数字，其他数字必须具有偶数频率(即 11121 => 11211 将是回答)。否则，您无法创建回文。
• 对于偶数长度的数字，所有数字的频率必须为偶数(示例，请参阅项目符号一)。否则，您无法创建回文。

我将从获取每个数字的频率开始，然后从那里开始。

希望这有帮助。