Data Structure

介绍面试过程中的数据结构，树、Hash表和图。

树

树中常见的概念

节点的度：指的是结点拥有的子树的个数，二叉树的度不大于2

高度：叶子节点的高度是1， 根结点的高度最高

节点的层次：从根结点开始，根结点为第一层，根结点的叶子节点为第二层，以此类推。

三种树的比较

full binary tree vs. complete binary tree vs. perfect binary tree 中文翻译的时候常常容易翻译不准，所以使用英文更加容易说清楚。

Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children. full binary tree 限制每个节点要么是有两个孩子好么是没有孩子。

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible complete binary tree限制最后一层只能是在最后一层的左边有左子树。

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level. perfect binary tree 最后一层一定是满的。

满二叉树

一棵深度为 $k$ 且有 $2^{k+1} -1$个结点的二叉树被称为完美二叉树。

特点：

1. 每一层上的结点都是最大结点数（每层都是满） 数学表达为，$2^{k-1}$
2. 叶子结点全部都是在最底层
3. 最后一层是 2^{k-1}， 总的结点个数是 $2^{k+1} -1$

对满二叉树结点位置进行编号（编号的定义对于完全二叉树的理解有重要的意义）

1. 从根节点开始，自上而下，自左而右
2. 每一结点位置上都有元素

完全二叉树

深度为 $k$ 的具有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为 $k$ 的满二叉树中编号为 $1 \sim n$ 的结点一一对应，称之为完全二叉树。 （满二叉树在实际中不是那么常见，但是完全二叉树就比较常见，因为没有约束最后一层必须是满的，但是存在的结点却保留这满二叉树的性质，存在的结点都是和满二叉树一一对应的）

大根堆和小根堆

特点：

1. 堆是一个完全二叉树( 如果有 h 层，那么 1- h-1 层都是满的，在h 层缺失的若干个 右叶子)
2. 小根堆的根节点的值是最小值，大根堆的根节点是最大值
3. 堆的结构适合采用顺序存储

堆的存储结构 一般都用数组来表示堆，$i $结点的父结点下标就为 $(i–1)/2 $。它的左右子结点下标分别为 $2 * i + 1 $和 $2 * i + 2$。如第0个结点左右子结点下标分别为1和2。在二叉排序树中，某结点的右孩子结点的值一定大于该结点的左孩子结点的值；在堆中却不一定，堆只是限定了某结点的值大于（或小于）其左右孩子结点的值，但没有限定左右孩子结点之间的大小关系。

堆的结构和完全二叉树的区别： 堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（这里的讨论以大根堆为例），所以，堆是结点之间满足一定次序关系的完全二叉树。具有n个结点的堆，其深度即为堆所对应的完全二叉树的深度$logn $。

接下来的树结构都是一种高效的查找结构。

二叉搜索树（二叉排序树）

定义： 是空树或者满足以下的性质

特点：

1. 若左子树不为空，那么左子树上所有结点的值小于（不大于）根结点的值
2. 若右子树不为空，那么右子树上所有结点的值大于（不小于）结点的值

查找、插入、删除操作的最坏时间复杂度

查找、插入、删除操作的平均时间复杂度

1. 二叉查找树出现 $O(N)$ 的时间复杂度在于树形结构变成了单链表的形式。
2. 平衡树和红黑树的区别：平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次，而红黑树的插入/删除操作带来的旋转操作最多为2 or 3次。

平衡二叉树（AVL树，俄国两个人名的首写字母）

可以介绍一个概念：平衡因子。该节点左子树的高度- 该节点的右子树高度，即左右子树高度之差，被称为平衡因子。

平衡二叉树的特点

1. 在AVL树中任意节点的两个子树的高度最大差为1.

2. 查找、删除、插入的平均和最坏情况下都是$O(N)$

使用左旋（left rotation）和右旋（right rotation）来调整树的平衡。

如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：

红黑树

