数据结构基本介绍
1、基本数据结构
1、数组、字符串 / Array & String
优点：
构建一个数组非常简单
能让我们在 O(1) 的时间里根据数组的下标 (index) 查询到某个元素
缺点：
构建时必须分配一段连续的空间
查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间
删除和添加某个元素时, 同样需要耗费 O(n) 的时间
例如：
leetcode 242.有效的字母异位词
2、链表 / Linked-list
单链表：链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
双链表：与单链表不同的是，双链表的每个结点中都含有两个引用字段。
利用快慢指针（有时候需要用到三个指针）
构建一个虚假的链表头
例如：
1）两个排序链表，进行整合
2）将链表的奇偶数按原定顺序分离，生成前半部分为奇数，后半部分为偶数的链表
如何训练技巧：
1）在纸上画出节点的关系
例如：
leetcode 25.K 个一组翻转链表
3、栈 / Stack
特点：后进先出（LIFO）
算法基本思想
可以用一个单链表来实现
只关心上一次的操作
处理完上一次的操作后，能在 O(1) 时间内查找到更前一次的操作
例如：
leetcode 739.每日温度
4、队列 / Queue
特点：先进先出（FIFO）
常用的场景：
1）广度优先搜索
5、双端队列 / Deque
基本实现：可以用一个双链表
队列的头尾两端能在 O(1) 的时间内进行数据的查看、添加和删除
常用的场景：
1）实现一个长度动态变化的窗口或者连续区间
例如：
leetcode 239.滑动窗口最大值
6、树 / Tree
树的共性，结构直观
通过树的问题来考察 递归算法 掌握的熟练程度
面试中常考的树的形状有：
1）普通二叉树
2）平衡二叉树
3）完全二叉树
4）二叉搜索树
5）四叉树
6）多叉树
特殊的树：红黑树、自平衡二叉搜索树
考察点：
1）树的遍历
前序（树的搜索、创建一颗新的树）、中序（二叉搜索树）、后序（需要知道树的左右信息时）
例如：
leetcode 230.二叉搜索树中第K小的元素
2、高级数据结构
1、优先队列 / Priority Queue
与普通队列的区别：
1）保证每次取出的元素是队列中优先级最高的
2）优先级别可自定义
最常用的场景：
1）从杂乱无章的数据中按照一定的顺序（或者优先级）筛选数据
本质：
二叉堆的结构，对在英文里叫 Binary Heap
利用一个数组结构来实现完全二叉树
特点（牢记）：
1）数组里的第一个元素 array[0] 拥有最高的优先级
2）给定一个下标 i，那么对于元素 array[i] 而言
父节点 对应的元素下标是 (i-1)/2
左侧节点 对应的元素下标是 2*i + 1
右侧节点 对应的元素下标是 2*i + 2
3）数据中的每个元素的优先级都必须要高于它两侧子节点
其基本操作为以下两个：
1）向上筛选（sift up / bubble up）
2）向下筛选（sift down / bubble down）
另外一个最重要的时间复杂度：
优先队列的初始化
例如:
leetcode 347.前 K 个高频元素
思路：
如何定义优先级别，以及优先队列中元素的数据结构
2、图 / Graph
最基本知识点如下：
1）阶、度
2）树、森林、环
3）有向图、无向图、完全有向图、完全无向图
4）连通图、连通分量
图的存储和表达方式：邻接矩阵、邻接链表
围绕图的算法也是各种各样：
1）图的遍历：深度优先、广度优先
2）环的检测：有向图、无向图
3）拓扑排序
4）最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall
5）连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
6）图的着色、旅行商问题等
必须数量掌握的知识：
1）图的存储与表达方式：邻接矩阵、邻接链表
2）图的变量：深度优先、广度优先
3）二部图的检测（Bipartite）、树的检测、环的检测包括有向图、无向图
4）拓扑排序
5）联合-查找算法（Union-Find）
6）最短路径：Dijkstra、Bellman-Ford
例如：
leetcode 785.判断二分图
3、前缀树 / Trie
也称为字典树
这种数据结构被广泛地运用在字典查找当中
什么是字典查找?
例如:给定一系列构成字典的字符串，要求在字典当中找出所有以"ABC"开头的字符串
方法一：暴力搜索法
时间复杂度：O(M*N)
方法二：前缀树
时间复杂度：O(M) // M 表示单词里最长的单词个数
经典应用：
1）搜索框输入搜索文字、会罗列以搜索词开头的相关搜索
2）汉字拼音输入法
重要性质：
1）每个节点至少包含两个基本的属性
2）children: 数组或者集合，罗列出每个分支当中包含的所有字符
3）isEnd：布尔值，表示该节点是否为某个字符串的结尾
4）根节点是空的
5）除了根节点，其他所有节点都可能是单词的结尾，叶子节点一定都是单词的结尾
最基本的操作：
创建方法：
遍历一遍输入的字符串，对每个字符串的字符进行遍历
从前缀树的根节点开始，将每个字符加入到节点的 children 字符集当中
如果字符集已经包含了这个字符，跳过
如果当前字符是字符串的最后一个，把当前节点的 isEnd 标记为真
搜索方法：
从前缀树的根节点出发，逐个匹配输入的前缀字符
如果遇到了，继续往下一层搜索
如果没遇到，立即返回
例题：
leetcode 212.单词搜索II
4、线段树 / Segment Tree
先从一个例题出发
假设我们有一个数组 array[0 ... n-1]，里面有 n 个元素，现在我们要经常对这个数组做两件事:
1. 更新数组元素的数值
2. 求数组任意一段区间里元素的总和(或者平均值)
方法一：遍历一遍数组
时间复杂度：O(n)
方法二：线段树
时间复杂度: O(logn)
什么是线段树？
种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和
例如：
数组是[1,3,5,7,9,11]
例如：
leetcode 315.计算右侧小于当前元素的个数
5、树状数组 / Fenwick Tree / Binary Indexed Tree
也被称为 Binary Indexed Tree
先从一个例题出发
假设我们有一个数组 array[0 ... n-1]，里面有 n 个元素，现在我们要经常对这个数组做两件事:
1.更新数组元素的数值
2.求数组前 k 个元素的总和(或者平均值)
方法一：线段树
时间复杂度: O(logn)
方法二：树状数组
时间复杂度: Ol(logn)
重要的基本特征
1）利用数组来表示多叉树的结构，和优先队列有些类似
2）优先队列是用数组来表示完全二叉树，而树状数组是多叉树
3）树状数组的第一个元素是空节点
4）如果节点 tree[y] 是 tree[x] 的父节点，那么需要满足 y=x-(x & (-x))
拓展练习
leetcode 308.维区域和检索-可变
求一个动态变化的二维矩阵里，任意子矩阵里的数的总和
总结：
优先队列：常见面试考点，实现过程比较繁琐。在解决面试中的问题时，实行"拿来主义"即可
图：被广泛运用的数据结构，如大数据问题都得运用图论
1）在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示
2）在地图上，要求解从起始点到目的地，如何行驶会更快捷，需要运用图论里的最短路径算法，
前缀树：出现在面试的难题中，要求能熟练地书写它的实现以及运用
线段树和树状数组：应用场合比较明确
如果要求在一幅图片当中修改像素的颜色，求解任意矩形区间的灰度平均值，则需要采用二维的线段树
