题目(树的子结构)

输入两棵二叉树 A 和 B ，判断 B 是不是 A 的子结构。二叉树的定义如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
        val(x), left(nullptr), right(nullptr) {
    }
};  

算法思路

首先应注意所输入二叉树的特殊值情况，如空指针。
算法主要分为两步。
第一步，首先应该从二叉树 A 的根节点开始遍历，寻找和二叉树 B 根节点相同的那个节点，设为 节点 C。我们对二叉树 A 遍历的时候可以利用二叉树的递归特性,对其左右子树执行相同操作。
第二步，需要判断树 A 中以 C 为根节点的子树的结构是否和树 B 的结构一样，那么仍然可以利用递归的特性。如果他们的根节点值相同，那么对树 A 中 C 的左子树和树 B 中 C 的左子树递归判断结构的一致性，然后对两棵树的 C 的右子树也递归，只有他们的子结构同时相同，那么二叉树 A 中才存在 二叉树 B 的结构，否则不存在。

算法实现

复杂度分析

二叉树 A 利用层序遍历的递归实现，每个结点只需遍历一次，故时间复杂度为 O(n)。而使用了递归，最差情况下递归调用的深度为 O(n)，所以空间复杂度为 O(n)。本题中还需要遍历二叉树 B，因此若设其节点数为 m 个，那么最终的时间复杂度为 O(n+m)，空间复杂度为 O(n+m)。

参考

<<剑指offer2>>

前言

经过前面三篇漫长的 SVM 介绍以及 SMO 算法的原理介绍和公式推导，终于到了 SMO 的算法实现以及最终的 SVM 分类实现了。那么现在就先看看 SMO 的 python 实现。

SMO python 实现

代码中的 \(\alpha_{i}\)，\(\alpha_{j}\) 对应了前一篇中的 \(\alpha_{1}\) 和 \(\alpha_{2}\)，并且代码中的计算方式都是套用前一篇中推导出来的公式，请仔细体会。另外，以下我把选出来的 \(\alpha_{i}\)，\(\alpha_{j}\) 分别成为第一个 alpha 值和第二个 alpha 值。

首先定义一个核转换函数用于计算训练集矩阵(X)与任意给定样本矩阵间的核转换结果。

下面定义一个 SVMStruct 类来封装一些属性和方法，以便可以快速构建一个 SVM 模型。

接下来定义一些 SVMStruct 类下的辅助方法。

接下来，函数 innerL为 SMO 主程序内层循环的代码。

外层循环的代码：

计算权重 \(w\) 的函数：

分类函数的代码：

最后是 plot 出样本点，和划分线：

那么最后可视化的结果为：

1. 本例中所用的数据集必须使用线性核才使得样本可分。
2. 本文代码见个人github repository MLCodeOnTheBlog

参考

[1] <<机器学习实战-中文版>>
[2] Sequential Minimal Optimization:
A Fast Algorithm for Training Support Vector Machines by John C. Platt
[3] 机器学习算法与Python实践之（四）支持向量机（SVM）实现 by zouxy
[4] 机器学习算法实践-SVM中的SMO算法 by PytLab酱

题目(合并两个排序的链表)

输入两个递增排序的链表，合并这两个链表并使得新链表中的节点仍然是递增排序的。

算法思路

首先应考虑代码鲁棒性，如果输入的链表 1 为空，那么链表 2 就是合并链表；如果输入的链表 2 为空，那么链表 1 就是合并的链表。

非递归版本

首先应该先确定合并链表的头结点,由指针 mergedHead 表示。然后定义合并链表的工作指针 p(初始指向头结点) 来完成合并链表的连接工作。

那么有了合并链表的工作指针 p，我们只要确定连接到 p 的下一个节点就行。因此只需要比较链表 1 和链表 2 的工作指针所指向的节点大小即可。那么重复以上操作，循环条件为链表 1 和链表 2 不空。

最后一步还需要检查是否还有剩余节点未完全连接完，因此需要对链表 1 或 链表 2 判空，若有剩余节点，择全部连接到工作指针 p 的后面即可，最后的最后将合并链表的尾节点指针置空。

递归版本

递归版本只要一个表示合并链表的头指针，然后依次递归比较两个链表中对应位置上节点的大小，然后递归连接到合并链表的指针上去即可。这里不再需要一个合并链表的工作指针，合并链表的指针自己就可以完成连接工作，它的下一个节点都是递归返回的。需要注意的是，递归版本没有移动这个指针，非递归版本中需要移动这个指针，因此设置了一个工作指针 p 代替合并链表指针来移动，原因在于我们最终返回的是合并链表的头结点指针，所以不能移动它，而所以就利用工作指针来移动并完成连接操作。

算法实现

非递归版本

非递归版本

复杂度分析

假设链表 1 有 m 个节点，链表 2 有 n 个节点。对非递归版本，算法需要遍历两个链表的节点，因此时间复杂度为 O(m+n)，算法仅改变指针指向，没有消耗额外空间，空间复杂度为 O(1)；对递归版本，时间复杂度相同，但由于使用递归，需要消耗递归工作栈，因此空间复杂度为 O(min(m,n))。

参考

<<剑指offer2>>

题目(反转链表)

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

算法思路

要想反转链表，我们自然会想到改变节点指针的指向为指向它之前的节点，因此，我们需要一个能够记录前驱节点的指针。但是这样一来会导致和它原先连接的链表断开，为了能够继续改变下一节点的指针指向，我们需要用后继指针记录当前节点的下一节点，以便当前节点指针变向后，它可以根据后继指针顺利找到到下一个节点，然后再执行指针变向，以此进行下去，直到当前节点的下一节点为空时，即到达链表表尾，返回当前节点即为反转后链表的头结点。

算法实现

复杂度分析

代码只线性遍历链表，因此时间复杂度为 O(n)，空间复杂度 O(1)。

参考

<<剑指offer2>>

前言

我们在写代码的时候要注意鲁棒性。那么所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。提高代码的鲁棒性的有效途径是进行防御性编程。防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。

那么在面试时，最简单也是最实用的防御性编程就是在函数入口添加代码以验证用户输入是否符合要求。比如我们常用的输入值的边界值检测和特殊值判断。另外，我们在面对题目的时候，要多问自己几个 “如果不…那么…” 这样的话，比如接下来的这题 “链表中倒数第 k 个节点”，就隐含着的一个条件，如果链表中的节点个数大于 k 呢。那么我们在编写代码的时候就必须把这种情况处理好。

题目(链表中倒数第 k 个节点)

题目:输入一个链表，输出该链表中倒数第 k 个结点。题目从 1 开始计数，头结点为1，以此类推…

算法思路

比较直观的思路就是遍历一遍链表，得到链表的节点个数 n，那么倒数第 k 个节点的位置就在 n-k+1 的位置上，因此需要再次遍历链表。

那么能不能只遍历链表一次呢？可以的。我们可以设置两个指针p1，p2,初始 p1 指向头结点，p2为空。然后，p1 先移动到正向第 k 个节点的位置，然后更新 p2 的指针指向头结点。然后就这样两个指针同时前进，直到前面的 p1 指针指向链表尾节点，此时 p2 所指的节点即为所求。有点类似有个尺子在衡量，然后水平移动尺子，最后尺子的初始位置就是所求。

算法实现

复杂度分析

两个算法思路的时间复杂度都为 O(n)，因为都是线性遍历。但是由于后者只需遍历一遍，因而后者的时间效率更优；空间复杂度为 O(n)

参考

<<剑指offer2>>