数据结构与算法 学习笔记
概念
数据结构是计算机存储和组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
常见的数据结构
算法
概念
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
算法是一种解决特定问题的思路。
常见的算法
算法复杂度
我们采用时间复杂度和空间复杂度来计算
时间复杂度
T(n)=O(f(n))
空间复杂度
空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
比如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:T(n)=O(2n)，忽略系数即为O(n)
线性表
线性表（Linear List）就是数据排成像一条线一样的结构，数据只有前后两个方向
数组（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构
应用
数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（百度百科）
常见的链表包括：单链表、双向链表、循环链表
数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。
栈和队列都属于线性数据的逻辑存储结构
栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。
队列
队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。
散列表
散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要
给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。
存储原理
哈希函数
散列表在本质上也是一个数组 散列表的Key则是以字符串类型为主的通过hash函数把Key和数组下标进行转换
作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。
递归，去的过程叫”递”，回来的过程叫”归
递归三要素
递归结束条件
函数的功能
这个函数要干什么，打印，计算
函数的等价关系式
递归公式，一般是每次执行之间，或者与个数之间的逻辑关系
二分查找
二分查找（Binary Search）算法，也叫折半查找算法
有很多数据的逻辑关系并不是线性关系，在实际场景中，常常存在着一对多，甚至是多对多的情况。家谱
二叉树
二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点
二叉查找树
二叉查找树(binary search tree)，二叉查找树在二叉树的基础上增加了以下几个条件
如果左子树不为空，则左子树上所有节点的值均小于根节点的值
如果右子树不为空，则右子树上所有节点的值均大于根节点的值
左、右子树也都是二叉查找树
广度优先遍历（BFS，Breadth First Search）
也叫层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。
深度优先搜索（DFS Depth First Search）
深度优先搜索，从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝
试另外一种方向，直到最后走到终点。就像走迷宫一样，尽量往深处走。
二叉查找树的插入和查找时间复杂度为:O(logn)
极端情况下二叉查找树退化成链表，时间复杂度为O(n)，所以需要平衡二叉查找树。
红黑树
红黑树就是一种自平衡的二叉查找树
除了二叉查找树(BST)的特征外，还有以下特征：
每个节点要么是黑色，要么是红色
根节点是黑色
每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）
如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）
新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡
多路查找树
*多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素 * 。
B树（BalanceTree）是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一
次读取多个数据，减少硬盘操作次数
B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，它的自身特征是：
非叶子结点的子树指针与关键字个数相同
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
所有关键字都在叶子结点出现
为所有叶子结点增加一个链指针
典型应用
MySQL索引B+Tree
B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个
分支，即多叉）平衡查找树。 多叉平衡
B树的高度一般都是在2-4这个高度，树的高度直接影响IO读写的次数。
如果是三层树结构—支撑的数据可以达到20G，如果是四层树结构—支撑的数据可以达到几十T
B和B+的区别
B树和B+树的最大区别在于非叶子节点是否存储数据的问题。
二叉堆
二叉堆本质上是一种完全二叉树，它分为两个类型
大顶堆(最大堆)
最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值
小顶堆(最小堆)
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值
算法思维
贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望
导致结果是全局最好或最优的算法
贪婪算法：当下做局部最优判断，不能回退
经典问题
部分背包问题
适用场景
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值
最大。
分治算法
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n
个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原
问题的解。
关于分治和递归的区别
分治算法是一种处理问题的思想，递归是一种编程技巧
经典问题
字符串转大写
回溯算法
回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发
现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径
经典问题 N皇后问题
动态规划
动态规划(Dynamic Programming)，是一种分阶段求解的方法。
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）
的方式去解决。
动态规划中有三个重要概念：
最优子结构
边界
状态转移公式（递推方程）dp方程
经典问题 01 背包问题