是平衡二叉树的一种，被称为自平衡二叉树。红黑树的每个节点上都存储着表示节点的颜色，可以是红色或者是黑色，所以称为红黑树。相对于 avl 来说，红黑树并不是完整符合平衡条件（任意两个子树的高度最大差为1），因此查找性能从理论上稍微不如 AVL 树。但是插入和删除的效率更高。

红黑树的特性：

1. 节点是红色或者黑色
2. 根结点是黑色
3. 每个叶节点（包括空节点）是黑色
4. 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

自平衡策略

对于一棵红黑树的操作最基本的无外乎增删改查，其中查和改都不会改变树的结构，所以与普通平衡二叉树操作无异。剩下的就是增删操作，插入和删除都会破坏树的结构，不过借助一定的平衡策略能够让树重新满足定义。平衡策略可以简单概括为三种：左旋转、右旋转，以及** 变色**。在插入或删除结点之后，只要我们沿着结点到根的路径上执行这三种操作，就可以最终让树重新满足定义。

三种基本操作：

• 左旋转 对于当前结点而言，如果右子结点为红色，左子结点为黑色，则执行左旋转，如下图：

• 右旋转 对于当前结点而言，如果左子、左孙子结点均为红色，则执行右旋转，如下图：

• 变色

场景：搜索

B 树

B 树概括来说是一个更加一般化的二叉搜索树，即一个节点可以拥有2 个以上的子节点。这种树结构又被称为平衡多路（即不止两个子树）查找树。

首先介绍两个简单类似的树形结构。下面是 2-3 树。其中的2，3表示的可以有2个或者3 个子树。（这种就是一种多路平衡树）

然后是2-3-4 树。

上面的两种可以看做是B 树的特例。B 树中最重要的特性是下面图片中的第三点：除根节点外的非叶子结点都至少有 $\left \lceil m/2 \right \rceil $棵子树。这个性质是控制着要不要进一步的分裂。第五个性质所有的叶子节点出现在同一层次上，不带信息。（参考上面的2-3树）

B 树最重要的是查找，相当于是二叉排序树的扩展。

使用场景：适合于读写相对大的数据块的存储系统，比如硬盘， 常常被用在数据块和文件系统中。

哈夫曼树（最优二叉树）

这个树和上面有点差别。如何根据节点不同的查找频率构造更加有效的搜索树？

总的原则：查询频率高的路径是比较短，查询频率低的路径比较长。最后的平均查找方式最低。

这里引入了一个概念：带权值路径长度（WPL）：设二叉树有 $n$ 个叶子节点，每个叶子节点带有权值 $w_k$， 从根结点到每个叶子节点的长度为$l_k$，则每个叶子节点的带权路径长度纸盒就是 $ WPL = \sum{w_kl_k}$

构造方式：每次把权值最小的两棵树合并。从这种构造方式中可以得到以下的特点：

1. 没有度为1 的节点
2. $n$ 个叶子节点的哈夫曼树总共有 $2n-1$ 个结点
3. 对同一组权值 ${w_1, w_2, w_3… , w_n}$， 存在着不同构的两棵哈夫曼树

最小生成树算法

生成树的特点：

1. 没有环
2. 连接所有的顶点
3. $N $个顶点， $N-1$ 边 (这种数量关系是很重要的)

还有一个要求是边的权重相加是最小。

这里介绍两种算法，kruskal 算法和prim算法。都是贪婪思想。方式不同。

Kruskal 算法 （克鲁斯卡尔）

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点$u_i$, $v_i$应属于两颗不同的树（这个是防止生成环的条件），则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3) ，直到所有顶点都在一棵树内或者有 n-1 条边为止

（其中的判断条件 所选的边属于不同的树，也可以理解为选择的边不能构成环）

Prim 算法（普里姆算法）

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

1. 图的所有顶点集合为 $V$；初始令集合 $u={s} $,$v=V−u$;
2. 在两个集合$u$, $v$能够组成的边中，选择一条代价最小的边$(u_0,v_0)$，并把$v_0$并入到集合 $u$中。
3. 重复上述步骤，直到最小生成树有 $n-1$条边或者 $n$个顶点为止。

