结构

数组

排序

知识

总结

时间复杂度

稳定性

重要稳定算法：冒泡、插入、归并、桶

重要不稳定算法：选择、快排、堆

也就是说一个序列中的相同值，它排序后，它的相同值的顺序不会改变即稳定

稳定性时间空间

稳定性和时间空间对比

1. 时间复杂度暂时2022-02没有低于O（N*logN）
2. 归并排序额外空间变成O(1),但算法困难，且不再稳定（归并排序 内部缓存法），不如用堆排序？
3. 原地归并排序时间复杂度变为O（N^2），增加算法难度，虽然空间O(1)不如用插入
4. 01 stable sort 快排可以保证稳定性，但是算法复杂，空间变为O（N），不如直接用归并
5. 以上三种算法性能三选二，没有三个都好的（稳定、时间O（N*logN）、空间O(1)）
6. 奇偶分开，要求相对奇数和偶数次序不变，空间复杂度O(1)，时间复杂度O（N），时间复杂度说不会直接问怎么做（01 stable sort ）
7. 实际工程排序分开排序如数组长度小于60插入（或归并）常数低，大于60快排变量低（利用各自的优势）
8. 考虑稳定性

其他

插入排序

升序，从左至右小则交换，插入前方局部有序，且都有序

选择排序

循环选择无序部分最小值放到队首，再取n-1最值放队首，直到结束(遍历，找最小值，与数组0位置交换，再找次小，再放1，直到最后)

计数排序

如年龄列表，第一次遍历统计个数，第二次遍历还原数组（根据下标索引，分区还原），时间复杂度O（n）

奇数排序（桶排序）

先根据个位数字放10个桶，倒出还原（从右往左，词频–，保证先入桶先出，保证排序稳定），再根据十位，倒出还原，直到最高位

归并排序

两个数组分别有序，再统一拷贝到一个数组（三个while模式）

冒泡排序

右边比左边大则交换，循环

题目

二分排序

二分查找

找大于等于某个数的最左侧index

局部最小

极限的概念，二分一边单调增，一边单调减，中间存在极限

数值整数次方

二分幂、快速幂，累乘

奇数排序

奇偶分开

计数排序思想，统计奇数，分片，遍历，奇数一片，偶数另一片。

归并排序

小和问题

左边小的数的和，在归并过程中，求左边小的个数和，等价于右边大的个数和，故当合并时，先拷贝的（左边比右边小）的产生1个数，累加后为结果

逆序对问题

左边的数比右边大，则两个数构成逆序对，在归并过程中当出现小于则打印

查找两个数组的相同字符

方法

方法1：对A中的数组进行排序，采取同样的排序方法对B中的数组进行排序

1. 从A，B中各自取出a，b进行比较
2. 如果a>b,那么从B中取出下一个数据b进行比较
3. 如果a<b,那么从A中取出下一个数据a进行比较
4. 如果a=b,那么找到一个，继续

方法2：hash

1. 对A中的m个数据装入到hash表
2. 对B中的n个数据一次去hash表中查询，如果找到那么就是相同元素

海量数据

升级：如果数据特别大，内存无法装下。 两个大文件，查找相同字符串

一、hash，分治法：

1. 采用hash算法对A文件进行hash成a个小文件
2. 采取同样的hash算法对B文件进行hash成b个小文件
3. 比较小文件对<a1,b1>………因为hash的问题，所以相同的字符串肯定在同个文件对里面。
4. 统计小文件对，可以继续采用hash，对a1的每一字符串建立hash表，遍历b1的字符串看是否在之前构建的hash表里面（和上面一样）

一般来说，如果内存可以存放，可以构造hash表，进行查找。如果内存无法加载，那么可以通过hash把大文件分成多个小文件，从而进行比较。

二、位图+布隆过滤器

注

hash算法在海量数据中的运用：

