算法临阵磨枪.txt

————

字典树：
	特性：
		1、字典树用边表示字母
		2、有相同前缀的单词公用前缀节点，那我们可以的得出每个节点最多有26个子节点（在单词只包含小写字母的情况下）
		3、整棵树的根节点是空的。为什么呢？便于插入和查找，这将会在后面解释。
		4、每个单词结束的时候用一个特殊字符表示，图中用的‘$’，那么从根节点到任意一个‘$’所经过的边的所有字母表示一个单词。
	编号方式：
		trie[i][j] = k;
		1、编号为i的节点的第j个孩子是编号为k的节点，相同字母编号可能不同，编号为i, k
		2、编号为i的节点的第j个孩子是编号为k的节点，相同字母编号相同，编号为i
	插入新单词：
	void insert()	// 采用第一种编号方式，id为孩子的次序，root为当前节点的编号，trie[root][id]为当前节点的第id个孩子的节点的编号
	{
    len = strlen(s);//单词s的长度
    root = 0;//根节点编号为0
    for(int i = 0;i < len; i++) {
        int id = s[i] - 'a';		//id为当前节点的孩子的编号
        if(!trie[root][id])				//如果之前没有从root到id的前缀 
          trie[root][id] = ++tot;	//插入，tot即为第一种编号的计数器
        root = trie[root][id];		//顺着字典树往下走
    }
	}
	查找前缀是否出现过：
	bool find()
	{
    len = strlen(s);
    root = 0;							//从根结点开始找
    for(int i = 0; s[i]; i++) {
        int id = s[i] - 'a';	
        if(trie[root][x] == 0)  //其实查找不过就是变形的插入 
        	return false;			//以root为头结点的x字母不存在，返回0 
        root = trie[root][x];		//为查询下个字母做准备，往下走 
    }
    return true;//找到了
	}
	查询某个单词是否出现过：
		我们用bool变量 v[i]表示节点i是否是单词结束的标志。	//i就是节点的编号，也就是上边代码中的tot
    那么最后return的是v[root],所以在插入操作中插入完每个单词是，要对单词最后一个字母的v[i]置为true，其他的都是false
  查询前缀出现的次数：
  	开一个sum[i]，表示位置i被访问过的次数，
	  那么最后return的是sum[root]，插入操作中每访问一个节点，都要让他的sum++
	  这里前缀的次数是标记在前缀的最后一个字母所在位置的后一个位置上。


——————

红黑树：
	特性：
		1、每个节点是黑色或者红色
		2、根节点是黑色
		3、每个叶节点（空节点）是黑色
		4、如果一个节点是红色的，那个他的子节点必须是黑色的
		5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
	注意：
		1、特性3的叶子节点是指空节点
		2、特性5可以确保没有一条路径会比其他路径长出两倍，因而红黑树是接近平衡的二叉树
	时间复杂度：
		O(lgn)
	红黑树的左旋和右旋：
		左旋中的左，意味着被旋转的节点将从子树的根节点变成一个左节点
		右旋中的右，意味着被旋转的节点将从子树的根节点变成一个右节点
	具体算法：
		还没什么时间看

——————

字符串匹配算法：

BF：
	朴素算法，不赘述，辣鸡
	该算法之所以慢，是因为只关心有效的位移，而不关心无效的位移

KMP：
	经典算法，不再赘述
	基本思想就是充分利用目标字符串的特性，利用最长前后缀公共元素长度来建立匹配失败的时候的next数组，根据next数组进行匹配
	时间复杂度：
		O(m+n)

Rabin-karp算法：
	基本思路：
		假设子串的长度为M，目标字符串的长度为N
		计算字串的HASH值
		计算目标字符串中每个长度为M的子串的HASH值，共需要计算N-M+1次，因为长度不足N的时候不需要计算
		比较HASH值
		如果HASH值不同，则必然不匹配，如果HASH值相同，则需要用朴素算法再次判断
	加快HASH计算速度：
		Rabin-Karp算法并不是对目标字符串的每一个长度为M的子串都重新计算hash值，而是在前几个字串的基础之上，计算下一个子串的hash值
		这就加快了HASH的计算速度，将朴素算法中的内循环的时间复杂度从O(M)降到了O(1)。
	时间复杂度：
		平均时间复杂度：O(M+N)

BM算法：
	SUNDAY算法就脱胎其中，但是还没具体了解

