如何让此代码更高效？ 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位数字。希望我错了，或者当你尝试时，你会得出同样的结论。当你进一步扩展的时候，你应该注意到一些模式，允许你推广到任何长度（我认为可能有一些重要的奇数长度和偶数长度之间的区别）。

实际上，为您提供解决方案不会很有成效（我相信它们已经存在于某处），但希望这可以改变您对如何解决问题足以解决问题的看法。