​ 单机处理大数据的问题也和mapreduce一样，分而治之，把海量数据切分成若干个小份进行处理。

1. 分而治之

   采用hash进行取模进行等价映射，将巨大的文件进行等价分割（符合一定规律的数据会被划分到同一个文件），划分成若干个小文件再进行处理。

2. 利用hashmap进行内存统计

   利用hashMap对小文件里面的数据进行统计

3. 排序

快速排序

荷兰国旗问题

数组分区，小于等于一个数左边，大于则右边（快排1.0）

小于左边，数字中间，大于右边（快排2.0）

（快排3.0从数组中找随机数进行分区迭代）

二维数组排序

知识

二维数组按行和按列遍历的效率

按行遍历的效率大概是是按列遍历的0.5倍    在c语言中，数组在内存中是按行存储的，按行遍历时可以由指向数组第一个数的指针一直向后遍历，由于二维数组的内存地址是连续的，当前行的尾与下一行的头相邻，所以可以直接到下一行

我们眼中的二维数组：

内存中的二维数组：

按行遍历比按列遍历的效率高体现在这些方面：

   1. CPU高速缓存：在计算机系统中，CPU高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。（百度百科解释）。 2. 缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的，几乎都是同行不同列的，而如果内循环以列的方式进行遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。随着数组元素越来越多，按列读取速度也会越来越慢。

可以用以下代码自行测试：

 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

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;
int main()
{
	const int MAX_ROW = 2000;
	const int MAX_COL = 2000;
	int(*a)[MAX_COL] = new int[MAX_ROW][MAX_COL];
	clock_t start, finish;

	//先行后列
	start = clock();
	for (int i = 0; i<MAX_ROW; i++)
	for (int j = 0; j<MAX_COL; j++)
		a[i][j] = 1;
	finish = clock();
	//totaltime=(double)()/CLOCKS_PER_SEC;
	cout << "先行后列遍历时间为：" << finish - start << "ms" << endl;
	//先列后行
	start = clock();
	for (int i = 0; i<MAX_COL; i++)
	for (int j = 0; j<MAX_ROW; j++)
		a[j][i] = 1;
	finish = clock();
	//totaltime=(double)()/CLOCKS_PER_SEC;
	cout << "先列后行遍历时间为：" << finish - start << "ms" << endl;

	return 0;
}

题目

有序二维数组查找

增序，从左下角起，目标大则右移，目标小则上移

异或

题目

数组中有一个数不一样

循环异或，最后的结果即为这个数

数组中有两个数不一样

循环异或，最后的结果即为这两个数异或，获取两个数二进制最低位，异或结果取反+1再与源结果相与，提起最小为1，两个数二进制某一位不同，则用此位为1其他位为0的数区分源数组，获取其中一个数，再将异或和与其异或得到另一个数。

字符串

搜索

知识

KMP 算法

空间换时间，匹配字符串切分，寻找最大公共子字符串，用匹配长度减去最大公共，为位数。主要就是优化匹配串中存在局部相同的部分的移动，时间： O(m+n)

BM算法

从右侧对比，不相等为坏，相等为好，字符串长度-好为位移，移动不相等部分最大值，即为求出的位移

Sunday算法

左侧对比，不匹配，看源串下一位是否在匹配串，在则移动匹配串从右向左位数+1.不存在则移动长度+1

回文

题目

最长回文串

输入无序材料串，用HashSet，第一次入，第二次出，统计个数，注意中间可以有最小

最长回文串2

输入有序材料串，中心扩展法：循环中心，两边扩展，记录最大,也要记录。动态规划：类似中心扩展，扩展相等 dp[i][j] = dp[i+1][j-1] + 2，不等为前后+一位的最大值，结果位dp[0][n-1]

验证回文串

双指针，非为字母则++，否则对比，前后。

其他

题目

替换空格

使用StringBuilder，如果是空格则append其他，如果不是空格，则append自己，str.replace()先搜索，再创建新数组速度收敛为3n，所有查找替换则为5n

