1

我正在阅读这篇关于常见算法问题的LeetCode 文章，“最长公共前缀”。他们展示了几种不同的方法，但我的问题仅与“分而治之”有关。它的示例显示了您经常在各处的书籍和博客中看到的典型递归自上而下方法。

看着这个让我想到我应该能够“迭代地”和“自下而上”地做到这一点。类似于自下而上的合并排序方法。所以这就是我结束的地方：

// type "Stack", function "prefix", and "min" implementations are not shown for brevity.
// Just assume they're defined somewhere and they work correctly.
//
// "prefix" function accepts two strings and returns a string
// Examples:
// prefix("abcd", "ab") returns "ab"
// prefix("abcd", "efgh") returns ""
// ... you get the idea.
//
// "min" does exactly what you'd expect. Its arguments are both type int.
func lcpDAndC(a []string) string {
        n := len(a)

        if n == 0 {
                return ""
        }

        var (
                stack Stack
                p, q  string
        )
        for lo := 0; lo < n; lo += 2 {
                hi := min(lo+1, n-1)
                stack = stack.Push(prefix(a[lo], a[hi])
        }

        for stack.Len() > 1 {
                p, q = stack.Pop2()
                stack.Push(prefix(p, q))
        }

        return stack.Pop1()
}

所以我的问题是：这仍然被认为是“自下而上”和“分而治之”吗？我认为可以安全地假设立即从叶子开始（自下而上的部分）只需一次处理两个元素，因为它通过数组一次（“划分”......但也是“征服？ ”）。这里的堆栈当然与递归方法中的调用堆栈发挥相同的作用。虽然，队列也可以，这是我认为我已经离开这里的另一个原因。

如果这不是“自下而上”和“分而治之”的正确应用，这是否至少应用了我不知道的其他一些理论？

4

1 回答 1

1

文章中使用的递归是Top Down因为它们将较大的案例分解为较小的案例，然后组合较小案例的结果。

在递归中，函数调用相互叠加到函数调用堆栈中。他们要么被弹出

(1) Once the base case is reached

或者

(2) Results of function calls above them in the stack has been computed and it's their turn now.

您的代码不执行Bottom Up递归，也不是D&C，

考虑这种情况：-

["care","car","cat","cater","click","clang","core","coral"]

最初堆叠：-

cor
cl
cat
car

While 循环迭代 #1：

c
cat
car

While 循环迭代 #2：

c
car

While 循环迭代 #3：

c

您的 while 循环以串行方式组合元素，并且不使用D&C. 如果您lo+=2在 for 循环中更改为，lo+=1那么您的代码与Approach 1: Horizontal scanning.

但是，使用队列会使代码成为Bottom-Up递归。请注意，每次弹出两个元素时，它们如何代表两个相互排斥的半部分，这些部分也会在Top Down方法的递归树中找到。考虑这种情况：-

["care","car","cat","cater","click","clang","core","coral"]

最初排队：-

cor
cl
cat
car

While 循环迭代 #1：

ca
cor
cl

While 循环迭代 #2：

c
ca

While 循环迭代 #3：

c
于 2020-04-27T05:59:04.687 回答