我正在尝试练习我的编码技能,我在 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。
最佳答案
问题在于 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
循环。
关于java - 我的 Havel-Hakimi 算法代码有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56820958/