我怎样才能使这段代码更有效率？ 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，它总是偶数，因此总是以偶数结尾，因此有 none.

接下来，1 位数字。表示为 ab，其中 a 和 b 是数字。反过来是ba，和的最右边（我从这里开始编号，从0开始编号，以供以后参考）是(a+b)%10，所以这个的最后一位只有当和 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

满足这些规则的任何组合都应该有效。这应该给出 a,c 的 20 组合，以及 b 的 5 独立值，因此 3 位数字的总数为 20 * 5 = 100。希望要么我错了，要么你在尝试时得出相同的结论。

当你进一步扩展时，你应该注意到一些模式可以让你泛化到任何长度（我认为奇数长度和偶数长度之间可能存在一些重要的区别）。

实际上为您提供解决方案不会有成效（而且我确信它们已经存在于某个地方），但希望这可以改变您对如何着手解决问题的看法，以便您能够解决它。

我怎样才能使这段代码更有效率？ Java算法

How can I make this code more efficient? Java algorithm

java

regex

algorithm

performance

coding-efficiency