在prim 算法中，没有判断是否为环的过程，跳出的条件是第一个列表全部已选，那么就形成了一个最小生成树。

在实现的时候，需要维持三个列表：顶点是否选择列表，顶点之间的最小距离列表和顶点之间的信息列表。

应用场景：

考虑城市之间间隔的距离，建设通信线路的难度等各种因素，将这些因素综合成一个数值表示，然后可以计算最小的建设成本。

写作参考

看视频理解

完全二叉树中叶子节点数量的计算

解法一： 叶子节点为 n/2 （向上取整），其中n 个是节点的总个数 解法二： 节点总数=n0+n1+n2 对于任意一个为空的子树 n0 =n2+1 当节点总数为偶数时候，n1 为1；当结点总数为奇数，n1 为0.所以连方程组，求解n2 和n0

Trie 树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：

a. 根节点不包含字符，除根节点外每一个节点都只包含一个字符 b. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 c. 每个节点的所有子节点包含的字符都不相同

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

1. 优点

• 插入和查询的效率很高，都为O(m)O(m)，其中 mm 是待插入/查询的字符串的长度。（关于查询，会有人说 hash 表时间复杂度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。）
• Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
• Trie树可以对关键字按字典序排序。

2. 缺点

• 当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
• 空间消耗比较大。

3. 应用场景

a. 前缀匹配 例如：找出一个字符串集合中所有以 “五分钟” 开头的字符串。我们只需要用所有字符串构造一个 trie树，然后输出以 五−>分−>钟 开头的路径上的关键字即可。trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能

b. 字符串检索 给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。检索/查询功能是Trie树最原始的功能。给定一组字符串，查找某个字符串是否出现过，思路就是从根节点开始一个一个字符进行比较：

4. 实现

可以参考这里

看动画轻松理解「Trie树」

Hash 表

一个hash 函数 $f(x) $

hash 函数

1. 单向算法（不能从f(x) 得到x, 只能是从x 得到 f(x)）
2. 唯一性
3. 输出长度固定

那么第三条会出现hash 碰撞。常用的处理方法：

1. 开放地址法（总的原则是在冲突的位置查找下一个位置，可以使用线性探查法，平方探查法等方式）
2. 再hash 法（同时使用多个hash 函数，如果第一个hash 函数发生冲突，那么接着使用第二个hash 函数）
3. 链地址法（将同一个hash 值相同的元素使用一个单链表进行存储）

图

连通图

对于无向图 $G$而言，若 $V(G)$中任一两个不同的顶点 $V_i$ 和$V_j$都连通（即有路径），则称$G$为连通图。

对于有向图$G$中， 如果对于两个顶点 $V_i$和$V_j$有一条从 $V_i$到 $V_j$ 的有向路径，同时有一条从 $V_j$ 到$V_i$的有向路径，那么称这两个顶点强连通。如果有向图中两个顶点都强连通，那么称这个图为强连通图。

连通分量

在无向图中，连通分量即为连通子图。

上图中，总共有四个连通分量。顶点A、B、C、D构成了一个连通分量，顶点E构成了一个连通分量，顶点F，G和H，I分别构成了两个连通分量。

强连通分量：在有向图中，尽可能多的若干顶点组成的子图中，这些顶点都是相互可到达的，则这些顶点称为一个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

并查集：判断图上是否存在环。可以参考之前的一个博客。

KMP 算法