字符串数组最长公共前缀序列

调用Arrays.sort()方法，将第一个字符串和最后一个字符串对比获取最长公共前缀序列

括号深度

左括号++即可

字符串转int

判断符号，按位取char-’0‘的int结果为位，结果*10+位，加上符号即可

链表

第k个节点

题目

链表中倒数第k个节点

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点也就是正数第(L-K+1)个节点

删除链表的倒数第N个节点

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点也就是正数第(L-K+1)个节点，k-1==k-1.next.next

两条链表

题目

合并两个排序的链表

递归，next非空，a小，merge（a.next,b）,b小，merge（a,b.next）,while+if else也可以，类似归并排序三个while，由于链表，其中一个为空，判断赋值一次即可

打印两个有序链表的公共部分

小于移动，相等打印共同移动

两条链表是否相交

判断是否有环，若无环，长链先走，相等时一起next，判断最后节点是否一致，一致则相交，不一致则不相交；

有环判断入环节点是否一致，一致相交，类似无环，终点为入环节点；若入环不一致，双方一致next，其中一个节点走回自己之前若和另外一个节点相同则相交，遇不到则不相交

其他

知识

解题方法论

1. 笔试，空间不用太在乎，主要为了时间复杂度
2. 面试，时间复杂度放第一位，但空间复杂度也要求最省

重要技巧

1. 额外数据结构（哈希表）
2. 快慢指针

题目

翻转链表

遍历，存next，next赋值位pre（初始null），now 赋值给pre，存的next复制给now

递归让this=change（this）

回文单链表

笔试：右边放到栈中，遍历另一半省空间，需要使用快慢指针，快指针两步，慢指针一步，快指针结束，慢指针中间，即可压栈

面试：同样取到中点，将后半翻转，双向对比空间O（1）、时间O（2*N）

单链表左边小，中间，右边打分区

笔试：放到数组（Node[]）中快排一轮，再构造链表

面试：设置三个区的头尾共6条链表，遍历分开放，当节点超过一个以后，head.next=tail,tail=newNode，最后串起来就好，注意最后连起来是空的部分。空间O（1）、时间O（N）

复制含有随机指针节点的链表

笔试：第一遍，将链表value拷贝挂到HashMap<Node,Node>中。第二遍，查map设置索引。空间O（1）、时间O（2*N）

面试：第一遍，将每个节点复制加在被复制的节点和下个节点之间，第二遍，复制随机指针(new.rand=pre.rand.next)，第三遍，两个两个处理分成两条链

判断链表中是否有环

笔试：将链表加入HashSet，执行next，当next在HashSet中出现第二次时，就存在环，且为环的头节点，否则不存在环。

面试：快慢指针，快指针走两步，慢指针走一步，当快慢相遇时，快指针回到链表头部，快慢指针都走一步，最后相遇则为环的头节点

栈

其他

题目

两个栈实现队列

入正常入一个栈，出时先全部压入另一个，弹出，再压回来，类似汉诺塔思想

判断栈的弹出序列

按照入栈压入，当和出栈顶相等时，出栈（入了再出），不相等则继续压栈直到个数，根据栈是否为空或出数组是否走到最后

树

遍历

知识

遍历序列

每个节点会走三次如1 2 3的树，遍历序列为1，2，2，2，1，3，3，3，1；

递归遍历

调整子树和打印的顺序，进行递归遍历

题目

先序遍历

先序遍历（深度优先）

弹出打印，先右再左入栈（如果有子节点）

二叉树序列化和反序列化

序列化：先序遍历：null用特殊符号代替（“#”），数字之间用特殊符号分割（“_”）

反序列化：分隔符切分为数组，建头节点，递归先左后右建树，遇到特殊符号给null

中序遍历

中序遍历

next有left就进栈，弹出打印，若有右树，对右树判断left…

