题目：一个链表中包含环，请找出该链表的环的入口结点。
算法主要分为两步走。
第一步需要判断链表是否有环。首先设置两个指针同时指向头结点，然后一个指针走一步，另一个指针走两步，如果他们能够相遇，那么说明该链表有环，并记录他们相遇的节点(相遇节点一定在环内),如果不存在这样的相遇节点，那么此链表无环。
第二步，需要找到链表中环的入口节点。首先需要根据相遇节点计算出此环中包含的节点个数 k，然后需要设置两个指针，其中一个指针先走 k 步，然后另一个指针再指向头结点；之后两个指针同时移动，直到他们相遇即都到达了环的入口节点，此时返回此节点。(后面寻找入口节点其实有点类似前一篇寻找链表中第 k 个节点的算法，仔细体会体会~)
代码只线性遍历链表，因此时间复杂度为 O(n)，空间复杂度O(1)。
<<剑指offer2>>
正则表达式匹配也是编程中很常见的技术，那么给定正则表达式匹配的规则，那么对于模式串，如何判断字符串是否与之匹配呢？这就涉及到了字符串的编程能力。字符串的应用也是面试中非常重要的一类。
题目：请实现一个函数用来匹配包括 ‘.’ 和 ‘*‘ 的正则表达式。模式中的字符 ‘.’ 表示任意一个字符，而 ‘‘ 表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 “aaa” 与模式 “a.a” 和 “ab\ac*a” 匹配，但是与 “aa.a” 和 “ab*a” 均不匹配。
很明显需要利用递归。
首先考虑下递归的出口。如果字符串与模式串能够匹配，那么此时，他们都匹配到了字符终止标记’\0’；否则，如果字符串还未到达’\0’,而模式串已经到达了 ‘\0’,那么说明此时匹配不成功。
接下来我们先考虑含 * 的情况，这里要注意含 * 的情况有包含一些 . 的情况，所以我们需要先考虑 * 的情况。
那么如果模式串的下一个字符是 * ，首先分为两种情况。
情况一：如果字符串和模式串的第一个字符相等或者模式串中第一个字符含 ‘.’而字符串未到达末位，那么又可以分为三种子情况：
情况二：字符串第一个字符和模式串第一个字符都匹配，或者模式串中含 . 并且字符串第一个字符不是’\0’，那么字符串和模式串继续前进一位匹配。
算法需要对每个字符都进行匹配，因此时间复杂度为 O(n)，另外由于采用递归，需要消耗 O(n)的递归工作栈，所以空间复杂度为 O(n)。
<<剑指offer2>>
在经过前面漫长的 SVM 学习之后，是时候学习怎么实现 SVM 了。其实，SVM 常常表现得很好并且有着高效的训练算法，这使得 SVM 曾经非常盛行。只是近些年来，由于深度学习起势，SVM 才不再那么盛行，但它依旧是很好用的分类算法。所以探究 SVM 的原理及思想显得非常有必要，那么现在我们就谈谈 SMO 算法。
首先，在前面的 SVM 学习中，我们有如下对偶问题:
并且需要满足KKT条件:
那么，由于一个训练样本 \(\left(x_{i},y_{i}\right)\) 对应一个 \(\alpha_{i}\)，因此我们只需要找到这样一组 \(\alpha_{i}\) 满足上述条件，这就是该对偶问题的最优解。有了这组 \(\alpha_{i}\) ,\(w\)、b 以及分类函数 \(f\left(x\right)\)就可以顺其自然地得到求解。
上述对偶问题是个凸二次规划问题，它具有全局最优解。一般可以使用现有的 QP 工具来进行求解。但是，当训练容量非常大的时候，训练算法反而耗时且低效。因此，有必要寻找更优的求解算法来代替实现。虽然出现了很多优化算法，但比较著名的是一个叫做 John C. Platt 的研究者提出的序列最小化算法 (Sequential Minimal Optimization，简称 SMO)。而它的思想是：将大优化的问题分解成多个小优化的问题。这些小问题往往比较容易求解，然后对他们进行顺序求解。这样之后得到的结果与将他们作为整体来求解的结果完全一致并且最重要的是 SMO 的求解时间更短了。
在介绍 SMO 之前，先介绍下坐标梯度下降算法，这也是 SMO 中利用到的简单的算法思想。
坐标下降是一种非梯度优化算法(坐标下降用于优化最小值，而坐标上升用于优化最大值，可通过加负号相互转换)。因为算法在每次迭代中，只会从当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值，并在迭代的过程中不断变化优化的坐标方向，直至函数得到收敛。
例如，我们要寻找函数 \(f\left( x,y\right) =5x^{2}-6xy+5y^{2}\) 的最小值。那么坐标优化的迭代过程如下图所示:
我们从某个起始点开始寻找，然后沿着一个方向往等高线上数值小的高度前进(类似下山)，在前进的时候，可以改变方向，例如此处可以往上或往右走，直至不断走向中心点，也就是收敛到最优解。
SMO 算法和坐标梯度下降思想差不多，只是 SMO 一次迭代优化的是两个变量 \(\alpha_{i}\)、\(\alpha_{j}\)。所以它的思想就是将带有多个优化变量的二次规划大问题分解为多个只含两个优化变量的二次规划小问题，这样既节省了时间成本也降低了内存消耗。
那么为什么需要一次优化两个变量呢？这是因为在 SVM 中存在着 \(\sum ^{m}_{i=1}\alpha _{i}y_{i}=c\) 约束，这是一个线性组合关系。而 SMO 在优化前会先固定暂时不进行优化的变量，那么如果仅优化一个变量，那么这个变量就会被其他已固定的参数表示出来，则它就不再是变量，因此，需要再找一个变量。即 SMO 算法先要确定一对 \(\alpha_{i},\alpha_{j}\)，其他的变量则先固定。
那么固定参数之后，就可以得到 \(\alpha_{i}\) 和 \(\alpha_{j}\) 的等式关系了。即：
那么我们就可以消去上述对偶问题中的 \(\alpha_{i}\)了，然后就得到了仅关于 \(\alpha_{j}\) 的单变量二次规划问题，然后利用费马引理进行求解即可。解出 \(\alpha_{j}\) 之后，\(\alpha_{i}\) 便可由等式轻易推出，这样就是一次迭代过程。迭代一次仅调整两个拉格朗日乘子。那么这样看来，SMO 之所以高效的原因就在于它是对单变量进行优化，可想而知单变量的收敛速度是比较快的。
总之，一次迭代的三个步骤是:
并且用 \(k_{i,j}\) 代替 \(k\left( x_{i},x_{j}\right)\) 表示。
然后，假设我们选中的待优化变量为 \(\alpha_{1}\) ，\(\alpha_{2}\) 。那么 \(\alpha_{3}\),\(\alpha_{4}\)，…，\(\alpha_{m}\) 则被固定，当做常数处理。那么将 SVM 的优化问题展开后得到：
其中将与 \(\alpha_{1}\)、\(\alpha_{2}\) 无关的 \(C_{1}\) 和 \(\sum ^{m}_{i=3}\sum ^{m}_{j=3}\alpha _{i}y_{i}\alpha _{j}y_{j}k_{i,j}\) 合并为常数项 C。
又已知 \(\alpha_{1} y_{1}+\alpha_{2}y_{2}=\xi\) ,\(y_{i}y_{i}=1\)，然后等式两边同时乘上 \(y_{1}\) 得到:
另外，记 \(v_{1}=\sum ^{m}_{i=3}\alpha _{i}y_{i}k_{i,1}\)，\(v_{2}=\sum ^{m}_{i=3}\alpha _{i}y_{i}k_{i,2}\)，最后将所有式子带入 \(w\left( \alpha_{1},\alpha _{2}\right)\) 得到：
接下来利用费马引理求极值，令 \(w\) 对 \(\alpha_{2}\) 的导数为零，得:
然后，现在我们要将 \(\xi\) 消去。
已知 SVM 分类函数公式:\(f\left( x_{i}\right) =\sum ^{m}_{i=1}\alpha _{i}y_{i}k_{i,i}+b\)，那么:
得到： \(v_{1}-v_{2}=f\left( x_{1}\right) -f\left( x_{2}\right) -k_{1,1}\xi+k_{1,2}\xi +\left( k_{1,1}+k_{2,2}-2k_{1,2}\right) y_{2}\alpha _{2}\)
现在，我们需要区别下迭代前和迭代之后的变量。其实我们固定的 m-2 个拉格朗日乘子都是上一次迭代的值，所以 \(v_{1}\) 和 \(v_{2}\) 所表示的式子都是前一次迭代的量，那么，由他们推导出来的 \(\alpha_{1}\) 和 \(\alpha_{2}\) 当然也是前一次迭代的量。
那么现在我们以 old 和 new 上角标分别区别前一次迭代和当前迭代的优化量，那么区分后式子改为：
接下来，合并两个式子，再得：
然后，我们记 \(E_{i}\) 为 SVM 的预测值和实际值的误差: \(E_{i}=f\left( x_{i}\right) -y_{i}\)，并且令 \(\eta=k_{1,1}+k_{2,2}-2k_{1,2}\)，所以最终的一阶求导公式为：
那么就可以解出:
上面解出的 \(\alpha_{1}\) 和 \(\alpha_{2}\) 并未考虑约束条件。那么，现在我们需要将约束条件加上，然后对所求出的最优解进行范围的修剪以得到最终满足约束条件的最优解。
即:
由于约束条件 \(0\leq \alpha _{1}\leq C\) 、 \(0\leq \alpha _{2}\leq C\) 以及 \(\alpha_{1} y_{1}+\alpha_{2}y_{2}=k, \quad k为常数\) 的存在，所以我们需要给 \(\alpha _{1}\) 和 \(\alpha _{2}\) 找到区间 \(\left[L,H\right]\)。由于只有两个变量，因此约束可以用二维空间中的图形来表示，如下图所示(方形约束)。
那么对于约束 \(\alpha_{1} y_{1}+\alpha_{2}y_{2}=k\)
根据左图：当 \(y_{1}\neq y_{2}\) 时，此约束简化为：\(\alpha_{1}-\alpha_{2}=k\)，那么根据 k 的正负可以得到上下界为：
根据右图：当 \(y_{1}= y_{2}\) 时，此约束简化为：\(\alpha_{1}+\alpha_{2}=k\)，上下界表示为：
那么，有了上下界之后，如果优化之后的 \(\alpha_{1}\) 和 \(\alpha_{2}\)跑出了边界，那么我们就需要纠正它，所以有：
得到了 \(\alpha ^{new}_{2}\)，再根据 \(\alpha^{new}_{1} y_{1}+\alpha^{new}_{2}y_{2}=\alpha^{old}_{1} y_{1}+\alpha^{old}_{2}y_{2}\) ，然后两边同乘以 \(y_{1}\) 可解出 \(\alpha ^{new}_{1}\)，即:
这样，我们就得到了两个优化的拉格朗日乘子 \(\alpha^{new}_{1}\) 和 \(\alpha^{new}_{2}\)
在每一次迭代中，优化 \(\alpha^{new}_{1}\) 和 \(\alpha^{new}_{2}\) 之后，就要更新阈值 \(b\)。那么为了使得被优化的样本都满足 KKT 条件，此时需要分为样本在边界上和样本不在边界上两种情况进行讨论。
假如给定一个字符串，如何判断它是数值？即该字符串对应的数必须是整数或者小数。当然，还要考虑科学计数法的加入。所以我们需要知道字符串遵循的模式，即 A[.[B]][e|EC] 或者 .B[e|EC]。其中 A 为数值的整数部分，B 紧跟着小数点为数值的小数部分，C表示指数部分。
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
在前言提到的字符串是数值时,它所遵循的模式中，A 和 C 是含’+-‘以及’0-9’的字符串，B是仅含 ‘0-9’的字符串。
那么我们就需要根据 ‘.’和 ‘e|E’ 的位置判别接下来的字符串所满足的条件。具体分析见代码。
另外，我们还可以根据字符串遵循的模式利用正则匹配表示式来匹配。正则表达式为 [+-]\?[0-9](.[0-9])\?([eE][+-]?[0-9]*)\?
需要扫描一遍字符串时间复杂度为 O(n)，空间复杂度为 O(1)。
<<剑指offer2>>
在单链表中删除一个节点，一般都是从链表的头节点开始顺序遍历，然后在链表中删除。但是这样的时候复杂度为 O(n)，那么能不能在 O(1) 时间内删除元素呢？
给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间删除该节点。链表结点与函数的定义如下：
struct ListNode{
int val;
ListNode* next;
}
void DeleteNode(ListNode** head, ListNode* pToBeDeleted);
首先，我们应该先考虑删除位置的情况。所以需要讨论删除位置在头节点、链表中以及链表尾部。然后，要实现在 O(1) 中删除节点，我们可以将待删除节点的下一节点的信息赋值给前一节点，那么现在只需要删除原待删除节点的下一节点即可，因为已经知道了新的待删除节点的前一节点的指针了，所以操作便只需耗时 O(1)。
时间复杂度为 O(1)
题目：在一个排序的链表中，如何删除重复的节点。(无头节点)
首先，为了更方便地操作链表，我们需要给链表加一个头结点。然后，我们需要两个指针 p 和 pre，分别表示指向当前节点和指向当前节点的前一节点。接着，需要判断当前节点和其下一节点是否存在重复节点，如果不存在则指针依次前移，继续遍历；否则从重复的第一个节点开始，循环跳过重复的节点并删除重复节点，最后 p 指针指向了第一个不重复的节点，然后只需把 pre 指针指向的节点和这个第一个不重复的节点连接即可,之后继续遍历。
需要遍历整个链表，所以时间复杂度为 O(n)。
<<剑指offer2>>