SUNDAY算法：
	核心思想：
		在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
	基本思路：
		THIS_IS_A_SIMPLE_EXAMPLE
		EXAMPLE
		原字符串和子串左端对齐，发现不匹配后检测原字符串的下一个字符“_”是否在子串中出现，没有出现，则直接将字符串移动到下一个位置
		THIS_IS_A_SIMPLE_EXAMPLE
		    EXAMPLE
		移动之后发现还是不匹配，但是原字符串的下一个字符“E”在子串中出现了，那么移动子串靠后的字符与原子串对齐
		这样从头逐个开始比较，最终匹配成功
	时间复杂度：
		最坏时间复杂度：O(MN)
		最好时间复杂度：O(N)
		平均时间复杂度：O(M+N)

——————

排序算法：
	算法		平均时间复杂度   最好    最坏    空间复杂度   排序方式    稳定性
	冒泡排序	O(n2)				O(n)		O(n2)		O(1)			内排序			稳定
	选择排序	O(n2)				O(n2)		O(n2)		O(1)			内排序			不稳定
	插入排序	O(n2)				O(n)		O(n2)		O(1)			内排序			稳定
	希尔排序	O(nlogn)			O(nlog2n)	O(nlog2n)	O(1)			内排序			不稳定
	归并排序	O(nlogn)			O(nlogn)	O(nlogn)	O(n)			外排序			稳定
	快速排序	O(nlogn)			O(nlogn)	O(n2)		O(logn)			内排序			不稳定
	堆排序		O(nlogn)			O(nlogn)	O(nlogn)	O(1)			内排序			不稳定
	基数排序	O(d(n+rd))			O(d(n+rd))	O(d(n+rd))	O(rd)			内排序			稳定

基数排序：
	基本思想：
		也叫桶排序，采用了多关键字排序的思想，举个例子解释什么是多关键字排序：
			一副有有花色并且有数值的扑克要按花色和数值进行排序，那么可以先按面值分成13堆，将13堆牌从小到大叠在一起，然后将整副牌颠倒过来，按花色分成四堆，再按从小到大的顺序合并，这样就得到了满足要求的牌。
		对关键字排序分两种：
			最高位优先（MSD）：
				先对最主位关键字K0排序，形成具有相同K0值的多个子序列，然后就每个子序列对关键字K1进行排序，依次重复
			最低位优先（LSD）：
				从最次为关键字Kd-1进行排序，然后对高一位关键字Kd-2进行排序，依次重复，知道对K0排序后形成一个有序序列
			不同点：
				若按照MSD排序，必须将序列逐层分为多个子序列，然后对各个子序列进行排序；而用LSD进行排序时，不必分成子序列，每个关键字都是整个序列参加
			在基数排序中使用的是最低位优先的思想。
		基数排序：
			基数排序则是通过“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法，因为有的关键字可以看作是多个逻辑关键字复合而成。
			如果关键字是数值，则可以把每一个十进制数字看作关键字，也就是说，一个三位数是由三个关键字构成，分别是它的个位数、十位数、百位数。
			由于分解而成的每个关键字都在同一个范围内（0~9），因而用LSD更为合适。
	算法过程：
		我们需要给待排序的记录准备10个桶，分别代表数字（0~9），对应着待排序记录中每一位的数值。
		先按照记录的个位进行分配，根据每个数的个位决定它加入哪个桶中，然后进行收集
		之后按照十位进行分配，位数不足的补0，然后进行收集，以此类推
	算法空间的优化：
		该算法由于需要准备桶，所以最初没有对算法空间复杂度进行优化时，需要一个10*n的二维数组作为临时空间。
		教材上使用“链式基数排序”的方法大大减少的空间的占用。
	时间复杂度：
		O(d(n+rd))：
			d：每个记录中含有的关键字的个数
			n：记录的个数
			rd：每个关键字的取值范围

——————

图：
	基本概念：
		无向图：
			完全图：有0.5n(n-1)条边的无向图
			稀疏图：很少条边或弧
			稠密图：有较多的边或弧
			权：与图的边或弧相关的数
			连通：节点到节点之间有路径
			连通图：任意两个节点之间都是连通的
			连通分量：无向图中的极大连通子图
			生成树：极小连通子图
			网：带权的图通常称为网
		有向图：
			强连通图：任意两个节点都存在路径
			强连通分量：有向图中的极大强连通子图
	存储结构：
		数组表示法：
			也叫邻接矩阵，表示n个顶点信息和n2个弧信息的存储量
			无向图：
				可以用压缩存储的方式值存入矩阵的下三角元素
			有向图：
				有向图行非零元素表示出度，列非零元素表示入度
		邻接表：
			是一种链式存储结构