判断是否搜索二叉树

中序遍历，都是升序

• 递归
  • 记录上一个值，空值返回true，判断左，和上一个值比：降序return，升序更新上一个值，判断右，出现降序return，否则继续
  • 无脑办法，中序放入list，判断递增
• 非递归
  • 记录上一个值，弹出时判断增序，降序return，升序更新上一个值

动态规划：左右树最大h值、h最小值;左右是，高度差，左小右大判断

（微软）纸条对折，凹折痕和凸折痕个数

中序遍历，头节点凹，之后子节点左凹右凸

递归动态循环次数：左，打印，右

后序遍历

后序遍历

弹出放入另一个栈，先左再右入栈（如果有子节点），弹出打印另一个栈

层序遍历

宽度优先（层序优先）

头节点放入队列，弹出打印，放左右，周而复始

求最大宽度

笔试：宽度优先遍历，初始化一个HashMap记录节点和层的映射，初始化头节点为一层，当前层节点个数0，最大值为最小；宽度优先放入map，和队列，弹出时判断层是否变化，变化了计算层节点个数，注意当前层节点个数重置为1，因为若层无节点意味着不会不相等，即层数不会+1

面试：记录当前层最后一个节点初始化为head，下一层最后一个节点初始化为null，当前层个数为0，最大值为最小；弹出打印，判断left!=null?下一层最后一个节点=当前进栈节点=left； right!=null？下一层最后一个节点=当前进栈节点=right；弹出，当前层个数+1，判断是否等于当前层最后一个节点，若是，更新max，当前层最后一个节点=下一层最后一个节点下一层最后一个节点=null，当前层个数归0，若不是只+1（和ifelse无关，都会+1），放入左右，周而复始

判断是否完全二叉树

层序遍历，记是否遇到孩子不双全节点为false，放头节点到队列，放左右，弹出打印，判断1、2条件，成立继续，否则返回false

• 情况分析
  • 任意节点，有右无左false
  • 1成立，遇到了第一个左右子叶不全，后续节点均为子节点

递归套路

是否满二叉树

求最大深度，和节点个数；2^最大深度-1=节点个数（1«最大深度-1==节点个数）

取左右树信息，高度和节点个数，最后判断满足上面条件

树的高度，左右子树组大+1

是否平衡二叉树（二叉树题目套路）

动态规划：取左右树信息，左右树平衡，左h-右h小于等于1；处理当前逻辑和返回结果

树的高度，左右子树组大+1

两个节点最低公共祖先

回溯法：使用Hashmap存节点的父节点，head父节点head，递归放入左右子树；创建hashSet，cur=o1，如果cur！=map.getCur？set添加cur，更新cur（往上窜）

set1加head，判断s2在不在set中，再往上窜，在则返回，不在更新cur（往上窜）

核心思想，生成父指针，放入一个向头的路径，另一个节点向上查找回溯，若相遇则碰撞

递归动态规划：null，o1，o2返回head，（情况1，先遇到即为结果，）左右子树递归，都非空返回头，（情况2，一边一个）一个非空返回不空的，都空返回空

• 情况分析
  • o1是o2祖先，或o2是o1祖先
  • o1、o2分开，不互为祖先

找一个节点的后继节点，O(N)->O(k)（有父指针）

• 情况分析
  • 有右树，右树左节点；
  • 无右树，是否par.left，是则找到，不是继续向上窜；parent为null返回parent（最右借点）

堆

排序

知识

大分堆加入

队尾放元素，若小于父节点则交换（i-1）/2

大分堆堆弹出（堆顶）

尾部放到首部（size–；拷贝）；和子孩子比，换小的，递归直到叶子节点（2xi+1，2xi-1）

特点

完全二叉树，插入和计算（上浮下沉）

优先队列使用的堆

题目

队列前k部分有序，怎么排序最好

