本文转载自Poll的笔记，有关红黑树的内容还可参考skywang12345，有关二叉树的面试算法总结可以参考面试算法之二叉树操作集锦，C++面试笔记–树

数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。本文中对数据结构中常见的几种树的概念和用途进行了汇总，不求严格精准，但求简单易懂。

二叉树

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。

二叉树的定义：

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有 $2^{i-1}$ 个结点；深度为k的二叉树至多有 $2^{k-1}$ 个结点；对任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。

二叉树的示例：

遗传算法是一种启发式搜索算法，其基本原理是模拟自然界物竞天择的演化法则。（说的这么高大上，其实就是比较高级的穷举法，不过穷举的时候给出穷举方向而已）。遗传算法具体步骤见下图（来自百度百科）：

名词介绍

染色体，个体，基因

这3个概念基本等价，遗传算法中每个个体都含有一个染色体\基因，遗传算法将在种群中选择优秀个体，将他们的染色体交叉、变异后产生新的下一代种群。

一下说了这么多新概念，你可能会有些晕，说到底，染色体就相当于自变量x，而我们的优化目标就相当于因变量y，他们之间有函数关系y=f(x)，这个函数f(x)就是评价一个染色体好坏、能否适应环境的适应度函数。

前人总结揭开正则表达式的神秘面纱，正则表达式30分钟入门教程，在线测试工具

某些字符

常用的元字符

如果想匹配. or ^ or $，需要在前面加上转义字符 \ ，如\. 。

本文转载自Poll的笔记

查找算法简介

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

1. 静态查找和动态查找。（注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。）
2. 无序查找和有序查找。
   • 无序查找：被查找数列有序无序均可；
   • 有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

• 对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
• Pi：查找表中第i个数据元素的概率。
• Ci：找到第i个数据元素时已经比较过的次数。

本文转载自计算机的艺术

链表简介

链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。本文对链表相关的面试题做了较为全面的整理，希望能对找工作的同学有所帮助。

链表结点声明如下：

1
2
3
4
5
6

struct ListNode
{
    int m_nKey;
    ListNode * m_pNext;
};

支持向量机基本思想

在n维空间中，可以使用n-1维超平面（可用线性方程 $\mathbf{w^Tx}+b=0$ 来描述）来分类（将n维空间分为2部分），下图以二维空间为例：

图中带圆圈标记的政府样本为距离超平面最近的样本点，也称支持向量。用支持向量机分类时有以下约束条件：应尽量去找正负样本正中心的超平面，这样对样本扰动容忍性好。

本文转载自长安CAE

动力学问题

在讨论隐式与显式动力学之前，先讨论一下动力学问题和静力学问题。在求解静力学问题时没有时间的概念，即使在载荷步控制力有Time这个选项，但是这个Time的含义更多的是载荷步。Time前后的求解过程相互没有影响。

动力学问题的特点是施加到结构上的外载荷的大小和方向可能随着时间的变化而发生变化，使结构产生速度和加速度。在用有限元求解静力学问题时主要是求矩阵方程组的问题，如下所示，只需要考虑结构的刚度矩阵。

本文使用python代码实现了常用的排序算法，并分析复杂度。有关动图以及算法详细介绍可以参考blog

插入排序法

• 基本介绍

  插入排序法依次选择元素，当选择第i位元素时，[0,i]为已排序序列，比较第i+1位元素大小并将其插入[0,i+1]序列中合适的位置。

• 算法复杂度

  插入排序法分为比较与插入（交换）2个过程。

  1. 最好情况：$O(n)$
  2. 最坏情况：$O(N^2)$
  3. 平均情况：$O(N^2)$
  4. 稳定

     1 2 3 4 5 6 7 8 9 10 11 12 13 14

     def Insert(l): for i in range(1,len(l)): num=l[i] j=i while(j>=0): if(l[j]<l[j-1]): l[j],l[j-1]=l[j-1],l[j] j-=1 else: break l=[0,20,3,5,4,65] Insert(l) print(l)

本文为阅读西瓜书的总结笔记。部分参考懒死骆驼

何为集成学习

集成学习通过构建并结合多个学习器来完成学习任务。先训练一组个体学习器，再通过策略将其结合起来。

集成学习的关键

如何使多个学习器的结合比单一学习器性能优越？关键在于学习器的多样性与准确性。

即个体学习器需要有一定的准确性，不能太坏，同时又需要有多样性，个体之间要有差异。但多样性与准确性往往相互冲突。

如何产生并结合好而不同的个体学习器是集成学习的核心。

集成学习的分类

目前集成学习主要可分为2大类，即：

1. boosting：弱学习器之间存在强依赖关系，必须串行生成的序列化方法。
2. bagging：弱学习器之间不存在强依赖关系，可以并行生成。

bagging和boosting分别是关注降低方差和降低偏差的两个代表，GDBT的每棵树生成都要比上棵树偏差小。

在OJ、牛客网上，经常有在线编程题需要读取输入样例,另外可能还需要一定的格式化输出知识，之前一直不太会这方面，此处来汇总一下。

python版

python的比较简单，可以直接通过input()语句读取一整行内容，并返回str类型。具体使用如下：

1
2
3
4
5
6
7
8
9
10
11
12

>>> a = input("input:")
input:123
>>> a
'123'
>>> type(a)
<class 'str'>
>>> a = int(input("input:"))
input:123
>>> a
123
>>> type(a)
<class 'int'>