搜索：
	时间复杂度：
		邻接矩阵作图：
			查找每个顶点的邻接点所需的时间为O(n^2)
		邻接表作图：
			查找每个顶点的邻接点的时间为O(e)，此时深度优先遍历的时间复杂度为O(n+e)
	深度优先搜索：
		类似树的先序遍历，是树的先序遍历的推广
	广度优先搜索：
		类似树的层次遍历的过程
	DFS和BFS：
		深搜和广搜的时间复杂度相同，区别只在于对顶点的访问数序的不同

图的连通性：
	连通图是指，在途中任一顶点出发，进行DFS或BFS，便可以访问到图中所有顶点。
	生成树：
		无向连通图的一个子图如果是一颗包含原图的所有顶点的树，则该子图称为原图的生成树。
		通过DFS得到的是深度优先生成树
		通过BFS得到的是广度优先生成树

最小生成树（MST）：
	最小生成树问题就是，构造连通网的最小代价生成树的问题，一棵生成树的代价就是树上各边代价的和
	原则：
		选择n-1条边构成最小生成树
		尽量选择权值最小的边，但不能构成回路
	MST的性质：
		假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果(u,v)是一条具有最小权值的边，则必定存在一颗包含便（u,v）的最小生成树。
		下边的两种最小生成树算法都使用了MST性质
	最小生成树算法：
		普里姆算法：
			基本思想：
				以顶点为主导，按照逐个将顶点连通的方式来构建最小生成树
			实现步骤：
				从图中某一顶点出发，选择你则和他关联的具有最小权的边，将其顶点加入到生成树的顶点集合U中
				之后每一步，都从“一个顶点在U中，二另一个顶点不在U的各条边”中选择权值最小的边，加入生成树的边集中，顶点加入U中
				以此类推，知道网络中的所有顶点都加入到生成树顶点集合U中为止
			时间复杂度：
				邻接矩阵：O(V^2)
				邻接表：O(E+VlogV)
			适用场景：
				求边稠密的网的最小生成树
		克鲁斯卡尔算法：
			基本思想：
				以边为主导，始终选择当前可用的最小权值的边
			实现步骤：
				设连通网络为G(V,{E})，最初先构建一个没有边的非连通图
				在E中选择一个具有最小权值的边，如果该边的两个顶点落在不同的连通分量上，则将该边加入到边集中，否则舍去，重新选择一条权值次小的边
				以此类推，直到所有的顶点在同一连通分量上为止
			时间复杂度：
				O(eloge)	//e是网中边的数目
			适用场景：
				边稀疏的网的最小生成树

最短路径：
	概念：
		从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径
	迪杰斯特拉算法：
		特点：
			使用了BFS解决带权有向图或带权无向图的“单源最短路径问题”，常用于路由算法
		基本思路：
			采用了一种贪心的策略，每次都查找与该点距离最近的点
		实现步骤：
			声明一个数组dis来保存源点到各个顶点的最短距离，以及一个用于保存已经找到了最短路径的顶点的集合T
			开始时，设s的权重为0，对于顶点如果存在能直接到达的边(s,m)，就把dis[m]设为该边的权，否则设为无穷大，初始时T里面只有s
			然后从dis中选择最小值，那么该值就是s到该值所对应的m的最短路径，把该顶点加入T中
			然后查看新加入的顶点是否可以到达其他定点，并查看通过该点到达m的路径是否比dis中的短，是的话就替换掉当前dis中的值
			以此类推，直到T中包含了图中所有的顶点为止
	弗洛伊德算法：
		特点：
			解决“任意两点间最短路径”的算法，可以正确处理有向图或无向图的最短路径问题，但是不能处理存在负权回路的图的问题
		实现步骤：
			假设图中有顶点N个，则需要对S和P进行N次更新。
			使用弗洛伊德算法时，需要引入两个矩阵，S和P，S中的元素a[i][j]表示顶点i到顶点j的距离，P中的元素b[i][j]表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点
			开始时，S中的a[i][j]的值为顶点i到顶点j的权值，如果i和j不相邻，则为无穷大，P中的b[i][j]为j的值
			之后进行更新，如果“a[i][j] > a[i][0] + a[0][j]”，则更新a[i][j]为“a[i][0]+a[0][j]”，b[i][j]为“b[i][0]”
			如此进行N次，更新完成