谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。
具体算法细节请参考：
字符串匹配的KMP算法: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html从头到尾彻底理解KMP: https://blog.csdn.net/v_july_v/article/details/7041827如何更好的理解和掌握 KMP 算法?: https://www.zhihu.com/question/21923021KMP 算法详细解析: https://blog.sengxian.com/algorithms/kmp图解 KMP 算法: http://blog.jobbole.com/76611/汪都能听懂的KMP字符串匹配算法【双语字幕】: https://www.bilibili.com/video/av3246487/?from=search&seid=17173603269940723925KMP字符串匹配算法1: https://www.bilibili.com/video/av11866460?from=search&seid=12730654434238709250除此之外，再来了解一下BM算法！
BM算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。 《字符串匹配的KMP算法》:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
2. 替换空格剑指offer：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这里我提供了两种方法：①常规方法；②利用 API 解决。
//https://www.weiweiblog.cn/replacespace/public class Solution { /** * 第一种方法：常规方法。利用String.charAt(i)以及String.valueOf(char).equals(" " * )遍历字符串并判断元素是否为空格。是则替换为"%20",否则不替换 */ public static String replaceSpace(StringBuffer str) { int length = str.length(); // System.out.println("length=" + length); StringBuffer result = new StringBuffer(); for (int i = 0; i 5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
该题在 leetcode 上有详细解答，具体可参考 Leetcode.
问题分析我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。
Solution两次遍历法
首先我们将添加一个 哑结点 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。我们把第 (L - n)个结点的 next 指针重新