我需要在名为 Node 的类中编写一个名为 findMax 的 Java 方法,该类有两个实例变量:int value 和 Node next。该方法不带任何参数,并且必须返回链表的最大值。在程序的上下文中,该方法将始终由链表的第一个节点调用(递归调用除外)。当我无意中找到一个可行的解决方案时,我正在努力完成该方法:
public int findMax(){
int max = value;
if(next == null){
return max;
}
else{
if(max <= next.findMax()){
max = next.value;
}
else return max;
}
return next.findMax();
}
此方法正确返回了我测试的每个链表的最大值。然而,由于我通过尝试随机排列代码找到了这个解决方案,所以我并不真正觉得我理解这里发生了什么。谁能向我解释一下这是如何/为什么有效的?另外,如果有更高效的解决方案,如何实现?
最佳答案
你可以想象一个链接列表看起来像这样:
val1 -> val2 -> val3 -> null
递归的工作原理是最终可以处理传递给函数的输入,而无需进一步递归。在您的情况下,如果next
指针为null
,则可以处理node.findMax()。也就是说,大小为 1 的链表的最大值只是值(递归的基本情况),任何其他链表的最大值是该节点的值的最大值或剩余元素的最大值。
ie) 对于值为 val3 的 Node n3
,n3.findMax()
仅返回该值
对于任何其他节点n
,n.findMax()
返回节点值或n.next.findMax()
的最大值
在开始的示例中,它的样子是:
n1.findMax()
= Max(n1.value, n2.findMax())
= Max(val1, Max(n2.value, n3.findMax())
= Max(val1, Max(val2, n3.value)) // Since n3.next == null
= Max(val1, Max(val2, val3))
这只是整个列表中的最大值
编辑:根据上面的讨论,虽然你所说的可能有效,但有一种更简单的编写程序的方法:
int findMax() {
if (this.next == null) {
return this.value;
} else {
return Math.max(this.value, this.next.findMax());
}
}
编辑 2:分析代码为何有效(以及为什么不好):
public int findMax(){
// This variable doesn't serve much purpose
int max = value;
if(next == null){
return max;
}
else{
// This if condition simply prevents us from following
// the else block below but the stuff inside does nothing.
if(max <= next.findMax()){
// max is never used again if you are here.
max = next.value;
}
else return max;
}
// We now compute findMax() again, leading to serious inefficiency
return next.findMax();
}
为什么这样效率低下?因为节点上对 findMax()
的每次调用都会对下一个节点上的 findMax()
进行两次后续调用。每个调用都会生成另外两个调用,依此类推。
解决这个问题的方法是存储 next.findMax()
的结果,如下所示:
public int findMax() {
if (next == null) {
return value;
}
else {
int maxOfRest = next.findMax();
if(value <= maxOfRest) {
return maxOfRest;
}
else return value;
}
}
关于java - 递归查找链表的最大值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43105035/