在java中使用reverse（）与BigInteger

-2

我需要找到输入的下一个回文，使得数字不超过1000000 DIGITS。为此，我正在使用BigInteger，并且正在获取“超出时间限制”。在java中使用reverse（）与BigInteger

现在该做什么？

import java.util.*; 
import java.lang.*; 
import java.io.*; 
import java.math.BigInteger; 


class Ideone 
{ 
    static boolean palindrome(BigInteger a) 
    { 
     String b=""+a; 
     StringBuffer s=new StringBuffer(b); 
     StringBuffer c=s.reverse(); 
     String d=c.toString(); 

     return d.equals(b); 
    } 

    public static void main (String[] args) throws java.lang.Exception 
    { 
     Scanner sc=new Scanner(System.in); 
     int t=sc.nextInt(); 
     while(t-->0){ 
      BigInteger k=sc.nextBigInteger(); 
      try{for(BigInteger i=k.add(BigInteger.ONE);;i=i.add(BigInteger.ONE)){ 
       if(palindrome(i)){System.out.println(""+i); break;} 

      }//for 
      }catch(Exception e){} 


     }//wh 
    } 
}

来源

2014-07-16 RJ Rachana Bagde

TLE？什么是？ - –

@MarcoAcierno超出时间限制。 –

如果此代码有效，您可以将其发布到CodeReview。我会开始使用valueOf缓存至少一些值，为什么你将它们转换为字符串？ –

由于V-X指出，没有必要整个增量业务，因为我们可以扭转局面：而不是检查哪个数字是回文，我们可以首先创建回文并测试它们是否大于我们的目标数量。

想象一下你的电话号码是123456，最大的回文是什么？

是否有形式123xyz （x，y和z表示缺失的位数）溶液？这种形式只有一个回文编号：123321.但是因为123321 < 123456，那不是我们的答案。
那么124xyz怎么样？遵循相同的逻辑，我们发现只有一个这样的数字124421，它大于123456。
中间是否还有其他回文？由于123999和124000之间没有数字，我们已经证明不可以。
因此，我们的答案是124421.

概括起来就是我们所做的：我们采取了数上半年（123456 - > 123），反映它（123 - > 123321），发现它低于我们的目标，所以我们添加了1（123 - > 124）并对其进行了镜像（124 - > 124421），这就是我们的答案。如果我们的初始数字是123004，我们将立即接受123321作为我们的答案。

我会让你找出当你有一个奇数的数字时，如果你的号码是9999 ... 9的形式，会发生什么。顺便说一句，如果你正在测试回文，没有必要扭转数字。您可以简单地检查第一位数字是否等于最后一位数字，然后比较第二位数字和第二位数字，以此类推。由于您只扫描一次字符串，速度会更快。

来源

2014-07-16 17:47:30 biziclop

没有增量我怎样才能得到下一个数字？ –

想象一下，你的号码是123456，最大的回文是什么？有123xyz形式的解决方案吗？不，因为这种形式只有一个回文数：123321，<123456。那么124xyz呢？再次，只有一个这样的数字，124421.中间是否还有其他回文？不，我们已经证明了这一点。因此，我们的答案是124421.总结一下：取数字的前半部分（123456 - > 123），加1（123 - > 124）并镜像它（124 - > 124421），这就是你的答案。所有你需要解决的是你的号码是999123的情况。 – biziclop

@biziclop你的评论应该是一个答案;你的回答应该是一个评论。 –

通过BigInteger.ONE增加数字？对于有1000000位数的数字，这肯定是一个笑话... 你觉得需要多长时间？

任务扰流板（请无视）：

如何削减数量的数字的一半数量和拼接与此相反的一半，并在必要时做的一个变化？它会太难吗？

如果您知道，问题与时间有关，您应该通过一些时间测量和记录来环绕代码。您应该记录您有多少位数字，以及验证回文多少时间。你应该先从非常小的数字开始。

来源

2014-07-16 17:46:52

你解决了整个问题，并杀死了OP = \ fun +1 –

的乐趣不要把我的评论过于直接。现在你的答案看起来只是一个评论... –

您应该尽量减少您对BigInteger的使用，因为String和BigInteger之间的所有转换都会占用不必要的时间。只需使用next()而不是nextInt()即可从扫描仪获取每个号码，并将其保存为String。一旦你有了这个数字，就有五种情况需要考虑，你可以在一系列if/else if区块中进行编程。

案例1 - 输入无效 - 它不是完全由数字组成。目前还不清楚你想如何处理这个问题，或者你是否想要打扰。
案例2 - 输入完全由九个组成。如果有n九，那么下一个回文由一个零，另一个零组成。例如，9999之上的下一个回文是10001。
案例3 - 数字的后半部分相反，小于数字的前半部分。你可以使用字符串比较 - 没有必要将任何东西转换成任何数字类型。如果有奇数位数（例如2n+1），则可以向下舍入（至n），以确定要检查的位数。在这种情况下，下一个回文由数字的前半部分组成，然后是中间数字（如果有），然后数字的前半部分反转。例如，如果输入是5678123，则比较567到321。由于567更大，因此此情况适用，输出应为5678765。
案例4 - 其他情况均不适用，即使是位数。取数字的前半部分并添加一个（如果您愿意，可以使用BigInteger来执行此步骤）。产出是由此产生的，其次是逆转。例如，如果输入是123789，那么数字的前半部分是124，输出应该是124421。
案例5 - 其他情况均不适用，奇数位数。取数字的前半部分;计算出包含多少位数时向上舍入。例如，如果输入是1234789，则采取1234。现在添加一个，然后输出结果，然后是除结果最后一位数字之外的所有数字。在本例中，您将输出1235，然后是123的逆转 - 即1235321。就像case 4一样，您可以使用BigInteger进行添加。

来源

2014-07-16 22:55:43

在java中使用reverse（）与BigInteger

回答

相关问题