暴力子字符串查找算法隐式回退 性能 显式回退Knuth-Morris-Pratt算法确定有限状态自动机 DFA的构造 性能Boyer-Moore算法跳跃表的构建 性能Rabin-Karp指纹字符串算法关键思想 Horner方法 性能字符串的一种基本操作就是子字符串查找。比如在文本编辑器或是浏览器中查找某个单词时，就是在查找子字符串。子字符串的长度（可能为100或1000）相对于整个文本的长度（可能为100万甚至是10亿）来说一般是很短的，在如此多的字符中找到匹配的...
使用正则表达式描述模式 非确定有限状态自动机NFA 模拟NFA的运行NFA的表示 构造与正则表达式相对应的NFA NFA的模拟与可达性除了查找子字符串，在很多时候并不知道被查找模式的完整信息，这时就需要用到正则表达式了。正则表达式在子字符串查找、合法性校验、网络爬虫等方面有着非常广泛的应用。 使用正则表达式描述模式 正则表达式对模式的描述，基于几个基本操作。连接操作，比如AB，表示由A和B连接而成的模式。 或操作，或操作可...
读写二进制数据 基因组数据的压缩 游程编码位图霍夫曼压缩前缀码和单词查找树 构造前缀码的单词查找树 写入和读取单词查找树 使用前缀码压缩 使用前缀码展开LZW压缩LZW的单词查找树 LZW的单词查找树 LZW压缩的展开对数据进行压缩能够有效节省保存信息所需的空间和传输信息所需的时间。虽然计算机存储设备的成本在不断降低，但由于需要存储的数据在飞速膨胀，压缩算法仍有非常重要的意义，因为与以往相比，数据被压缩后节省的空间会...
4.1 排序 4.1.1 选择排序 简单选择排序是指，对一个序列A中的元素A[1] ~ A[n],令i从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。 4.1.2 插入排序 直接插入排序是指，对序列A的n个元素A[1] ~ A[n],令i从2到n枚举，进行n-1趟操作。假设某一趟时，序列A的前i-1个元素A[1] ~ A[i-1]已经有序，而范围[i,n]...
问题 A: 通信系统 时间限制: 1 Sec 内存限制: 32 MB 提交: 1677 解决: 456 [提交][状态][讨论版][命题人:外部导入] 题目描述 某市计划建设一个通信系统。按照规划，这个系统包含若干端点，这些端点由通信线缆链接。消息可以在任何一个端点产生，并且只能通过线缆传送。每个端点接收消息后会将消息传送到与其相连的端点，除了那个消息发送过来的端点。如果某个端点是产生消息的端点，那么消息将被传送到与其相连的每一个端点。 为...
概念快慢指针判断链表是否有环Bool ifLoopOfList(List head){List quick=NULL;List slow=NULL;quick=slow=head;do{quick=quick->next->next;slow=slow->next;printf("quick->%d\tslow->%d\n",quick->data,slow->data);if(quick==slow){return 1;}}while(quick);return 0;} 工程文件 #include <stdio.h> #include <stdlib.h> typedef struct node{int data;struct node *next; }Node,*List; typedef int Bool; List createLoopList...
PAT B1036?跟奥巴马一起编程?(15分)美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！ 输入格式： 输入在一行中给出正方形边长 N（3）和组成正方形边的某种字符 C，间隔一个空格。 输出格式： 输出由给定字符 C 画出的正方形。但是注意到行...
1、选择排序 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。 步骤：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 重复第二步，直到所有元素均排序完毕。总共需要进行n趟操作（1≤ i ≤ n），每趟操作选出待排序部分[i...
键索引计数法频率统计 将频率转换为索引 数据分类 回写低位优先的字符串排序 高位优先的字符串排序许多重要而熟悉的问题都是基于字符串处理的，比如信息处理（根据给定的关键字搜索网页、文档）、通信系统（发送文本消息、电子邮件、下载电子书）、编程系统（程序是由字符串组成的，再由编译器或解释器将字符串转换为机器指令）、基因组学（生物学家根据密码子将DNA转换为由A、C、T、G四个字符组成的字符串，字符串处理已经成为了计...
最小生成树的应用 切分定理 贪心算法 加权无向图的数据结构 Prim算法 Kruskal算法最小生成树的应用 加权图是一种为每条边关联一个权值的图模型，这种图可以表示许多应用，比如在一副航空图中，边表示航线，权值就可以表示距离或费用；在一副电路图中，边表示导线，权值就可以表示导线的长度或成本。在这些情形中，最令人感兴趣的便是如何将成本最小化。最小生成树就是用于在加权无向图中解决这类问题的。最小生成树相关的算法在通信...
加权有向图 数据结构加权有向边 加权有向图 最短路径边的松弛 Dijkstra算法地图或者导航系统是最短路径的典型应用，其中顶点对应交叉路口，边对应公路，边的权重对应经过一段路的成本（时间或距离）。在这个模型中，问题可以被归纳为：找出从一个顶点到达另一个顶点的成本最小的路径。此外，网络路由、任务调度等也属于同类问题。 加权有向图 加权有向图是研究最短路径问题的模型。在加权有向图中，每条有向边都有一个与之关联的权...
概述Dynamic programming，缩写：DP 通过将原问题分解为相对简单的子问题的方式来求解复杂问题。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 常见解题逻辑 典型应用场景
~ 参考 5min学算法公众号 概述 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 适用前提：局部最优策略能导致产生全局最优解贪心算法作为五大算法之一，在数据结构中的应用十分广泛。例如：...
概述 在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空...
7.1栈的应用 栈:后进先出，可以理解为一个箱子，而箱子的容量仅供一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把箱子最上方的书拿出。 栈顶指针：始终指向栈的最上方元素的一个标记，栈中没有元素（即栈空）时令TOP为-1. 栈的常见操作示范实现,使用数组st[]来实现栈: (1)清空(clear): 栈的清空操作将栈顶指针TOP置为-1，表示栈中没有元素。 void clear(){TOP = -1; } (2)获取栈内元素个数(size) 栈内元素个数为TOP...