java - 使用 java 逻辑错误的 Project Euler 24

Question

我正在尝试解决问题 24 https://projecteuler.net/problem=24 我和 euler 项目的负责人在这个问题上花了很多时间，但仍然没有成功。

但现在不是问题所在，我想知道我的方法出了什么问题。

我使用简单的排列来获取最左边的数字，并从要找到的项中获取剩余的值(通过减去，即使用模运算符)。

Java 代码:

import java.util.ArrayList;

public class LexOrder
{

public static int factorial(int num)
{
    int res=1;
    if(num <= 1)
        return 1;

    while(num > 1)  
    {
        res *= num--;   
    }
    return res;
}

public static ArrayList<Integer> addValue(int digit, ArrayList<Integer> al)
{
    int temp=0, count=0;    
    while( count <= digit )
    {
        if( al.contains(count) )
            temp++;
     count++;
    }

    int val = digit+temp;

    //checking weather the new number exists in the ArrayList or not.
    while(true)
    {
        if(! al.contains(val) )
        {
            al.add(val);
            break;
        }
        else
        {
            val++;
        }
    }
    return al;
}

public static void main(String args[])
{
    ArrayList<Integer> al = new ArrayList<Integer>();   
    int index = 999999; 
    int numOfDigit = 10;

    if( factorial( numOfDigit ) > index && index >= 0)
    {
            System.out.println("Index Validated");
    }
    else
    {
            System.out.println("Index out of bounds");
            System.exit(0);
    }

    int digit, count=1;
    while( index !=0  )
    {
        digit = ( index / factorial( numOfDigit - count ) );
        al = addValue(digit, al);

        index = ( index % factorial( numOfDigit - count ) );

        if(index == 0)
            break;
        count++;
    }

    // Adding value in ascending order.
    int temp =0;
    while( al.size() < numOfDigit )
    {

        if(!al.contains(temp))
            al.add(temp);

    temp++;
    }

    System.out.println(al);
}
}

输出: [2, 7, 8, 3, 9, 1, 4, 5, 6, 0]

输出应该是: 2783915460

Answer 1

因此，在无法向您介绍确切的数字的情况下，我可以看出您管理数字的方式有问题:

int temp=0, count=0;    
while( count <= digit )
{
    if( al.contains(count) )
        temp++;
 count++;
}

int val = digit+temp;

这种方法尤其无法检查某些数字(特别是 digit 和 digit+temp 之间的数字)是否已在数组列表中。

我能够通过计算未使用的元素数量来修复它:

int val=0, count=0;
while( count < digit)
{   if( !al.contains(val++) )
        count++;
}