极简

不了解堆结构的同学请先移步《堆与堆排序》 什么是加强堆？ 我们现在知道，堆结构主要用来处理海量数据下的动态优先级问题，需要频繁入队和频繁把优先级最高的元素出队。但有一种情形是普通堆结构难以高效处理的：一旦堆中的数据发生改变，如果不维护，此堆将作废无法使用；如果维护，那么定位发生变动的元素所需要的时间复杂度就为 O(N) ，其性能变得低效。为了应对堆中数据可能发生改变的情况，加强堆闪亮登场。 加强堆与普通堆的不同之处在于：加强堆使用了一张哈希表来记录元素及其所在位置。当元素发生变动时，可以由这张表快速定位到所在位置，从而进行相应调整。注意，哈希表的键为元素，值为其对应的位置，即数组下标；而数组本身也是算一张索引表，数组下标是索引，数组内容则是元素。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 ...

约束用来保证数据库中数据的有效性和正确性。 主键约束 主键（PRIMARY KEY）的完整称呼是“主键约束”，是 MySQL 中使用最为频繁的约束。一般情况下，为了便于 DBMS 更快的查找到表中的记录，都会在表中设置一个主键。使用主键应注意以下几点： 每个表只能定义一个主键。 创建主键时，自动创建主键索引 主键值必须唯一标识表中的每一行，且不能为 NULL ，即表中不可能存在有相同主键值的两行数据。这是唯一性原则。 一个字段名只能在联合主键字段表中出现一次。 联合主键不能包含不必要的多余字段。当把联合主键的某一字段删除后，如果剩下的字段构成的主键仍然满足唯一性原则，那么这个联合主键是不正确的。这是最小化原则。 创建主键

最大线段重合问题 问题描述 给定很多线段,每个线段都有两个数 [start, end] ，表示线段开始位置和结束位置，左右都是闭区间规定：1）线段的开始和结束位置一定都是整数值；2）线段重合区域的长度必须>=1，也就是说仅顶点重合并不算重合区域。返回线段最多重合区域中,包含了几条线段。 问题分析 我们一步一步分析。 首先，怎么判断两条线段不重合？容易想到，当 line1.left >= line2.right 或 line1.right<=line2.left 时，就可以判定这两条线段不重合了。如下，line1.right<line2.left ，line3.left>line2.right 所以 line2 与 line1、line3 都不重合。 接着，如何判断两条线段不重合？仔细分析后可以发现，当 line1.left<=line2.left<line1.right 时，line1 与 line2 就发生重合(无需考虑 line2.right )，如下图： 有读者一定会疑问，当 line2.left<=line1.left&l ...

比较器 比较器用于自定义数据类型的比较，主要有两种方式： 基于函数的比较器 C++用模板实现十分方便，而且这种方式不仅能够传函数比较器，还可以传仿函数和lambda函数 ： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<unordered_map>#include<iostream>#include<vector>#include<utility>#include<algorithm>#include<list>using namespace std;template<class T>void mySwap(T& a, T& b) { T tmp = a; a = b; b = tmp;}struct stu{ string name; int age; stu(in ...

完全二叉树 什么是完全二叉树？ 如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是 满二叉树 ；也可以这样解释：如果二叉树中除了叶子结点，每个结点都有左右两个子树，则此二叉树称为满二叉树。如下两个树都是满二叉树： 而 完全二叉树 的定义为：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。也可以这么定义：一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如下两棵树就是完全二叉树： 完全二叉树的表示 二叉树的存储结构有两种，分别为顺序存储和链式存储。这里我们采用顺序存储。完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。 图示如下： 以数组下标 i 表示节点的位置，可得以下公式： 节点i的父节点=[(i-1)/2] ，[ ] 表示向下取整。比如上图中值为 9 的节点，其下标为 4，[ (4-1) / 2 ] = 1，所以其父节点 ...

索引简介 在 MySQL 中，通常有以下两种方式访问数据库表的行数据： 顺序访问 顺序访问是在表中实行 全表扫描 ，从头到尾逐行遍历，直到在无序的行数据中找到符合条件的目标数据。顺序访问实现比较简单，但是当表中有大量数据的时候，效率非常低下。例如，在几千万条数据中查找少量的数据时，使用顺序访问方式将会遍历所有的数据，花费大量的时间，显然会影响数据库的处理性能。 索引访问 索引访问是通过遍历索引来访问表中记录行的方式。使用这种方式的前提是对表建立一个索引，在列上创建了索引之后，查找数据时可以直接根据该列上的索引找到对应记录行的位置，从而快捷地查找到数据。索引之所以快，是因为其底层采用 B+ 树，详细内容见：Mysql索引 . 索引最大的优点就是在海量数据下能够大幅提高查询速度。当然，索引也有缺点：1）索引需要占磁盘空间；2）当对表中的数据进行增加、删除和修改的时候，索引也要动态维护，这样就降低了数据的维护速度。索引可以提高查询速度，但是会影响插入记录的速度 。因为，向有索引的表中插入记录时，数据库系统会按照索引进行排序 ，这样就降低了插入记录的速度，插入大量记录时的速度影响会更加 ...

