如何讓此代碼更高效？ Java算法

Question

我正在嘗試下面的挑戰。 https://www.hackerrank.com/contests/projecteuler/challenges/euler145/submissions/code/25262675

基本上，代碼需要反轉大約1-19位數字的不同長度，將這些數字相加在一起，然後檢查結果是否完全由奇數組成，前導0是不允許的（例如100應該被排除）。

我已經完善的代碼可以計算出這些數字，但是在網站上有一個超時時間，我覺得它的性能不夠好。

我試過使用正則表達式，但無法得到它正確排序，它影響結果。任何指導都是最好的方式來編寫它，以便它儘可能快地運行，這將非常有用，如果它需要使用正則表達式或其他任何東西。

public static void main(String[] args) { 

    Scanner scan = new Scanner(System.in); 
    long t = scan.nextInt(); //Number of numbers to test 
    for (int i = 1; i <= t; i++){ 
     long n = scan.nextLong(); 
     calc(n); //begins calculation 
    } 
} 

public static void calc(long n) 
{ 
    long reversible = 0; //Counter 
    for (long i = 1; i < n; i++) 
    { 
     if (i%10 != 0) //Makes sure number does not end with a zero 
     { 
      long reverse = 0; 
      long j = i; 
      long checkOdd; 
      //Reverse the number 
      while(j != 0) 
      { 
       reverse = reverse * 10; 
       reverse = reverse + j%10; 
       j = j/10; // 
      } 
      long result = i + reverse; //Add current number and reverse 
      while (result != 0) 
      { 
       //Check and remove numbers to see if odd or not 
       checkOdd = result%10; 
       if (checkOdd%2 == 0){ //Even detected, move to next number 
        result = 0;       
       } 
       result = result/10; //Move to next digit 
       //Counts and ensures we do not count the same number multiple times 
       if (checkOdd%2 == 1 && result == 0) 
       { 
        reversible = reversible + 1; 
       } 
      } 

      /** REGEX TEST CODE -- fails when result is 5 digits long after testing */ 
      /** if(Pattern.matches("\\d[^02468]", Long.toString(result))) 
      { 
       System.out.println(result); 
       reversible = reversible + 1; 
      }*/ 


     } 
    } 
    System.out.println(reversible); 
} 

Answer 1

這不會完全解決您的問題，但希望能讓您開始思考這個問題。由於這是關於計算集合的基數的，我們應該考慮如何構造該集合的元素，而不是如何檢查元素是否在該集合中。

首先，嘗試考慮如何構建特定長度的數字。

我們將從一位數字開始。我們將把它們表示爲a。如果我們拿a並將其撤銷，我們得到a。當它翻倍時，我們得到2a，這總是偶數，因此總是以偶數結尾，因此沒有。

接下來是1位數字。表示爲ab，其中a和b是數字。相反的是ba，這個總和的最右邊的位置（我會從這裏開始編號爲0，以備將來參考）的總和爲(a+b)%10，所以當b和b中的正好一個是奇數時，最後一位數字只是奇數。此外，a+b有一個1或0的進位，我們將這稱爲z。這對下一部分很重要。位置1的總和是(a+b+z)%10。已經確定a+b必須是奇數，z現在必須爲0才能保持這個奇數。所以a+b < 10。現在你只需要這個工作的組合數量和b。請注意，它們都不是0，因爲它們在數字的末尾。

a | b 
1 | 2,4,6,8 
2 | 1,3,5,7 
    ... 

當然，我們真的只需要能夠計數這些。所以對於a=1我們只需要知道b是偶數，所以有b<9有4種可能性。對於a=2,b是奇數和b<8，所以有4個選項。

你應該能夠重現這個想法的3位數字，並希望通過計算可能性的數量節省，而不產生或驗證任何可能性應該變得更加明顯。

編輯：順便說一句，沒有工作到那裏爲三位數abc，我得出這樣的結論：

a+c is odd 
a+c>=10 
b<=4 

任意組合出席會議的規則應該工作。這應該給20組合​​,5獨立的值爲b因此20 * 5 = 100共3位數字。希望我錯了，或者當你嘗試時，你會得出同樣的結論。當你進一步擴展的時候，你應該注意到一些模式，允許你推廣到任何長度（我認爲可能有一些重要的奇數長度和偶數長度之間的區別）。

實際上，爲您提供解決方案不會很有成效（我相信它們已經存在於某處），但希望這可以改變您對如何解決問題足以解決問題的看法。