算法

动态规划问题的分类求最大最小值从左上角走到右下角路径的最大数字和最长上升子序列长度计数有多少种方式...有多少种方法选出k个数使得和是sum求存在性取石子游戏，先手是否必胜能不能选出k个数使得和是sum常见动态规划问题的类型坐标型动态规划(20%)：二维数组下标就是坐标，如机器人路线问题序列型动态规划(20%)：划分型动态规划(20%)：给一个字符串或数组让划分成若干段满足一些性质区间型动态规划(15%)：选择连续区间而符合一定条件，f(i,j)背包型动态规划(10%)：一定空间的背包最多带多少物品的问题最长序列型动态规划(5%)：最长上升子序列等类似问题博弈型动态规划(5%)：博弈算出一个人

贪心算法的思想即对于目标T，对于达成它的每一局部都选择最优选项，直到满足或最终近似满足为止，最终结果或许不是全局最优解，但应该是近似最优解，因为它足够简单。每一步都采取局部最优做法！贪婪算法大多时候都是近似最优算法！贪心算法的三步走：第一步：明确到底什么是最优解？第二步：明确什么是子问题的最优解？第三步：分别求出子问题的最优解再堆叠出全局最优解？贪心算法的前提：原问题复杂度过高；求全局最优解的数学模型难以建立；求全局最优解的计算量过大；没有太大必要一定要求出全局最优解，“比较优”就可以。以上情况几乎99.99999999999%就要使用贪心算法的思想来解决问题！分解子问题的方法：1.按串行任务

回溯法回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。使用回溯法解题的基本步骤如下所示：(1)针对所给问题，定义问题的解空间。(2)确定易于搜索的解空间结构。(3)以深度优

分治法分治算法采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。我们只要求出子问题的解，就可得到原问题的解。在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，依此类推，直至可以直接求出解为止。这就是分治策略的基本思想。使用分治算法解题的一般步骤如下所示：(1)

迭代法迭代法也被称为辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。在使用迭代算法解决问题时，需要做好如下3个方面的工作：(1)确定迭代变量在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。(2)建立迭代关系式迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。(3)对迭代

递归法在计算机编程应用中，我们常常遇到代码的递归调用，事实上，递归是一种编程技巧，它是分治思想的一种重要体现。递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。从直观上讲，递归是将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已经已知答案的最小问题为止，然后再逐级返回，从而得到大问题的解。从本质上讲，计算机在执行递归调用时是一个不断压栈出栈的过程，递归的每一次“递”都是入栈，将函数状态或临时变量的指针入栈，而每一次“归”时都是出栈，将子问题的解逐渐交还给上层调用者。递归算法有如下3个特点:(1)递归过程一般通过函数或子过程来实现。(2)递归算法在函数或子

递推法递推算法犹如稳重的有经验的老将，使用“稳扎稳打”的策略，不断利用已有的信息推导出新的东西。在日常应用中有如下两种递推算法：(1)顺推法：从已知条件出发，逐步推算出要解决问题的方法。(2)逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。顺推法例如斐波那契数列就可以通过顺推法不断递推算出新的数据：兔子问题：有一对兔子,从出生后第3个月起每个月生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子不死,问第二十个月的兔子对数是多少?算法分析：分析:我们要想办法找规律兔子对数：第一个月：1；第二个月:1；第三个月:2；第四个月:3；第五个月:5；第六个月:

一、枚举法枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。使用枚举算法解题的基本思路如下所示：(1)确定枚举对象、枚举范围和判定条件。(2)逐一枚举可能的解，验证每个解是否是问题的解。枚举算法一般按照如下3个步骤进行：(1)题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。(2)判断是否是真正解的方法。(3)使可能解的范围降至最小，以便提高解决问题的效率。什么时候选择枚举法？在任何情况下，都需要选准最合适的对象，无论是枚举还是其他算法思想，这是最关键的。选准(枚举)对象的根本原因在于优化，具体表现为减少求解步骤，缩小求解的解空间