视图是什么 MySQL 视图（View） 是一种虚拟存在的表，同真实表一样，视图也由列和行构成，但视图并不实际存在于数据库中 。行和列的数据来自于定义视图的查询中所使用的表（ 基表 ），并且还是在使用视图时动态生成的。数据库中只存放了视图的定义（.frm文件），并没有存放视图中的数据 ，这些数据都存放在定义视图查询所引用的基表中。使用视图查询数据时，数据库会从基表表中取出对应的数据。因此，视图中的数据是依赖于基表表中的数据的。一旦基表中的数据发生改变，显示在视图中的数据也会发生改变；在视图中修改数据，基表中的数据也会发生改变。 从下图可见，创建视图后，只生成了视图的 .frm 文件，没有 .ibd 文件，这是因为 customer_info.frm 与 customer_view.frm 的数据都是由 customer_info.ibd 提供。 视图的作用 保密 看这样一个需求：公司职员表的信息很多（姓名、薪水、部门、上级、工号、电话等），而其中有些信息属于个人隐私（薪水、电话），我们希望将此表下放到某管理员时，他只能看到其中的部分信息（姓名、部门、上级、工号），此时，就需要生成原 ...

荷兰国旗问题 问题描述 拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。该问题本身是关于三色球排序和分类的，由荷兰科学家 Dijkstra 提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra 就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。下面是问题的正规描述： 现有 n 个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。在算法中，更多这样描述：如何通过两两交换，将一个数组中小于 N 的数放在靠左边，等于 N 的数放在靠中间，大于 N 的数放在靠右边 ；比如，数组 arr[1, 14, 5, 16, 8, 7], N=8, 则两两交换后得到[1, 7, 5, 8, 16, 14]。注意，左右两边内部不一定有序 。 问题分析 设计一个大(右)小(左)区间，通过不断扩展区间达到 分区(partition) 的效果。过程图示如下： 有以下几点需要注意： ...

问题描述 给定一个数组 arr，两个整数 lower 和 upper，返回 arr 中有多少个子数组的累加和在 [lower, upper] (左闭右闭)范围上。注意，子数组是连续的，单独一个元素也是子数组 。 重要工具 — 前缀和数组 当我们需要 频繁计算 数组中 [l, r] 范围中元素的累加和时，如果每次都要遍历子区间的元素，就显得十分低效，此时前缀和数组就有大用处了。前缀和数组的元素是原数组从 0 下标开始到当前位置所有元素的累加和，比如：arr[4, 8, 6, 10, 12] ，其对应的前缀和数组为：presum[4, 12, 18, 28, 40]；当需要计算 arr 的区间 [2, 4] 中的累加和时，只需要用 presum[4] - presum[2-1] 就可得到对应的累加和。原理很好理解，不再过多阐述。 分析 在不使用前缀和数组的情况下，此问题的复杂度将达到 O(N3)O(N^3)O(N3) ：从下标 0 遍历 N 次 -> 从下标 1 遍历 N-1 次 ->从下标 2 遍历 N-2 次 …每次遍历时，都还需要遍历该范围内的元素以计算累加和。如果 ...

排序稳定性 定义：假定在待排序的序列中，存在多个相同值，若经过排序，这些值的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。 排序稳定性很容易被认为是排序速度的稳定性，比如插入排序就是速度不稳定的算法。 排序稳定性对于基础类型（如 int、double 等）没有任何意义，而对非基础类型则具有重要意义。设想下面两个场景： 打印整个年级的名册，要求先按班级排序，然后班级内部再按年龄排序，这就要求排序算法具有稳定性。 你在淘宝上购买商品，如果先将价格从低到高排列，再将评价从高到低排列，那么排在前面的就是物美价廉的商品。 那么哪些排序算法具有稳定性呢？注意，排序稳定性取决于具体实现的细节，例如冒泡排序、选择排序以及归并排序，它们既可以是稳定排序，也可以是不稳定排序，关键取决于你如何处理两个相等的值（把前者仍放前面，后者仍放后面） 。其他排序算法的稳定性见下表。 综合比较 排序 时间复杂度 空间复杂度 稳定性 冒泡排序 O(N^2) O ...