在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

回答

相關問題