next数组的含义：以 i 为终点的后缀 和以1 为起点的前缀相等，并且满足长度最长，那么这个就是 next[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<iostream>

using namespace std;
/**
 s 表示source， p表示pattern，n和m 分别是对应的长度
 get_next是计算了 next数组， 主程序中写了匹配的模板（逻辑结构）
 */
const int N =1e6+10;
int n, m;
char s[N], p[N];
int nex[N];

// 因为存储和计算的时候都是从 1开始的，所以 j+1 才是真正有意义比较项，这个模板其实很好记的。
void get_next()
{
    for(int i =2, j =0; i<=m; i++)
    {
        while(j && p[i] !=p[j+1]) j=nex[j];
        if(p[i] ==p[j+1]) j++;
        nex[i] =j;
    }    
}

// abcd, abcdd
// dd
int main()
{
    cin>> n>>m;
    
    scanf("%s", s+1);
    scanf("%s", p+1);
    
    get_next();
    //匹配
    //for(int i =1; i<=m; i++) cout<< nex[i] <<" ";
    
    for(int i =1, j =0; i<=n; i++)
    {
        while(j && s[i] != p[j+1]) j =nex[j];
        if(s[i] ==p[j+1]) j++;
        
        if(j ==m)
        {
            j =nex[j];
            cout<<"true"<<endl;
            
        }
    }
    return 0;
}

时空复杂度分析

复习之后，这两个视频是需要再快速过一遍的：

视频一：https://www.bilibili.com/video/av32548823/?p=1 视频二：https://www.bilibili.com/video/av32548823/?p=2

快速排序的时间复杂度最坏是 $O(N^2)$， 但是这种情况是很难达到的。 hash 表中时间复杂度最坏是 $O(N)$， 但由于不知道这种hash 函数是什么，所以很难达到这种情况。

做笔试的时候的步骤

1. 首先看数据范围，然后根据数据范围约莫着使用什么算法

下面介绍的是根据数据范围反推算法复杂度和算法内容：

一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下，C++代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

1. $n <= 30$, 指数级别, dfs+剪枝，状态压缩dp
2. $n <= 100 –> O(n^3)$，floyd，dp
3. $n≤1000 => O(n^2)$，$O(n^2logn)$，dp，二分
4. $n≤10000 => O(n \times \sqrt(n)) $，块状链表
5. $n≤100000 => O(nlogn) $=> 各种sort，set/map、heap、dijkstra+heap，二分
6. $n≤1000000 => O(n) $, 以及常数较小的 $O(nlogn)$ 算法 => hash、双指针扫描、kmp，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra
7. $n≤10000000 => O(n)$，双指针扫描、kmp
8. $n≤10^9 => O( \sqrt(n)) $，判断质数
9. $n≤10^{18} => O(logn)$，最大公约数

简单版本

2. $n <= 100 => O(n^3)$，floyd，dp
3. $n≤1000 => O(n^2)$，$O(n^2logn)$，dp，二分
4. $n≤100000 => O(nlogn) $=> 各种sort，树状数组、set/map、heap、dijkstra+heap、二分
5. $n≤1000000 => O(n) $, 以及常数较小的 $O(nlogn)$ 算法 => hash、双指针扫描、kmp 常数比较小的 $O(nlogn)$ 的做法：sort、heap、dijkstra
6. $n≤10000000 => O(n)$，双指针扫描、kmp
7. $n≤10^9 => O( \sqrt{n}) $，判断质数
8. $n≤10^{18} => O(logn)$，最大公约数

总的原则：最好是 1s 能够进行 $10^7$ 次运算。

$ 10^2 -> O( n^3) $ dp， floyd $ 10^3 -> O( n^2) $, dp， 二分, 枚举 $ 10^5 -> O( nlogn) $ 各种 sort 函数， set/map, heap, 二分 $ 10^6 -> O( n) $， 常数较小的 $O(n log n)$算法 -> hash， 双指针，kmp， $10^7 -> O(n)$，双指针， kmp 算法 $ 10^18 -> O( logn) $

比较一下 $O(n^2)$ 和 $O(nlogn)$ 的时间复杂度， 当n =100000 的话

• $O(n) = 10^5$
• $O(n^2) = 10^{10}$
• $O(nlogn ) = 20n = 2 \times 10^6$

在c++ 中分析递归的空间复杂度是不容易分析的，因为需要进行 $logn$ 级别的递归，这个栈空间是需要加到内存的申请中去的。 快排只有递归写法，所以空间复杂度上至少是$log n$的。

链表的时间和空间分析是比较简单的。

这个题目是可以好好看看，为什么不能使用快排但可以使用归并。因为前者不能写成非递归，后者可以写成非递归形式。

主定理一般用于算dfs 中的时间复杂度 对于dfs +剪枝的题目，一般是不好分析时间复杂度的，因为有的剪枝效率是很高的，那么久变得不可预测了。

树的时间度分析 使用的例题： leetcode 192

动态规划：

时间复杂度两种计算方法：

1. 状态 数量$O(n^2)$, 状态转移复杂度 $O(1)$ ， 所以总的是两者的相乘
2. 看循环的个数，两个for 循环叠加，那么就是 $O(N^2)$

dp 中会用到 memory 的思想 （记忆化搜索），有可能是递归的形式，实际上时间复杂度并不是dfs 的形式。

二分查找的时间复杂度是 $O(log n)$（常识）

字符串 leetcode 245 是比较nice 的题目，好好看看。 kmp 算法是 214 ，可以看看

单调队列 （这个对于两个例题是需要再看看）

丑数，时间复杂度最优的是O(n)

hash 表专题

hash表的最坏时间复杂度不用考虑，一般考虑均摊时间复杂度（$O(1)$）就可以。

149 这个题目是比较困难的，可以看看的哦

实现

1. two sum

hash 表含义是存储之前的数字。hash 表的增删改查时间复杂度都是 $O( 1)$。下面的程序总的时间复杂度是 $O(n)$，空间是 $O(n)$

2. repeated DNA sequences

unorderedc_map<string, int> 使用 string.substr() 得到子串，然后将子串放到 hash 表中，如果 count()大于2，那么这个就是最后的结果。

3. design hashmap

定义常量表示大数组的时候，应该多加几个数字，防止边界情况，并且尽量使用质数。

1
2

int N =20011 ;

对待冲突是有两种方法：拉链法和开放寻址法。前者加一个链表，后者是发生冲突的时候，向着周围的空间进行寻找。？ 空间大小和原数据大小的关系？查找一下。

使用到了 迭代器 概念，这个题目是比较难的。

design hashmap， 这个题目特别好。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class MyHashMap {
public:
    /** Initialize your data structure here. */
    // 实现自己的hashmap
    // 关键在于处理 冲突，有两种方式，链表法 和开放寻址法； 这里实现的时候，使用链表法
    //
    int N =20011;
    
    vector<list<pair<int, int>>> h;
    
    MyHashMap() {
        h =vector<list<pair<int, int>>>(N);
        
    }
    // 快速的 find 一个key的位置, 首先是一个 list，然后是一个链表
    // 查找的时候，已经包含了处理链表的情况
    list<pair<int, int>> :: iterator find(int key)
    {
        int t =key %N;
        
        for(auto it =h[t].begin() ; it != h[t].end(); it ++)
        {
            if(it -> first ==key) return it;
        }
        return h[t].end();
    }
    
    // 这种pair 的结构是非常容易操作key,value 这样的数字
    /** value will always be non-negative. */
    void put(int key, int value) {
        auto it =find(key);
        int t =key %N;
        
        if(it ==h[t].end()) h[t].push_back({key, value});
        else it -> second= value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        auto it =find(key);
        
        int t =key %N;
        if( it ==h[t].end()) return -1;
        return it->second;
        
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        auto it =find(key);
        int t =key %N;
        if(it != h[t].end()) h[t].erase(it);
        
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

Subarray Sum Equals K

题解思路也是非常的惊奇。时间复杂度是 $O(1)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    // 前缀和 + hash的思路
    // hash 处理的是插入和查询的问题
    int subarraySum(vector<int>& nums, int k) {
        
        unordered_map<int, int> hash;
        
        int res =0;
        int sum =0;
        //hash[]
        
        hash[0] =1; // 因为后面用到的 sum ==k 这样的前缀和
        for(int i =0; i<nums.size() ;i++)
        {
            sum += nums[i];
            res += hash[sum -k];
            hash[sum] +=1;
            
        }
        return res;
        
    }
};

并查集常用的两种操作

1. 合并两个集合
2. 判断两个点是否在同一个集合中

有两种优化，路径压缩和按秩合并。前者优化之后时间复杂度变成 $O(log n)$ 后者进一步优化变成 $loglog n$。因为后者优化之后收益不大，所以一般使用前者。

leetcode题目

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    
    vector<int> p;
    
    int find(int x)
    {
        if( p[x] !=x) p[x] =find(p[x]);
        return p[x];
    }
    
    
    int findCircleNum(vector<vector<int>>& M) {
        
        int n= M.size();
        int res =n;
        
        // 初始化
        for(int i =0; i<n; i++) p.push_back(i);
        
        for(int i =0; i<n ; i++)
            for(int j  =0; j<i; j++)
            {
                if(M[i][j] ==0) continue;
                
                if(find(i) != find(j))
                {
                    // find(x) 函数是找x 的父节点
                    // find(i) 的父节点指向了 find(j)
                    p[find(i)] =find(j);
                    res -=1;
                }
            }
        
        return res;
    }
};

自己手写堆的话，可以实现以下四个功能：

1. 查找最大值 $O( 1) $
2. 插入一个数 $O (log n)$
3. 删除一个数 $ O(log n)$
4. 修改一个数 $O(log n)$

如果使用 c++ 中 LST 中 priority_queue 那么只能使用上面 1. 2. 3. 种功能，并且删除一个数，只能删除堆顶，而不是删除任意一个。默认是大根堆的实现。

** Top K Frequent Words**

小根堆有很多实现方式，C++ 中默认是大根堆，所以可以存储相反数。hash 表存储单词出现的次数。 heap 表示堆的单词。 在result 存储的时候，实际上最先出来的是最差的，所以是从后往前遍历。

pair 是双关键字比较大小，如果第一关键字不同，那么比较出来大小，如果第一关键字相同，那么比较第二关键字大小。题目中要求出现频率大且字典序小的在前面。如果使用 负数表示，那么就转换成了负数小（正数大）且字典序小的在前。所以使用大根堆比较好处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<queue>
// 注意 priorty_queue 是定义在 queue 里面的
using namespace std;
vector<string> topK_frequent(vector<string> arr, int k )
{
    typedef pair<int, string> PAIR;
    unordered_map<string ,int> hash;
    priority_queue<PAIR> heap;
    for(auto word: arr)
        hash[word] ++;
    for(auto item : hash)
    {
        PAIR t(-item.second, item.first);
        heap.push(t);
        if(heap.size() > k) heap.pop();
    }
    vector<string> res(k);
    for(int i =k-1; i>=0 ; i--)
    {
        res[i] =heap.top().second;
        heap.pop();
    }
    return res;
}

int main()
{
    vector<string> arr={"i", "love", "leetcode", "i", "love", "coding"};
    int k =2;
    vector<string> res =topK_frequent(arr, k);
    for(auto u: res)
        cout << u<< " ";
    cout <<endl;
    return 0;
}

在python 中默认是小根堆，也是(-val, key) 这样保持一致，如果是都小，那么排在前面。最后的结果是先弹出来的，那么就是出现频率最大，并且字母序在前面的那种。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        import collections, heapq
        has =collections.defaultdict(int)
        for word in words:
            has[word] +=1
        heap =[]
        for (key, val) in has.items():
            heapq.heappush(heap, (-val, key))
        res =[]
        while k:
            val, key = heapq.heappop(heap)
            res.append(key)
            k -=1
        return res
        

类似的题目

347. Top K Frequent Elements

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        typedef pair<int, int> PAIR;
        priority_queue<PAIR> heap;
        for(auto num : nums)
            hash[num] +=1;
        for(auto item : hash)
        {
            PAIR  t(-item.second, item.first);
            heap.push(t);
            if(heap.size() > k) heap.pop();
        }
        vector<int> res(k);
        for(int i =k -1; i >=0; i--)
        {
            res[i] =heap.top().second;
            heap.pop();
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution(object):
    """
    是出现频率最大的k 个数字，那么想到的是使用小根堆的思想，维护 k 大的小根堆
    """
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import collections, heapq
        has =collections.defaultdict(int)
        heap =[]
        for num in nums:
            has[num] +=1
        # 取反 这样保证是根据 次数进行选择，
        for (key, val) in has.items():
            heapq.heappush(heap, (-val, key))
        res =[]
        while k:
            _, key =heapq.heappop(heap)
            res.append(key)
            k -=1
        return res

LeetCode 295 动态维护有序序列 -> 手写平衡树

使用对顶堆的思想。找中位数是 $O(1)$， 插入操作是 $O(log n)$ 的。

模板课总结

排序算法（快排和归并排序）

二分（整数二分，浮点数二分）

学习方法：理解只有，多写 3-5遍。重复才是王道。

对于边界问题非常复杂的问题，建议大家背过模板，这样是比较nice的。 如果对于数据量很大的情况，建议使用 scanf() 进行读入，因为 cin 相对来说是比较慢的。 稳定性，两个相同的数字，如果再排序前后能够保持相对的顺序，那么就是稳定的。快排是不稳定的，归并排序是稳定的。快排中的数字变成 pair<num, index>类型，那么就可以成为稳定的排序。

（背诵一个固定的模板就行） 快排的思想： 分治。算法步骤：

1. 确定分界点， q[l], q[r], q[l(l +r) /2] 随机都是可以的
2. 调整区间， 使一侧是小于等于x，另外一侧是大于等于x 就是ok的
3. 递归处理左右两段

快排的平均时间复杂度是$n log_{2} n$， 最坏是 $O(n^2)$。

归并排序- 分治

1. 确定分界点，mid =(l +r) /2
2. 递归排序, left 和 right
3. 归并，合二为一

快排是先操作后递归，归并是先递归然后其他操作。时间复杂度是(平均和最坏) $O(nlog_2n)$，总共是有 $logn$ 层，然后每层计算是$O(n)$。归并排序相对于快排是需要一个额外的$O(n)$ 的空间去存储排序之后的结果。

if (l >= r) 如果没有数字或者只有一个数字的时候，做的操作. 在常用的模板中，因为使用了一个临时数组，所以是需要把结果拿回来，所以最后是需要一个循环进行操作的。

二分

二分的本质不是单调性（如果具有单调性，那么是可以二分，但如果没有单调性，也是有可能二分的）。二分的本质是边界，可以找到一个分界点，左边是满足这个条件，右边是不满足这个条件。这个时候就可以二分。每次二分的时候都保证答案是在这个区间内的。

整数二分 版本一：当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。 版本二：当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。 可以通过这个题目好好理解两者的区别。在排序数组中查找元素的第一个和最后一个位置

cpp 中list 封装是链表，vector 封装是数组。

该题目的讲解可以从这里找找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return vector<int>({-1, -1});
        vector<int> res;
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != target) return vector<int>({-1, -1});
        res.push_back(r);

        l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        res.push_back(r);
        return res;
    }
};

浮点数二分问题。浮点数不存在 +1，-1 操作，因为这个是可分的。但是存在精度问题，如果题目要求是 6位小数，那么边界值判断是使用 $1e-8$ 就可以保证。（要保证比要求的位数多两位，一般是没有问题的）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<iostream>

using namespace std;

int main()
{
    
    double x ;
    cin >>x;
    
    double l =0, r =0;
    while( r -l > 1e-8)
    {
        double mid =( l+r) /2;
        if(mid *mid >=x) r =mid;
        else l =mid;
    }
    printf("%lf\n", l);
    
    return 0;
}