leetcode问题

Question

老师这个课程能问leetcode上的问题吗?如果可以我想问一下最长回文子串的马拉车算法的思路,网上搜来的解释不太理解

Answer 1

liuyubobobo 2019-07-26 03:23:54

看见你在我的线数课也问这个问题了。看来对这个问题耿耿于怀啊：）

首先，这个课程可以问leetcode的所有问题。

其次，关于马拉车算法的思路（我一搜才知道，Manacher被中文翻译成了这个样子。。。），确实比较复杂。复杂的地方在于，定义的变量比较多。必须很清晰地理解每一个变量的语义。

如果完整解释马拉车算法，我可能要写一篇很长的文章。主要这本身也不是图论算法。我的建议是这样的，我们根据一个（或者多个解析），有针对性的看一下。我在网上搜了一下，我觉得这个解析还不错：

https://www.zhihu.com/question/37289584

我的建议是，你针对这个解析，看哪里没有理解，进一步提问。

注意，你的问题千万不要是不懂18行，19行，20行，什么意思。这个解析里，在尝试很具体的解释18，19，20行在做什么。你必须深入的把你的问题问的更细致，这个解析里，具体哪部分，你没有想明白，在哪里卡住了。

我们试试看，用这种方式，能不能让你理解这个算法？：）

注意，整个算法的核心，其实是上面链接里的第18行。如果对第18行有疑问，我觉得这个文章讲的挺好：https://www.cnblogs.com/grandyang/p/4475985.html

另外，上面的文章给出了完整的实现。也强烈建议你针对一个测试用例，实际单步跟踪，看一下在算法的每一步，各个变量是如何变化的，为什么会这么变化，最后是怎样获得最终结果的。

也可以参考我的实现：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0005-Longest-Palindromic-Substring/cpp-0005/main8.cpp 似乎比他的实现更安全。

加油！：）