将有序部分放入堆，取堆首放入数组，将无序数放堆首，直到无序耗尽，在取堆首放入数组，直到堆空，时间复杂度O（nlogk）

给二叉树堆排序

从最下边三个数（1棵树）排序，再排倒数第二层，直到到堆顶（略快于尾部或首部添加）-

图

总结

知识

存储方式

1. 邻接表

   1 2 3

   A：B，C B： C:

2. 邻接矩阵

   1 2 3

   1 1 1 1 1 1 1 1 1

3. 其他

   1. 特殊的图，但不能表示所有的图

      1	5 2 2 4 2 1

   2. 二维数组

      1 2 3 4

      [ [3,0,2], [2,0,2] ]

技巧

记住模板，将特殊形式转化为模板存储结构

模板

遍历

宽度优先

知识

1. 利用队列实现（使用set避免死循环）
2. 从源节点开始依次按照宽度进队列，然后弹出
3. 每弹出一个点，把该节点所有没有进过队列的临界点放入队列
4. 直到队列变空

广度优先

知识

1. 利用栈实现（set避免死循环）
2. 从源节点开始把节点按深度放入栈，然后弹出
3. 每弹出一个节点，把该节点下一个没有进过栈的邻接点放入栈
4. 直到栈变空

题目

拓扑排序（编译顺序，避免死循环）

找入度为0的点，找到后将入度为0的点及其出度删除，循环找入度为0的点（队列+map）

最小生成树

题目（无向有权图）

KrusKal算法（类并查集，判断图是否有环）

加入最小的边，检测图是否形成环，若有环，则不加（从最小的边开始，维护n个集合，当入节点和出节点在同一个集合则生成环，否则合并集合（单独的加入集合））

Prim算法

与出发点无关，将点加入Set（第一次出现），将当前点连通的边加入优先队列（小根堆），从堆中取出最小的边，若其指向的点是新出现的点（set没有），则边添加至结果集合，并将其边添加至堆中（会将重复的边添加到堆中，但是不会影响结果，因为重复的边添加后，对应的点也是再set中注册过的，故后面出堆的时候会舍弃）

若存在多个森林问题（两个图之间不连通，则需要对全部的node进行遍历，返回多个图的最小生成树）

单元最短路径算法

题目

Dijkstra算法（没有权值为负数的边，需要指定出发点）

设置map，记录node到出发点的距离，头节点放入map，设置set记录节点是否用过，根据set和map获取一个距离最小的节点（可以直接取head节点），且没有在set中注册过的点，当这个节点不为空，循环，遍历当前节点的链接节点，若map中无则计算距离，否则将计算距离和map中比较取小的，遍历完节点后，set中注册当前最小值节点，更新最小值节点，直到最小值为空（所有节点都在set中注册过）

堆可以优化：入堆值，不需要改值，系统的好，若入堆值仍要改变，系统会全局扫描开销较大

//TODO

A星算法

//TODO

其他

题目

判断图是否存在环（类并查集）

n个节点，各自作为set。遍历所有的边，当入点和出点不在同一个集合，则合并两个集合（单独的加入集合）并继续，若存在同一个集合则存在环

集合

并查集

知识

定义

并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（LCA）等。

方法

• makeSets 初始化，将所有节点单独设置set
• isSameSet 判断是否为同一个set
• find 递归查询最高父节点
• union 合并

路径压缩

每递归查询父节点时，直接将最高父节点替换当前的父节点，提高查询效率

其他数据结构

算法

递归

时间复杂度

知识

Master公式

T(N) = a*T(N/b) + O(N^d)

动态规划

题目

青蛙跳1或2，n阶方法个数

斐波那契数列，找规律

青蛙1-n，n阶方法个数

动态规划，错位相减。1 « –number;//2^(number-1)

小知识

取中点

l+r-l»1，防溢出

取一个数二进制最低位为1的数

x&（~x+1）

2^n-1

1«n-1