java - 我的 Havel-Hakimi 算法代码有什么问题？

Question

我正在尝试练习我的编码技能，我在 Dailyprogrammer Reddit 上发现了一个使用 Havel-Hakimi 算法 (https://www.reddit.com/r/dailyprogrammer/comments/bqy1cf/20190520_challenge_378_easy_the_havelhakimi/) 的编码练习，但它总是返回错误的 boolean 值。

我试图在每个循环中检查我的进程，以确保所有方法都在做正确的工作并且输出是我所期望的，但它总是返回错误的 boolean 值。

public static void main(String[] args) {
    int[] answer = {16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16};
    System.out.println(hh(answer));
    ArrayList<Integer> temp = new ArrayList<Integer>();
    System.out.println(temp.size());
}

//This is the actual Havel-Hakimi Algorithm Method
public static boolean hh(int[] answer) {
    ArrayList<Integer> temp = new ArrayList<Integer>();
    int n;
    for(int i = 0; i < answer.length; i++) {
        temp.add(answer[i]);
    }
    for(int j = 0; j < temp.size(); j++) {
        if(temp.get(j) == 0)
            temp.remove(j);
    }

    if(temp.size() == 0) {
        return true;
    }
    Collections.sort(temp);
    for(int t = 0; t < temp.size(); t++) {
    }
    n = temp.get(0);
    temp.remove(0);
    if(n > temp.size()) {
        return false;
    }
    for(int k = 0; k < n; k++) {
        temp.set(k, temp.get(k) - 1);
    }
    int[] newAnswer = new int[temp.size()];;
    for(int l = 0; l < temp.size(); l++) {
        newAnswer[l] = temp.get(l);
    }
    return hh(newAnswer);

}

使用 main 方法中提供的数组，“hh”方法应该返回 true 但它返回 false。

Answer 1

问题在于 Collections.sort(temp)，它按升序对输入集合进行排序，而您希望它按降序排序。您可以使用 Collections.sort(temp, Collections.reverseOrder())

这是您代码中的逻辑问题。

我应该指出，有些语句在您的代码中是不必要的(例如 Collections.sort(temp) 之后的 for 循环，它什么都不做)，其他语句可以增强(比如前两个for循环，而不是复制整个数组，然后过滤它，为什么不只复制需要的元素？)，你也可以通过使用a来避免使用递归while(true) 循环。

这是一个可以帮助您解决问题的代码:

public static void main(String[] args) {
    int[] answer = {16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16};
    System.out.println(hh(answer));
}

//This is the actual Havel-Hakimi Algorithm Method
public static boolean hh(int[] answer) {
    while(true) {
        // Filter zero's from answer array 
        ArrayList<Integer> temp = new ArrayList(Arrays
                // get a Stream<Integer> from int[]
                .stream(answer)
                // filter zero's (this returns an IntStream)
                .filter(a -> a != 0)
                // reconvert it to Stream<Integer>
                .boxed()
                // Collect the stream as a List<Integer>
                .collect(Collectors.toList()));

        // Check the filtered array if it became empty after filtering
        if (temp.isEmpty()) {
            return true;
        }

        // Sort the filtered array in descending order
        Collections.sort(temp, Collections.reverseOrder());

        // Remove the first element (note that remove method returns the removed element)
        int n = temp.remove(0);

        // Check if the first removed element is larger than the new size of the array
        if (n > temp.size()) {
            return false;
        }

        // Reconstruct the input array for the next iteration
        answer = IntStream.range(0, temp.size())
                .map(i -> i < n ? temp.get(i) - 1 : temp.get(i))
                .toArray();
    }
}

如果您不熟悉 Streams，您可以简单地使用 for 循环。