引入随着信息爆炸时代的来临，互联网上充斥着着大量的近重复信息，有效地识别它们是一个很有意义的课题。例如，对于搜索引擎的爬虫系统来说，收录重复的网页是毫无意义的，只会造成存储和计算资源的浪费；同时，展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括：镜像网站内容复制嵌入广告计数改变少量修改一个简化的爬虫系统架构如下图所示：事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数

引入什么情况下需要布隆过滤器？我们先来看几个比较常见的例子：字处理软件中，需要检查一个英语单词是否拼写正确在FBI，一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里，一个网址是否被访问过yahoo,gmail等邮箱垃圾邮件过滤功能这几个例子有一个共同的特点：如何判断一个元素是否存在一个集合中？常规思路与局限如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hashtable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。数组链表树、平衡二叉树、TrieMap(红黑

Trie，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，RadixTree/Trie，PATRICIAtree，以及bitwise版本的crit-bittree。当然很多名字的意义其实有交叉。Trie树是一种非常重要的数据结构，它在信息检索，字符串匹配等领域有广泛的应用，同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hotspot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。Hash算法一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓

排序排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。排序的主要目的就是实现快速查找。排序分类增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。稳定排序和不稳定排序：具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之是不稳定的。内部排序和外部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之成为外部排序。本文目录冒泡排序一、冒泡排序（BubbleSort）1.1思想冒泡排序(bubblesort)：每个回合都从第一个元素开始和它后面的元素

哈希表的概念哈希表（HashTable）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构，那该有多好。这就是哈希表创建的基本思想，而实际上哈希表也实现了这样的一个“夙愿”，哈希表就是这样一个集查找、插入和删除操作于一身的数据结构。哈希表（HashTable）：也叫散列表，是根据关键码值（key-value）而直接进行访问的数据结构，也就是我们常用到的map。哈希函数：也称为是散列函数，是Hash

B树B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一种树。其实，B-tree就是B树。B-树的定义B树（B-tree）是一种树状数据结构，是一种平衡的多路查找树，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。一棵m阶的B-树,或为空

我们知道，对于一般的二叉搜索树（BinarySearchTree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。平衡二叉树

目录1、二叉排序树的定义2、二叉排序树的查找3、二叉排序树的插入与删除4、二叉排序树的构造5、二叉排序树的删除定义二叉排序树（BinarySortTree）又称为二叉查找树（BinarySearchTree）、二叉搜索树。它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树的一个结点，则key[y]>=key[x]。那么，这棵树就是二叉查找树。二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后再就行和每个节

查找基本概念查找就是在数据集中找出一个“特定元素”。查找表是由同一类型的数据元素(或记录)构成的集合。查找表是一种以集合为逻辑结构、以查找为核心的数据结构。关键字有时候我们需要指定某数据项的值来查找，这就用到了关键字。关键字是数据元素中某个数据项的值，用以标识一个数据元素。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”；若此关键字能识别若干记录，则称之谓“次关键字”。例：对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。查找表可分为两类:静态查找：仅作查询和检索

最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小，例：公交查询系统。问题解法：求从某个源点到其余各点的最短路径—Dijkstra算法每一对顶点之间的最短路径—Floyd算法例如：从某点到其他各顶点的最短路径最短路径不一定是经过边最少的路径，但在这些最短路径中，长度最短的那一条路径上只有一条边，且它的权值在从源点出发的所有边的权值最小。路径长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小

有向无环图及其应用一个无环的有向图称做有向无环图,简称DAG图。DAG图是一类较有向树更一般的特殊有向图。拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。例，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动。顶点表示活动，有向边表示活动的先后关系的网简称为AOV网。AOV网中不能有环，否则工程无法顺利进行。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological

最小生成树问题提出：要在n个城市间建立通信联络网，城市间的通信线路造价不同，希望找到一种方案使得建立该通信网所需花费的总代价最小。问题分析：n个城市间，最多可设置n(n-1)/2条线路；n个城市间建立通信网，至少需n-1条线路；问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）连起来，且总耗费（各边权值之和）最小。定义：生成树中边的权值（代价）之和最小的树。构造最小生成树的准则：必须只使用该网中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。实例：普里姆(Prim)算法普里姆方法的思想：1）在图中任取一个顶点K作为开始点，令U={k}

图的遍历在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访问过，未访问的值为0，访问过的值为1。图的遍历有两种方法：深度优先搜索遍历（DFS）、广度优先搜索遍历（BFS）。深度优先搜索深度优先搜索思想首先访问顶点i，并将其访问标记置为访问过，即visited[i]=1；然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；若与i有边相连的顶点都被

图的基本概念图是由一个顶点集V和一个边集E构成的数据结构。Graph=(V，E)图中代表一条边的顶点的偶对如果无方向性，即无序，则称此图为无向图。例：V={V1,V2,V3,V4,V5}；E={(V1,V2),(V1,V4),(V2,V3),(V3,V4),(V2,V5)}在无向图中，(x,y)与(y,x)表示同一条边。图中代表一条边的顶点的偶对如果有序的，则称此图为有向图。在有向图中，用<x,y>表示一条有向边，在有向图中也称边为“弧”，x称为边的弧尾或始点，称此边为顶点x的一条出边；y称为边的弧头或终点，称此边为顶点y的一条入边。例：V={V1,V2,V3,V4}；E={&lt

二叉树遍历的几种方法存储结构：typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode;遍历树的遍历顺序是相对父结点来说的。先序遍历：先访问根结点,然后分别先序遍历左子树、右子树。递归先序：voidPreOrderTraverse(BiTreebt){/*最简单的Visit函数：Visit(ElemTypee){printf(e);}*/if(bt){Visit(bt->data);PreOrderTraverse(bt->lchild);PreOrderT

线索二叉树利用空指针域来真存放结点的前驱和后继信息定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉链表表示的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现：在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域(0指结点，1左前右后)ltag:若ltag=0,lchild域指向左孩子；若ltar=1,lchild域指向其前驱rtag:若rtag=0,rchild域指向右孩子；若rtag=1,rchild域指向其后继例如：遍历中序线索二叉树在中序线索二叉树中

树树的表示方式有树形图表示法:逻辑结构描述直观嵌套集合表示法（文氏图表示法）凹入表示法广义表表示法二叉树二叉树是另一种重要的树形结构，是度为2的有序树，它的特点是每个结点至多有两棵子树。二叉树的递归定义二叉树是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不相交的左子树和右子树。二叉树的特点如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。注意：二叉树不是树的特例。它们是两种不同的数据结构。二叉树举例二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点。(i

串的模式匹配算法子串（模式串）的定位操作通常称为串的模式匹配。这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。串的顺序存储实现#include<stdio.h>#include<string.h>#defineMaxLen256/*定义能处理的最大的串长度*/typedefstruct{charstr[MaxLen];intcurlen;/*定义当前实际串长度*/}SString;BF算法设计思想：将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较

队列队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。队列的修改是依先进先出的原则进行的。队列的基本操作1．初始化队列InitQueue(&Q)将队列Q设置成一个空队列。2．入队列EnQueue(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。3．出队列OutQueue(&Q,&e)将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4．取队头元素GetHead(Q,&e)得到队列Q的队头元素之值，并用e返回其

1.栈的定义栈，也叫堆栈，是最常用也是最重要的数据结构之一。栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。栈操作的特点：后进先出，先进后出。因此，栈称为后进先出表（LIFO,LastInFirstOut）。示意图：2.栈的基本运算初始化栈InitStack(*S)压栈Push(*S,x)——在栈顶插入元素出栈Pop(*S,x)——在栈顶删除元素取栈顶元素GetTop(S,x)判栈空Empty(S)栈的几种状态（最大长度MaxSize为4）：栈空、压栈、栈满、出栈3.栈的存储结构栈有

1.链表线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。采用链式存储结构的表示的线性表简称链表。链式存储方式可用于表示线性结构，也可用于表示非线性结构。链表通常有两个域data域——存放结点值的数据域next域——存放结点的直接后继的地址，需要指针类型表示2.单链表的表示方式3.链表的存储结构由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。用链式存储结构表示线性表中的一个元素时至少需要两部分信息，一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。4.链表的