数据结构与算法

2020-02-07 约 1900 字预计阅读 4 分钟收录于算法

数组、链表、跳表

数组：查找快，插入慢

vector<int> a;              //声明一个int型向量a
vector<int> a(10);         //声明一个初始大小为10的向量
vector<int> a(10, 1);      //声明一个初始大小为10且初始值都为1的向量

链表：插入快，查找慢
跳表：为了补足链表查找慢的缺陷而设计，以空间换时间，在链表的不同位置添加索引，通过索引来访问具体元素。比如可以每隔两个元素添加一个索引，则访问时间减半，若再在索引之上添加索引，构成第二级索引则时间再次减半，以此类推，最后链表访问的时间复杂度为logn，这样既保证了查找的速度，也保证了插入删除的效率，当然插入和删除的时间复杂度不是之前的O(1)，而是变为O(logn)，这是因为当进行插入删除时，索引也要随之更新一遍

由以上跳表的思想可知，再进行算法优化时，首先考虑优化的目的是什么，若是想让算法更快，则考虑以空间换取时间；同理可以时间换空间

栈、队列、双端队列、优先队列

栈：先进后出。对于最近相关性问题可考虑栈来实现，如括号匹配问题
队列：先进先出。对于先来后到类问题可考虑队列

查询为O(n)，添加删除为O(1)

双端队列deque，更为灵活，两端均可插入和删除
优先队列priority_queue，插入O(1),取出O(logn)，按优先级进行取操作，底层用堆或二叉搜索树或treap来实现
C++中的优先队列为大根堆

map、set、哈希表

哈希表:空间换时间 O(1) c++中哈希表为unordered_map和unordered_set map:键值对映射
遍历元素：

map<int, int> mp;
for(auto m:mp) {
    cout << m.first << m.second;
}
或
// for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
//     cout << it->first;
// }

set:集合:元素唯一

树、二叉树、二叉搜索树

树与图的区别：树中无环
二叉搜索树：左子树上所有节点都小于根节点，右子树上所有节点都大于根节点(注意是左右子树而不是左右节点)
在求解树相关问题时一般用递归进行解决，若用遍历算法的话要借助栈和队列，先序和后序用栈，层次用队列。其中先序遍历比较好写，故在写后续遍历时可借助先序遍历来实现，即先实现根-右-左的遍历，再逆置即可得到左-右-根的后序

Trie树

Trie树，也叫字典树、前缀树
优点：是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题，最大限度地减少无谓的字符串比较，查询效率比哈希表高
缺点：空间消耗大

基本性质：

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

递归、分治、回溯

递归： 自身调用自身，一般是用于分治和回溯的手段
构成递归的三要素：

终止条件
处理当前层逻辑
处理下层逻辑(2、3步可颠倒)

分治： 将问题划分为多个子问题进行处理，通常利用递归进行处理
例题：归并排序、求逆序对
回溯： 相当于遍历穷举的递归形式
在每一次的递归中，根据上一层传下来的状态，在当前层遍历所有可能情况，对每一种情况再分别递归到下一层
在当前层遍历所有可能情况时，可根据题意设置条件进行剪枝(剔除不合题意的解)；在循环中每当遍历一种情况后，在遍历后一种情况前要将状态回溯为上一层的状态

回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少搜索空间，而这种减少不是一个一个解的减少，而是对搜索空间进行大规模剪枝，从而使得实际搜索空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。参考

动态规划

本质：用分治的思想进行递推，与分治的主要区别在于动态规划往往需要求一个最优解 (即常常说的需要具备最优子结构)
DP三部曲：定义子问题，定义状态数组，和状态转移方程
方式：一般为两种

自底向上：也称为递推，因为时从数组开始递推到最后
自顶向下：也称为记忆化递归，因为递归是从顶向下的，在递归中记忆已经计算过的值避免重复计算

DFS、BFS

DFS：一般用递归的方法实现，或借助栈来实现
BFS：一般借助队列来实现

最短路径：从一个节点出发，求距离它的最短路径问题

树的BFS：单源最短路径
图的BFS：单源最短路径、多源最短路径

对于图的BFS需要判断节点是否已经被访问过，若必要的话可以另外设置一个visited数组
对于图的多源BFS中的源应该是无差别的

贪心算法

每次只找最优，来保证全局最优
一般用于最优化问题，如最小生成树、哈夫曼编码等，而工程应用一般用动态规划，贪心是找不到最优解的
与动态规划的区别：贪心只对当前子问题找最优解，不能回退；动规会保存之前的历史结果，根据当前状态状态进行选择，可回退

查找

二分查找

前提：元素有序
延伸：数组中有一个旋转点的也可以二分查找如[4,5,6,7,0,1,2]

目录