java - 某些代码中错误数组索引超出范围

Question

我的递归函数中存在数组索引越界异常。有人可以尝试向我指出为什么会这样吗？这一行: return minChange(a, IntegerList);存在数组索引越界异常以及最有可能的这一行:

返回minimumValue(1 + minChange(a - d，integerList)，minChange(a，updatedList));

    /* Function minChange: Minimum Change
    Pseudo-code:
    minChange(0, ds)      = 0
    minChange(a, [])      = Failure
    minChange(a, d :: ds) = minChange(a,ds)                     if d > a
    minChange(a, d :: ds) = min(1 ++ minChange(a - d, d :: ds)  otherwise
     */
    public int minChange(int a, List<Integer> integerList) {

        //int minimumResult = 0;
        int indexNumber = 0;

        int d = integerList.get(indexNumber); (line 246)

        if(a == 0) {
            // If a is 0 return 0
            return 0;

        } else if(integerList.isEmpty()) {
            return -1;

        } else if(d > a) {

            integerList.remove(indexNumber); // Remove first element from list

            // Recursive call to minChange
            return minChange(a, integerList); (line 261)

        } else {
            // Create updatedList and remove first element
            List<Integer> updatedList = integerList;
            updatedList.remove(indexNumber);
            indexNumber++;

            return minimumValue(1 + minChange(a - d, integerList), minChange(a, updatedList)); (line 269)

        }


Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out-of-bounds for length 0
at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:246)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:261)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:269)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:269)
    at AlgorithmsSetZero.minChange(AlgorithmsSetZero.java:269)

如何修复此数组索引越界异常。看来有一根线需要修复。如果是这样我该如何修复这个错误？有哪些方法？

Answer 1

为什么失败:

导致越界异常的特定事件序列是，例如:

minChange(1, [4]) // goes into second-to-last (else if) case, since 4 > 1. 4 is then removed.
minChange(1, [])  // crashes

目前尚不清楚您的代码在这种情况下的用途，因为您的伪代码没有定义 minChange(a, ds)。

即使我们规定输入列表必须有多个项目，我们也经常会遇到同样的情况:

minChange(5,[4, 8])
minChange(1,[8])
minChange(1,[])

我不确定您打算在这里发生什么，但是，无论如何，还有其他问题......

错误:

您的代码中很可能存在此行的错误:

// this just creates another reference to the existing list
// https://stackoverflow.com/questions/6536094/java-arraylist-copy
// meaning: both recursive calls will operate on the same list
// even though one uses the "updatedList" reference and one uses "integerList"
List<Integer> updatedList = integerList;

此外，使用 indexNumber 表示存在错误，因为它仅在值为 0 时才使用 - 递增是毫无意义的。请记住，函数中的局部变量在每次递归调用中都会“重置”，除非您将它们作为参数传递。

调试策略:

首先，澄清您真正希望算法做什么。

然后，检查它实际上在做什么。作为一种调试技术，我建议在函数调用开始时添加一些打印语句:

System.out.println("minChange(" + a + ", " + integerList + ")");

...以便您可以查看崩溃前发生的情况的日志。您还可以使用调试器来实现此目的。

最后，一旦它适用于一些简单的情况，就编写一个模糊测试器，在一堆随机列表和不同大小的a上检查您的算法，看看是否有任何您需要的情况。错过了。