匹配_有限自动机字符串匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称为字符串。 原理 有限自动机 定义...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
贪心算法
概述 贪心算法（Greedy Algorithm）是一种构造性算法，用于解决最优化问题 其核心思想是在每一步选择中，都采取当前状态下最优的选择，期望通过一系列局部最优的选择达到全局最优 贪心算法在许多实际问题中非常有效，但并不是所有问题都适用 特点 局部最优选择 每一步都选择当前...
排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...
动态规划相关
概述 动态规划（Dynamic Programming，简称 DP）是一种通过分解问题来解决复杂问题的算法技术，特别适用于具有最优子结构性质的问题，即问题的最优解可以由其子问题的最优解构建而成 动态规划的核心思想是将问题分解成更小的子问题，并保存这些子问题的解，避免重复计算，从而...
匹配_KMP模式匹配算法：二
预处理操作 参数 iterP_begin:模式序列P的起始迭代器 iterP_end:模式序列P的终止迭代器 解析 初始化 pai[1] = 0,k = 0 遍历(q从：2->m) 从2开始，因为Pk必须是Pm的真子集。 条件：k > 0 && p[k...
排序_冒泡排序
简述 冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。 复杂度 名称 最好 平均 最差 空间 稳定性 冒泡排序 n n2 n2 1 是 理解 冒泡排序，有n个数字，就要进行n次大循环 每次大循环，会找到所有数里面的...
一些变量值交换的方法
第三个变量 实现 优点 简单易懂，逻辑清晰 缺点 需要额外的空间来存储临时变量 异或运算 实现 优点 不需要额外的空间 运算只使用基本的逻辑运算，适用于底层硬件编程 缺点 对大多数程序员来说，这种方法不如使用第三个变量的方式直观，容易引起误解 如果 a 和 b 是同一个变量，这种...
匹配_KMP模式匹配算法：一
模式匹配 对子串的定位操作通常被称为串的模式匹配 简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止 朴素的模式匹配算法 KMP模式匹配算法 S串：abcdefgab T串...
基础算法模板
快速排序 归并排序 整数二分算法 浮点数二分算法 高精度加法 高精度减法 高精度乘低精度 高精度除以低精度 一维前缀和 二维前缀和 一维差分 二维差分 位运算 双指针算法 离散化 区间合并
搜索当前分类