0

我正在尝试下面的挑战。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);
}
4

1 回答 1

0

这不会完全解决您的问题，但希望能让您开始思考这个问题。

由于这是关于计算集合的基数，我们应该考虑如何构造该集合的元素，而不是如何检查元素是否在该集合中。

首先，尝试考虑构造特定长度的数字的方法。

我们将从一位数字开始。我们将这些表示为a. 如果我们取a并反转它，我们得到a. 当 this 加倍时，我们得到2a, this 总是偶数，因此总是以偶数结尾，因此没有。

接下来，1位数字。表示为abwherea和bare 数字。相反的是ba，总和的最右边的位置（我将从这里开始编号，从 开始0，以供将来参考）是(a+b)%10，所以只有当 和 b 中的一个恰好是奇数时，它的最后一位才是奇数。此外，a+b带有1or的进位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的组合a,c，以及3 位数字5的总和的独立值。希望要么我错了，要么你在尝试时得出同样的结论。b20 * 5 = 100

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

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

于 2016-08-08T03:17:41.580 回答