在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？
虽然我不是算法顶尖选手，但是我的算法水平也足够令我在名企的面试中取得一些优势。 我的建议是： 1.红黑树的插入和删除不算难以理解的算法，但比较繁琐。首先需要熟悉搜索树的“指针旋转”操作，然后插入结点需要分3种情况讨论，删除结点需要分4种情况讨论。要熟悉所有其中的步骤的话，会造成比较大的负担。我没有听说有人遇到考核红黑树的实现细节的面试官。虽然不意味着一定不会遇到钟情于红黑树的面试官，但是我不会花费有限的精力去搞定它。 2.对于红黑树，你可以只了解：红黑树是一种大致平衡的二叉搜索树（叶子到根的最大长度不大于其最小长度之两倍，而严格的平衡二叉树的定义是：任意节点的左右子树的高度差的绝对值不大于1），单次的查找、插入、删除的复杂度都是lg(n)，这些操作的复杂度都不会恶化；红黑树的定义；红黑树结点数与树高的约束：lg(n+1) >= h/2，及其证明；STL中的map和set是用红黑树实现的，以及它们的用法。 3.KMP算法是比较难以理解的算法，但是不繁琐，而是很精妙，值得理解，有助于培养算法思维。独立理解不容易，你可以尝试看看我附赠的KMP算法解释。虽然在校招中不太可能有面试官要求手写KMP算法，但是有可能有面试官会让你解释KMP的原理。 4.少年，想开一点，临时抱佛脚不可能面面俱到，押题大多数情况做的是无用功，随缘就是了。为了应试做准备的话，应该优先练习链表类题目和二叉树类题目，这类题目比较常出现在面试中。 附赠：KMP算法理解 面试官： 现在请你把我当做完全不了解KMP算法的人，向我解释一下KMP算法的原理。 面霸： KMP算法俗称“看(K)毛(M)片(P)算法”，用于快速文本匹配。试想你有两条字符串src和pat，需要判断pat是否在src中出现，如果出现就给出出现的具体位置。假设src的长度为N，pat的长度为M，首先我们来讨论一下一个平凡的蛮力解。 如果你想判断两个字符串是否相等，你会写一个这样的循环（在纸上写下）： for(int i = 0; i < M; i++) if(src[ i ] != dst[ i ]) return false;return true; 这里你最多比较了M次。回到原来的问题，有了这个子函数，你只要依次判断（一边在纸上写符号）src[i, i + M - 1], i = 0, 1, 2, ... 与dst是否相等就行了。复杂度是N乘以M。 那么如何优化呢？我换一种说法，为什么能够优化呢？因为你做了重复的事情。我们换一种写法，就能更直观地发现重复在哪里。  你看这个变量i（一边用手指），它每次比较完一轮，就退回到原来的位置的下一个位置重新开始匹配。难道我刚刚做了那么多次比较，得到的信息就白白扔掉了吗？KMP三人找到了一种简单的利用这信息的方法，只要花点力气对模式串pat做一下预处理，就能使这匹配程序里的循环变量i只进不退，从而达到N+M的复杂度。 我们把这个匹配过程想象成，模式串依附着源串向后移动。你看（一边画图），i在这个位置，j在这个位置，走了这么一段路才发生失配了，意味着这两条(src[i - j, i - 1]和pat[0, j-1])是公共子串，也就是说此时src的这条子串的信息完全包含于pat的前缀子串之中，原则上我如果对pat做了充分的了解，就可以保持i不变，而单单令pat往后移动。假如我可以令pat移动一步而i不变，那说明这两大段是相等的；假如这两大段不相等，那么我至少可以令pat移动两步。观察发现，我应该令pat移动多少步，取决于pat[0, j - 1]的最长的相等{前缀、后缀}的长度。 KMP的精髓就在于，用了一个线性的算法，得到了每次在pat[ j ]发生失配时，应该让pat往后移动多少步，这个值对应于pat[0, j - 1]的最长相等{前缀、后缀}的长度。这些值所存的数组叫做next数组。 我需要写出计算next数组的函数，才能具体解释这个算法。 面试官： 可以了，说到最长相等前后缀这点就足够了。接下来请你手写一个归并排序的代码…… 附一套高效的KMP代码： 这个函数的过程可以看作将pat和自身做匹配的过程。第13行至第16行的判断比较令人费解，其实那是一个加速优化。语句j = next[ j ]也可以看作用动态规划做的优化。get_next可以写成下面的非优化形式，并且它的复杂度也是O(M)：  然后是利用next数组进行匹配的代码：  关于复杂度：无论是get_next还是indice_kmp，在每个while循环单体中，存在一个严格增量：i + (模式串往后移动的步数)，因此该算法的复杂度是O(N + M). 最后说一句：看毛片有害身心健康。 有首歌是这么唱的： You VOTE ME UP~~~~ so I can stand on moutains ~~~~