数据结构与算法
一、数据结构
一组数据的存储结构
二、算法
操作一组数据的方法
三、二者关系
数据结构为算法服务，算法作用在特定的数据结构之上
四、常用数据结构
数组、链表、堆、栈、队列、二叉树、散列表、跳表、图、Trie树
五、常用算法
递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
六、图解
复杂度分析
一、什么是复杂度分析？
1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4.复杂度描述的是算法执行时间或占用空间与数据规模的增长关系
二、为什么要进行复杂度分析？
1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
三、如何进行复杂度分析？
1、大O表示法
1）来源
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
2）特点
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。
2、复杂度分析法则
1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
四、常用的复杂度级别
1、多项式阶
随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2)（平方阶）、O(n3)（立方阶）
2、非多项式阶
随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，O(2^n)（指数阶）、O(n!)（阶乘阶）
3、时间复杂度四大分类
1）最好情况时间复杂度：最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
2）最坏情况时间复杂度：最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。
3）平均情况时间复杂度：执行这段代码的时间复杂度， 也称加权平均时间复杂度或者期望时间复杂度。
4）均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。（特殊的平均时间复杂度）
数组（Array）
一、线性表
数据排成线一样的结构，线性表上的数据只有前后两个方向；链表、队列、栈等也是线性表结构
二、非线性表
数据之间不是简单的前后关系，比如二叉树、堆、图
三、特点
数组是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。
数组从0开始编号
查询效率较高，可根据下标随机访问；插入与删除效率较低，因为要保证内存数据的连续性，每次插入与删除基本都需要移动其它数据（操作数组最末尾数据不需要）
四、数组容器：ArrayList
ArrayList优势：封装数组操作细节，支持动态扩容，存储空间不够，自动扩容为1.5倍大小；创建ArrayList的时候指定数据大小，可节约扩容是的内存申请与数据搬移的性能损耗
ArrayList无法存储基本数据类型，当需要存储基本数据类型时，会将其转换成对应的包装类再进行存储
链表（Linked list）
一、缓存
提高数据读取性能的技术，常见的有CPU缓存、数据库缓存、浏览器缓存等
二、缓存淘汰策略
缓存占满时清除数据的优先顺序
1、先进先出策略FIFO（First In, Fist Out）
2、最少使用策略LFU（Least Frequently Used）
3、最近最少使用策略LRU（Least Recently Used）
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
三、特点
删除插入效率较高，不需要移动其它数据；查询效率较低，需要逐一遍历节点数据查找
常见链表结构：单链表、双向链表、循环链表
四、单链表
每个链表节点除了存储数据之外，还需要记录链表上下一个节点的地址，这个记录下个节点地址的指针叫做后继指针next；第一个节点叫做头结点，最后一个节点叫做尾节点，尾节点指针指向下一个空地址NULL
五、循环链表
特殊的单链表，与单链表的区别为尾节点不指向空地址Null，而是指向链表的头节点，从链尾到链头比较方便
六、双向链表
每个链表节点除了存储数据，还有记录前后节点地址的前继指针prev与后继指针next，最后一个节点的后继指针指向第一个节点的前继指针
与引用类似，都是存储所指对象的内存地址
赋值变量给指针，就是赋值变量的地址给指针，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量
存储同样数量的数据时，双向链接明显比单链表占用更多的空间。因其双指针支持双向遍历，所以查询、插入、删除等操作要比单链表高效。
栈（Stack）
一、特点
“操作受限”的线性表，只允许在一端插入和删除数据
具有先进后出、后进先出的特性
用数组实现的栈叫做顺序栈，用链表实现的栈叫做链式栈
二、时间复杂度
不管是基于数组还是链表的栈，入栈push()、**出栈pop()**的时间复杂度都为O(1)，动态扩容的顺序栈使用均摊时间复杂度分析方法之后，其时间复杂度也为O(1)
三、栈帧
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”；栈用来存储函数调用的临时变量，临时变量被称为栈帧；当函数调用开始进入“栈”中时，栈帧依次入栈，当函数调用完成时，栈帧依次出栈
队列（Queue）
一、特点
具有先进先出、后进后出的特性
操作受限的线性表结构
只支持两个基本操作：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。
用数组实现的叫做顺序队列，用链表实现的叫做链式队列
队列拥有两个指针：一个head指针指向队头，一个tail指针指向队尾
数据入队与出队的时间复杂度都为O(1)，当队尾无法插入新数据且队列数据未满发生数据搬移时，使用均摊时间复杂度分析方法之后，入队操作时间复杂度也为O(1)
二、循环队列
对头与队尾相连，形成闭环
循环队列优点：可以解决数据搬移问题
循环队列缺点：代码实现较复杂，关键要确认好队空和队满的判定条件
队满时，（队尾下标+1)%队列长度=对头下标，(tail+1)%n=head
队满时，循环队列会浪费一个数组的存储空间
三、阻塞队列
在队列基础上增加了阻塞操作
如果队列为空，从队头取数据会被阻塞，无法取到数据；如果队列满了，从队尾插入数据会被阻塞，无法插入数据
阻塞队列 可以定义为生产者-消费者模型
四、并发队列
在多线程情况下，会有多个线程同时操作队列，存在线程安全问题
线程安全的队列叫做并发队列
最简单的实现方法是在enqueue()、dequeue()方法上加锁。同一时刻仅允许一个存或者取操作
递归（Recursion）
一、什么是递归？
1、递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
2、方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
3、基本上，所有的递归问题都可以用递推公式来表示，比如
f(n) = f(n-1) + 1;
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);
4、本身借助栈实现
二、递归的优缺点
1.优点：代码的表达力很强，写起来简洁。
2.缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。
三、使用递归解决问题需满足的条件
1、一个问题可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。
2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3、存在递归终止条件
四、递归理解
递归关键为：1、递推公式 2、终止条件
只要遇到递归，就把它抽象为一个递推公式，不用想每层的调用关系也不要去分解递推的步骤，一切从简。
五、递归常见问题及解决方案
1.堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。
2.重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。
六、如何将递归改写为非递归代码？
笼统的讲，所有的递归代码都可以改写为迭代循环的非递归写法。
如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。
排序（Sort）
一、排序算法
1、怎么衡量排序算法的执行效率？
1.最好情况、最坏情况、平均情况时间复杂度
2.时间复杂度的系数、常数 、低阶
3.比较次数和交换（或移动）次数
2、排序算法的内存消耗
通过空间复杂度来衡量
原地排序算法：特指空间复杂度为O(1)的排序算法
3、排序算法的稳定性
稳定性：如果待排序的序列中存在值相等的元素，排序过后，值相等元素之间原有的先后顺序不变
符合稳定性的排序算法叫做稳定的排序算法，不符合稳定性的排序算法叫做不稳定的排序算法
二、冒泡排序（Bubble Sort）
1、如何排序？
只操作相邻的两个数据，每次冒泡操作笔记相邻两个元素，根据大小关系判断是否交换位置。一次冒泡至少会让一个元素移动到它应该在的位置，重复n次，就完成n个数据的排序
2、冒泡排序归类
冒泡排序是原地排序算法，冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)
冒泡排序是稳定的排序算法，当有相邻的两个元素大小相等的时候，相同大小的数据在排序前后不会改变顺序
3、时间复杂度
冒泡排序最好情况时间复杂度为O(n)，要排序的数据已经是有序的了只需要进行一次冒泡操作；最坏情况时间复杂度为O(n2)，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作；所以冒泡排序的复杂度需要用平均时间复杂度来恒定
冒泡排序包含两个操作原子，比较和交换。数组逆序度确定，交换次数确定，所以复杂度主要看比较操作，比较操作的复杂度上限是O(n2)，所以平均情况下的时间复杂度就是O(n2)。
4、有序度
有序度：数组中具有有序关系的元素对的个数，两个元素为一对
eg:（2，4，3，1）这组数据有序度为2，(2,4)和(2,3)这两对
完全有序的数组的有序度叫做满有序度，n*(n-1)/2
eg:（2，4，3，1）这组数据满有序度为4*(4-1)/2=6
逆序度与有序度相反，默认从小到大为有序
逆序度=满有序度-有序度，排序的过程就是一种增加有序度，减少逆序度，最后达到满有序度完成排序的过程
三、插入排序（Insertion Sort）
1、如何排序
插入数据时遍历数组，找到数据应该插入的位置将其插入；插入数据依旧能保持数据有序
插入排序将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
插入排序也包含两种操作，一种是元素的比较，一种是元素的移动
移动次数等于逆序度
2、插入排序归类
插入排序是原地排序算法，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)
插入排序是稳定的排序算法，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变
3、时间复杂度
最好是时间复杂度为O(n)，要排序的数据已经是有序的，并不需要搬移任何数据，每次只需要比较一个数据就能确定插入的位置；最坏情况时间复杂度为O(n2)，如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据。
在数组中插入一个数据的平均时间复杂度是O(n)，所以插入排序平均时间复杂度为O(n2)。
四、选择排序（Selection Sort）
1、如何排序
将数据分为两个区间，已排序区间和未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
2、选择排序归类
选择排序是原地排序算法，空间复杂度是O(1)
选择排序是不稳定的排序算法，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
3、时间复杂度
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。初始已排序区间数据未0，数据为满有序度时依旧会将未排序区间最小数据放入已排序区间