Project Euler 145 小案例未得到预期结果

Question

我正在做一个叫做Project Euler 145的项目，内容是：

有一些正整数n，它们的特点是，[ n + reverse(n) ]的结果全部是奇数（十进制）数字。比如说，36 + 63 = 99，还有409 + 904 = 1313。我们称这些数字为可逆数字；所以36、63、409和904都是可逆数字。n和reverse(n)都不能有前导零。

在一千以下，有120个可逆数字。

那么在十亿（10**9）以下，有多少个可逆数字呢？

我正在尝试以下代码（为了测试结果，我用10代替10^9，结果应该是零）：

def check(x):
    y = int(str(x)[::-1]) #x backwards
    #add the rev number to the original number (convert them to a list)
    xy = list(str(x+y))
    #a list of even digits.
    evens = ['0', '2', '4', '6', '8']
    #check if the number has any digits using intersection method.
    intersect = set(xy).intersection(set(evens))
    if not intersect:
        #if there was no intersection the digits must be all odd.
        return True
    return False

def firstCheck(x):
    if (int(str(x)[:1])+(x%10))%2 == 0:
        #See if first number and last number of x make an even number.
        return False
    return True

def solve():
    L = range(1, 10) #Make a list of 10
    for x in L:
        if firstCheck(x) == False:
            #This quickly gets rid of some elements, not all, but some.
            L.remove(x)
    for x in L:
        if check(x) == False:
            #This should get rid of all the elements.
            L.remove(x)
    #what is remaining should be the number of "reversible" numbers.
    #So return the length of the list.
    return len(L)

print solve()

这个代码分为两个部分：在solve方法里，有一个firstCheck和check。第一个检查是为了快速排除一些数字（这样当我创建一个10^9大小的列表时，可以节省一些内存）。第二个检查是用来去掉所有那些不被认为是“可逆数字”的数字。在第一个检查中，我只是看看第一个和最后一个数字是否组成一个偶数，如果是，就把这个数字排除掉。在check方法中，我把数字反转，两个数字相加，然后把结果变成一个列表，然后检查这个列表是否和偶数列表有交集，如果有，就把它从列表中去掉。最终的列表应该就是“可逆数字”的数量，所以我取这个列表并返回它的长度。对于range(1,10)，我得到的结果是2（而不是期望的零）。而且它没有排除的数字是[4,8]，我找不到原因。

Answer 1

这是一个Java的解决方案，执行这个方案大约需要3分钟。

public class Euler145 {

public static void main(String[] args) {

  int i, j, add, convert, count = 0;
  String get;
  StringBuilder rev;

 for ( i=0; i <= 1000000000; i++) {
        get = "" + i;
        rev = new StringBuilder(get);
        rev.reverse():
        convert = Integer.parseInt(rev.toString());
        add = convert + i;

        if (add % 2 != 0)  {

            while (add > 0)  {
                 j = add % 10;

                 if (j == 1 || j == 3 || j == 5 || j == 7 || j == 9)  {
                    add /= 10;
                    String leadZero = "" + i;
                    if (j == 0 && !leadZero.endsWith("0"))  {
                        count++;
                    }
                   }  else  {
                     break;
                 }
            }
        }
   }
      System.out.println(count);
 }
}

Answer 2

我看到两个问题。

首先，你在遍历一个列表的时候，修改了这个列表两次：

for x in L:
    if firstCheck(x) == False:
        #This quickly gets rid of some elements, not all, but some.
        L.remove(x)

这样做会导致一些意想不到的、难以预测的情况。你可以选择遍历这个列表的一个副本，或者直接使用列表推导式来过滤：

L = [x for x in L if firstCheck(x)]

等等。

第二，你没有检查并去掉前面的零，所以当你检查10的时候，它返回True，但实际上应该是False。解决了这两个问题后，你的代码看起来就能正常工作了：

>>> len(solve(10))
0
>>> len(solve(1000))
120

[我只是添加了一个参数来选择范围。]