数据结构包括：线性结构和非线性结构
-
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
-
线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的（存储地址）
-
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
-
常见的线性结构有：数组、队列、链表和栈
- 非线性结构包括：二维数组、多维数组、广义表、树结构、图结构
编写的五子棋程序中，有存盘退出和续上盘的功能
分析问题
因为左侧二维数组中存放了很多的默认值0，因此记录了很多没有意义的数据-->稀疏数组
当一个数组中大部分元素为0，或者为同一个值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法
- 记录数组一共有几行几列，有多少个值
- 把具有不同值的元素的行列及值信息记录在一个小规模的数组中，从而缩小程序的规模
稀疏数组举例说明
二维数组转稀疏数组
- 遍历原始的二维数组，得到有效数据的个数sum
- 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
- 将二维数组的有效数据存入到稀疏数组
稀疏数组转二维数组
- 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
- 在读取稀疏数据后几行的数据，并赋值给二维数组即可
银行排队的案例
-
队列是一个有序列表，可以使用数组或者是链表来实现
-
队列遵循先进先出的原则。即：先存入队列的数据，要先取出；后存入队列的数据后取出。
-
使用数组模拟队列的示意图
- 队列本身是有序列表。若使用数组来实现队列存储数据，则队列数组声明如上图所示，其中MaxSize是该队列的最大容量
- 因为队列的输入、输出是分别从起始和末尾来处理，因此需要两个变量front和rear分别记录队列的起始位置和末尾位置。front会随着数据的输出而改变，rear会随着数据的输入而改变。front和rear初始设置为-1。
- 当有数据入队列时，需要考虑如下
- 当前队列是否已满。rear==MaxSize-1，如果满了则无法存数据
- rear末尾下标指示后移rear++，将数据存入rear所指的数组中
- 当有数据出队列时，需要考虑如下
- 当前队列是否空。front==rear，如果队列为空则无数据可出
- front起始位置后移front++，返回当前front位置的数据
问题分析
- 使用数组模拟队列，当队列状态满了之后，数组就不能再继续使用了。
- 可以改成一个环状的队列，取模%
对数组模拟队列的优化，充分利用数组，因此将数组看作是一个环形的（通过取模的方式来实现）。
分析说明
- front指向当前队列头元素，初始位置为0
- rear指向队列尾元素的下一个位置，初始位置为0
- 当(rear+1)%maxSize=front时 表示队列满了
- 当rear=front时表示队列为空
- 当队列增加元素时rear=(rear+1)%maxSize
- 当元素从队列里取出时front=(front+1)%maxSize
链表是有顺序的列表，它在内存中存储如下：
- 链表是以节点的方式来存储，是链式存储。
- 每个节点包含一个data域，一个next域
- 链表的各个节点不一定是连续存储的
- 链表分带头节点和不带头节点的的链表，根据实际的需求来确定
使用带头节点的单向链表实现英雄排行榜管理。完成对英雄人物的增删改查操作
直接添加到链表尾部逻辑分析
-
链表头节点用来做为牵引头，不移动
-
当节点的next属性为空时表示链表最后
-
添加节点时，从头节点获取第一个有效数据，开始遍历链表找到最后一个节点，将待添加的节点添加到最后
按顺序添加节点分析
-
从头节点开始获取有效节点（next）开始进行遍历链表
-
判断是否到达链表的最后，如果是则可以直接添加，否则进行下一步
-
判断当前节点的下一个节点的值是否大于要添加的节点的值，是跳出循环进行下一步，否继续遍历
-
判断当前节点的下一个节点的值是否等于要添加的节点的值，是跳出循环进行下一步，同时标识有相同节点，否继续遍历
-
判断是否是相同的节点，如果是相同的节点，输出提示不进行添加，如果不是相同节点进行下一步
-
将待添加节点的next指向当前节点的next，再将当前节点的next指向待添加节点
删除节点逻辑分析
-
如果到最后节点了，说明不存在要删除的节点
-
找到需要删除节点的前一个节点temp
-
将temp.next=temp.next.next
更新节点逻辑分析
- 如果是空节点，则更新操作不能完成，否则进行下一步
- 判断是否是要更新的节点，是则更新，否继续循环查找
求单链表有效节点的个数
- 遍历链表，进行加一，直到最后一个节点
查找单链表中倒数第k个节点
- 判断k是否有效，即k不能小于等于0，也不能大于有效节点个数
- 倒数第k个就是正数第（length-k）个
- for循环遍历到第（length-k）个节点，就是要查找的倒数第k个节点
单链表反转
- 创建一个新的头节点revertHead，
- 对要反转的链表进行遍历，遍历时将当前遍历的节点取出，放到新的链表的最前面
- 将原来链表的头节点的next指向revertHead的next
合并两个有序链表
- 其实就是对链表的节点进行有序添加
- next指向当前节点的下一个节点
- pre指向当前节点的前一个节点
单向链表的缺点分析
- 单项链表的查找方向只能是一个方向，而双向链表可以向前或者向后查找
- 单项链表不能自我删除，需要靠辅助节点，而双向链表可以自我删除
双向链表的遍历
遍历的方式和单链表一样，区别是双向链表可以向前查找，也可以向后查找
添加节点到双向链表的最后
- 先找到尾节点temp
- 让temp.next=newNode，同时让newNode.pre=temp
双向链表的修改
修改和单向链表一样
双向链表的删除
- 找到要删除的节点temp
- 执行temp.pre.next=temp.next，同时让temp.next.pre=temp.pre
如下图所示是一个节点和多个节点时单向环形链表的状态。
当只有一个节点时，该节点的next域指向自己。
Josephu（约瑟夫）问题
Josephu问题为:设编号为 1，2，... n 的 n 个人围坐一圈，约定编号为 k(1<=k<=n)的人从 1 开始报数，数 到 m 的那个人出圈，它的下一位又从 1 开始报数，数到 m 的那个人又出圈，依次类推，直到所有人出列为止，由 此产生一个出圈编号的序列。
提示:用一个不带头结点的循环链表来处理 Josephu 问题:先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。
需要一个first变量，用来代表环的起始。
- 环的大小应该不小于1，否则无意义
- 一个指向当前末尾的节点变量currentNode，保证currentNode.next=first
- 添加的节点temp
添加节点的操作步骤
-
创建一个节点temp
-
判断节点编号是不是1即第一个节点，如果是就让first变量指向它，同时让currentNode也指向它，然后设置currentNode.next=first；
-
如果不是一号节点，让currentNode.next=temp；然后让currentNode指向temp，然后设置currentNode.next=first；
出圈的操作步骤
-
创建一个辅助节点helperNode，该节点初始指向队列的末尾节点。
-
根据startNo，同步的移动helperNode和first，此时helperNode的next指向first
-
然后再找到要出圈的节点delNode，根据计数的次数countNo。循环得到delNode的位置
-
让firstNode指向delNode.next，让helperNode.next指向first节点helperNode.next=first
计算表达式的值
计算机底层是如何运算得到结果的? 我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)
- 栈也称为stack
- 栈是一个先入后出的有序列表
- 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端称为栈顶，另一端为固定的一端称为栈底。
- 根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶；而删除元素则刚好相反，最后放入的元素最先被删除，最先放入的元素最后被删除
- 如下图所示
- 子程序的调用：在跳往子程序前，会先将当前程序的下个指令的地址存到栈中，直到子程序执行完后在将地址取出，以回到原来的程序中
- 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入了栈中
- 表达式的转换（中缀表达式转后缀表达式）与求值
- 二叉树的遍历
- 图的深度优先搜索法
- 用数组模拟栈的使用，由于栈是一种有序列表，所以可以使用数组的结构来存储栈的数据结构
- 实现思路如下：
- 定义top表示栈顶，初始值为-1
- 入栈操作，top++;stack[top]=value
- 出栈操作，int value=stack[top]; top--;
使用栈来实现综合计算器（此时只有正整数的加减乘除运算）。
输入一个表达式[7*2*2-5+1-5+3]计算结果。
思路分析：
前缀表达式又称波兰表达式。前缀表达式的运算符位于操作数之前。
举例： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算过程
从右至左扫描表达式，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对它们做响应的计算，并将结果入栈；重复这个过程直到表达式最左端，最后运算得出的值就是表达式的计算结果。
举例：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
- 从右至左扫描，将6、5、4、3压入栈中
- 遇到+运算符，因此弹出3和4，计算出3+4的值，得到7，再将7入栈
- 接下来是x运算符，因此弹出7和5，计算出7x5=35，将35入栈
- 最后是 - 运算符，计算出35-6的值，即29，由此得出最终结果
中缀表达式就是常见的运算表达式，如(3+4)×5-6。
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
举例： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
| 正常表达式 | 逆波兰表达式 |
|---|---|
| a+b | a b + |
| a+(b-c) | a b c - + |
| a+(b-c)*d | a b c – d * + |
| a+d*(b-c) | a d b c - * + |
| a=1+3 | a 1 3 + = |
后缀表达式计算过程
从左至右扫描表达式，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复这个过程直到表达式最右端，最后运算得出的值就是表达式的计算结果。
举例：(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入栈中
- 遇到运算符+，因此弹出3和4，计算出3+4的值，得到7，再将7入栈
- 将5入栈
- 接下来是 x 运算符，因此弹出5和7，计算7x5的值，得到35，将35入栈
- 将6入栈
- 接下来是 - 运算符，因此弹出35和6的值，计算35-6的值，得到29，由此得到最终结果。
逆波兰表达式就是计算后缀表达式的值，这里使用jdk提供的Stack栈数据结构
在逆波兰表达式实现计算器中可以发现后缀表达式实现起来比较方便，但是得到后缀表达式的结果手动实现比较难，尤其表达式很长的情况下。下面看下将中缀表达式转为后缀表达式的步骤。
注意：下面步骤中说的运算符是指加减乘除等运算符，左右括号()使用操作符表示，同时操作符没有优先级，只有运算符有优先级
- 初始化两个栈，运算符栈s1和中间结果存储的栈s2
- 从左至右扫描中缀表达式
- 遇到操作数时，将其压入到栈s2中
- 遇到运算符时，将其与s1栈顶符号的优先级比较
- 如果s1栈顶为空，或者栈顶运算符为左括号"("，则直接将此运算符入栈到s1
- 否则，若优先级比栈顶运算符高，也将此运算符入栈s1
- 否则，将s1栈顶的符号弹出并压入到s2中，再次转到4.1
- 遇到括号时
- 如果是左括号，则直接压入到s1栈中
- 如果是右括号，则依次弹出s1栈顶的符号，并压入到s2栈中，直到遇到左括号为止，此时将这一对括号丢弃
- 重复步骤2-5，直到表达式扫描结束
- 将s1中剩余的运算符依次弹出并压入s2
- 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
将中缀表达式“1+((2+3)*4)-5”转换为后缀表达式的过程如下：
| 扫描到的元素 | s2（栈底->栈顶） | s1（栈底->栈顶） | 说明 |
|---|---|---|---|
| 1 | 1 | 数字，直接入栈 | |
| + | 1 | + | 运算符，s1栈顶为空 |
| ( | 1 | + ( | 是左括号，直接入栈 |
| ( | 1 | + ( ( | 是左括号，直接入栈 |
| 2 | 1 2 | + ( ( | 数字，直接入栈 |
| + | 1 2 | + ( ( + | 运算符，此时s1栈顶是左括号，直接入栈 |
| 3 | 1 2 3 | + ( ( + | 数字，直接入栈 |
| ) | 1 2 3 + | + ( | 右括号，循环弹出s1： 弹出+号压入到s2，直到遇到(，丢弃这一对括号 |
| * | 1 2 3 + | + ( * | 运算符，此时s1栈顶是左括号，直接入栈 |
| 4 | 1 2 3 + 4 | + ( * | 数字，直接入栈 |
| ) | 1 2 3 + 4 * | + | 右括号，循环弹出s1： 弹出*号压入到s2，直到遇到(，丢弃这一对括号 |
| - | 1 2 3 + 4 * + | - | 减号，此时s1栈顶是+ ，减号的优先级不比加号高，将s1栈顶的符号弹出并压入到s2中，继续和s1栈顶比较，这个时候s1空了，那么减号直接入栈 |
| 5 | 1 2 3 + 4 * + 5 | - | 数字，直接入栈 |
| 表达式扫描结束 | 1 2 3 + 4 * + 5 - | 将s1中的弹出到s2 |
最后的结果：1 2 3 + 4 * + 5 -
注意：由于s2在实际操作中就是不断的添加元素，为了方便得到最后结果，在代码实现时可以使用List来代替
递归：recursion
简单说：递归就是方法本身调用自己。递归有助于编程者解决负责复杂的问题，同时可以让代码变得简洁。
方法区栈
- 一些数学问题：8皇后、汉诺塔、阶乘、迷宫问题、球和篮子问题（Google编程大赛）
- 一些算法中也会用到递归：快排、二分查找、归并排序、分治算法
- 将用栈解决的问题使用递归解决代码比较简洁
- 在执行递归方法时，会将新的方法压入到方法区栈中
- 方法中的局部变量是独立的，不会相互影响
- 如果方法中使用的是引用类型变量，就会共享该引用类型的数据
- 递归必须向退出递归的条件逼近，否则进入无限循环就会出现StackOverflowError。
八皇后问题，是一个古老而著名的问题，是回溯算法的经典案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法(92)
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列，判断是否冲突，如果冲突就放在第三列依次把所有列放完，直到找到一个合适的
- 第三个皇后放在第三行，还是第一列、第二列...直到第八个皇后也能放在一个不冲突的位置，算是找到了一个正确的解
- 当得到一个正确的解时，在栈回退到上一个栈时，就会开始回溯。即将第一个皇后放在第一列的所有正确解找到
- 然后将第一个皇后放在第一行第二列，后面继续循环执行1、2、3、4步骤，直到第一个皇后放到第一行第八列走完，得到所有的结果。
说明
一个8X8的棋盘，理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法用一个一维数组解决问题。比如：arr[8] ={0 , 4, 7, 5, 2, 6, 1, 3}表示的含义是arr的下标表示第几个皇后即行，arr[index]的值表示列。
两个点在同一个斜线
点(x1,y1)和点(x2,y2)如果abs(x1-x2)=abs(y1-y2)那么两个点在一个斜线上
排序也称排序算法，排序是将一组数据，依指定的顺序进行排列的过程。
- 内部排序：指将需要处理的数据都加载到内存中进行排序。
- 外部排序：当数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
常见的算法分类
-
事后统计法
这种方法存在两个问题：一是想要对设计的算法的运行性能进行评价，需要实际运行该程序；二是所得到的时间依赖于计算机的硬件、软件等环境因素，这种方式，要在同一台计算机的相同状态下进行，才能比较哪个算法速度更快
-
事前估计的方法
通过分析某个算法的时间复杂度来判断哪个算法更优。
基本介绍
一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。
举例说明
- 忽略常数项
结论: 2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略 3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略
- 忽略低次项
结论: 2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10 n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20
- 忽略系数
结论: 随着n值变大，5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5和3可以忽略。 而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键
-
一般情况下算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O( f(n) )，称O( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
-
T(n) 不同，但时间复杂度可能相同。 如:T(n)=n2+7n+6 与 T(n)=3n2+2n+2 它们的 T(n) 不同，但时间复杂 度相同，都为 O(n2**)**。
-
计算时间复杂度的方法:
- 用常数 1 代替运行时间中的所有加法常数 T(n)=n2+7n+6 => T(n)=n2+7n+1
- 修改后的运行次数函数中，只保留最高阶项 T(n)=n2+7n+1 => T(n) = n2
- 去除最高阶项的系数 T(n) = n2 => T(n) = n2 => O(n2)
-
常数阶O(1)
-
对数阶O(log2n)
在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n) .
-
线性阶O(n)
-
线性对数阶O(nlog2n)
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
-
平方阶O(n^2)
-
立方阶O(n^3)
-
k 次方阶 O(n^k)
-
指数阶O(2^n)
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关
- 类似于时间复杂度，一个算法的空间复杂度(SpaceComplexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。
- 空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的 临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例 如快速排序和归并排序算法**,** 基数排序就属于这种情况
- 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品 (redis, memcache)和算法(基数排序)本质就是用空间换时间.
从小到大排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一轮结束后，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
对于n个数字，当n-1个位置都确定时，那么这个待排序数组就是排序完整的。由于每一轮排序可以确定一个元素，所以n个数需要n-1轮，每轮确定冒出一个最值
优化：如果在某趟排序寻找过程中，没有发生一次交换，说明当前序列已经顺序了，可以提前结束冒泡排序。
选择排序也属于内部排序算法，是从待排序的数据中，按指定的规则选出某一元素，再按照规定排序方式交换位置后达到排序的目的。
从小到大排序
- 第一轮循环从arr[0]-arr[n-1]中选取最小值，与arr[0]比较进行交换
- 第二轮循环从arr[1]-arr[n-1]中选取最小值，与arr[1]比较进行交换
- 第i轮循环从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]比较进行交换
- 第n-1次循环从arr[n-2]-arr[n-1]中选取最小值，与arr[n-2]比较进行交换
也是每轮循环得到一个最值，所以也是需要n-1次循环
插入排序属于内部排序算法，对待排序的元素以插入的方式找寻该元素适当位置，以达到排序的目的。
把n个待排序的元素看成一个有序列表和一个无序列表，开始时有序表只包含一个元素，无序表包含n-1个元素，排序过程从无序表中取出第一个元素，使其与有序列表进行比较，为其找到合适的位置，使之成为新的有序表。
当较小的数在待排序数组的后面时，数组移动的次数明显增多，对效率有影响。
如数组arr={2,3,4,5,6,1}，当待插入数是1时，整个过程是这样的。
几乎所有的数组都进行了移动，比较影响性能
希尔排序是希尔在1959年提出的一种排序算法，希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
希尔排序是基于插入排序实现，因此在给待排序元素设置位置时，有交换和移动两种实现方式。性能上还是有差别的。
快速排序是对冒泡排序的一种改进。基本思想是一趟排序将待排序的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小。然后在按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。以此达到整个数据变成有序序列。
- 先从待排序队列中取出一个数作为基准数
- 分区过程，将比这个数大的放在它的右边，比这个数小的放在它的左边
- 在对左右区间重复以上步骤，直到各区间只有一个数
快速排序的过程可以拆解为：挖坑填数+分治。
以一个数组为例：
取中间一个数作为基数，l为数组起始左边下标，r为数组起始右边下标，emptyIndex为当前坑位的下标，pivot为当前选取的基数变量。
l=0，r=9，emptyIndex=4，pivot=arr[emptyIndex]=60;
由于已经将arr[emptyIndex]的数保存到pivot变量了，可以认为该位置是个空坑，可以让其他数填充了；
此时l=0，从左边开始找大于pivot的数，发现当l=0时，arr[0]=72，大于pivot符合条件，将arr[0]挖出来填充到上一个坑arr[4]的位置上，即arr[4]=arr[0]，让emptyIndex=0；
此时r=9，从右边开始找小于等于pivot的数，发现当r=8时，arr[8]=48，小于pivot符合条件，将arr[8]挖出来填充到上一个坑arr[0]的位置上，即arr[0]=arr[8]，让emptyIndex=8；
此时l=0，从左边开始找大于pivot的数，发现当l=3时，arr[3]=88，大于pivot符合条件，将arr[3]挖出来填充到上一个坑arr[8]的位置上，即arr[8]=arr[3]，将emptyIndex=3；
此时r=8，从右边开始找小于等于pivot的数，发现当r=5时，arr[5]=42，小于pivot符合条件，将arr[5]挖出来填充到上一个坑arr[3]的位置上，即arr[3]=arr[5]，将emptyIndex=5；
此时l=3，从左边开始找大于pivot的数，发现当l=4时，arr[4]=72，大于pivot符合条件，将arr[4]挖出来填充到上一个坑arr[5]的位置上，即arr[5]=arr[4]，将emptyIndex=4；
此时r=5，从右边开始找小于等于pivot的数，发现当r=4时，等于了l，这个时候结束循环。将pivot设置到当前坑的位置上，即arr[emptyIndex]=pivot，最后数组的状态如下所示：可以发现60的左边的数都比60小，60右边的数都比60大。
注意事项：
- 在过程中要创建临时的l和r，不能使用实参left和right值，因为循环过程中会对下标进行移动
- 注意临界值等于的处理，会出现死循环
归并排序是利用归并的思想是实现的排序方法，该算法采用经典的分治策略。分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案合并在一起，即分而治之。
将上图中最后一次合并的过程图解如下：
- i，j分别指向两个子数组的起始位置
- 比较arr[i]和arr[j]，得到将arr[j]填充到temp数组中，将j++
- 重复上面的步骤，直到一个子数组末尾结束
- 将另外的一个数组中剩余的数依次填充到temp数组中
- 将temp数组中的数拷贝到arr数组中
- 基于排序属于分配式排序，又称桶子法或bin sort。它是通过键值的各个位的值，将要排序的元素分配至某些桶中，达到排序的作用
- 基数排序法属于稳定型的排序，基数排序法是效率高的稳定排序法
- 基数排序法是桶排序的扩展
- 基数排序是1887年赫尔曼 何乐礼发明的。
- 将所有待排序的数统一为同样的数位长度，数位短的数前面补零，即假如原数组为[10,2,213]，则可以看为[010,002,213]，同时创建一个二维数组的十个桶，每个桶大小是待排序数组的长度即bucket[10][a r r .length]，然后开始循环;
- 第一次循环按照数组中待排序的数的个位，将其放到对应的桶中直到数组循环完毕
- 将桶中的数组按顺序复制到待排序数组中
- 重复第二、三步
- 最后将待排序数组就是已经排序的数组
- 基数排序是对桶排序的扩展
- 基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成oom。因为要创建十个桶，每个桶大小是待排序数组的长度。即有 4size * 10 * arr.length
- 基数排序是稳定
- 这里对有负数的场景没有讨论
- 稳定排序：如果a原本在b前面，同时a=b，排序之后a仍然在b的前面
- 不稳定排序：如果a原本在b前面，同时a=b，排序之后a可能出现在b的后面
- 内排序：所有排序操作都在内存中外城
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
- 时间复杂度：一个算法执行所耗费的时间
- 空间复杂度：运行完一个程序所需内存的大小
- n：数据规模
- k：桶的个数
- In-place：不占用额外内存
- Out-place：占用额外内存
在Java中，常用的查找算法有四种：
- 顺序查找
- 二分查找
- 插值查找
- 斐波那契查找
线性查找就是遍历数列，查找是否有待查询元素
二分查找要求数列是有序的。
- 首先确定数列的中间下标mid=(left+right)/2
- 比较findVal和arr[mid]的值
- 如果findVal大于arr[mid]，则递归向右查找
- 如果findVal小于arr[mid]，则递归向左查找
- 如果findVal等于arr[mid]，则说明找到了值
- 如果找到了就返回，结束递归
- 如果递归到left>right也没有找到findVal，也需要结束递归，说明查无此元素
插值查找算法类似于二分查找，不同的是插值查找每次的mid是根据要查找的值计算得出，即可以理解为要查找的值参与了查找自己的过程，所以插值查找也叫做自适应查找。
由于要查找的值参与了计算mid的过程，因此在一定情况下可以减少二分查找递归的次数。
在二分查找时，mid的计算方法是mid=(left+right)/2
在插值查找时，mid的计算方法是mid = left + (right - left) * (findVal - arr[left]) / (arr[right - arr[left]]);
举例说明插值在1-100 的数列中查找10的过程。
使用上面提到的公式mid=0 + (99 - 0) * (10 - 1) / (100 - 1) =9
在数列arr中arr[9]就是等于10，此时只递归了一次
- 黄金分割点是值把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。比值是一个无理数，取其前三位数字的近似值是0.618。由于按照此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。
- 斐波那契数列{1,1,2,3,5,8,13,21,34,55}。发现斐波那契数列的两个相邻数的比例越来越接近黄金分割值。即该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
斐波那契查找原理与前两种相似，仅仅是改变了中间节点mid的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1，F代表斐波那契数列。
- 由于斐波那契数列F[k]=F[k-1] + F[k-2]的性质。例如当k=6时，那么F[k]=8、F[k-1]=5、F[k-2]=3。即长度为8的数列可以分为长度为5和长度为3的两个数列。
- 那么mid位置的计算low+F(k-1)-1
- 类似的，每一个子段也可以用相同的方式分割
- 但是顺序表的长度不一定刚好等于F[k]，所以需要将原来的顺序表长度n增加至F[k]。在扩充时增加的元素使用原数组最后值填充
- 循环进行区间分割，查找中间值
- 判断中间值和目标值的关系，确定更新策略
-
构建一个斐波那契队列
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] -
将待查找数列填充合适的长度
假设待查找数据队列如下：
[1, 2, 4, 6, 7, 9, 13, 16, 17, 21, 23, 25, 27, 31, 45, 56, 58, 61, 65, 67, 73, 75, 88, 93, 102]
这里共有25个元素，不等于斐波那契数列中任何F(n)，此时，策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前数组长度为25，斐波那契数列中大于25的最近元素为34。
-
填充后待查找数列如下
[1, 2, 4, 6, 7, 9, 13, 16, 17, 21, 23, 25, 27, 31, 45, 56, 58, 61, 65, 67, 73, 75, 88, 93, 102,102,102,102,102,102,102,102,102,102]
此时共34个元素
-
循环进行区间分割，查找中间值
这一个步骤与二分查找和插值查找相似，都是不断的缩小搜索区间，进而确定目标值的位置。每次分割中间位置的计算如下：mid=left + F(n-1) -1
此时数组被分割为左右两个区间，左边区间含有F(n-1)个元素
-
判断中间值和目标值的关系，确定更新策略
中间值和目标值有三种大小关系，分别对应三种处理方式：
- 相等，则查找成功，返回中间位置即可
- 中间值小于目标值，则说明目标值位于中间值到右边界之间（即右区间），右区间含有F(n-2)个元素，所以n应该更新为n=n-2
- 中间值大于目标值，这说明目标值位于左边界和中间值之间（即左区间），左区间含有F(n-1)个元素，所以n应更新为n=n-1
有一个公司，当有新员工报道时，要求将该员工的加入（id、姓名），当输入该员工ID时，输出该员工信息。不实用数据库，尽量节省内存，速度越快越好。
散列表也叫哈希表，是根据关键码值而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
数组存储方式分析
- 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
- 缺点：如果要检索某个具体的值，或者插入、删除元素会有整体移动，效率较低
链式存储方式分析
- 优点：在另一个角度对数组存储方式有优化（在插入、删除时不需要再有整体移动）
- 缺点：在进行检索具体值时，效率仍然低
树存储方式分析
能提高数据存储、读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。
- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点（没有子节点的节点）
- 节点的权（节点值）
- 路径（从root节点找到该节点的路线）
- 层
- 子树
- 树的高度（树的最大层）
- 森林（多棵子树构成森林）
树有很多种，每个节点最多只能有两个子节点的树，成为二叉树。二叉树分为左节点和右节点。
满二叉树
如果二叉树所有叶子节点都在最后一层，并且总节点总数=2^n-1，n为层数，则我们称为满二叉树。
完全二叉树
如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点从左边开始连续；倒数第二层的叶子节点从右边开始连续，则称为完全二叉树。
使用前序、中序、后序遍历二叉树：
- 前序遍历：先父节点，在左节点，最后右节点
- 中序遍历：先左节点，在父节点，最后右节点
- 后序遍历：先左节点，在右节点，最后父节点
总结：看父节点的位置，就确定是前序、中序、后序了。
前序遍历
- 先输出当前节点
- 判断当前节点有没有左节点，如果有则递归前序遍历左节点
- 判断当前节点有没有右节点，如果有则递归前序遍历右节点
前序查找
- 先判断当前的节点是否是要查找的节点，如果是查找结束
- 判断当前节点的左节点是否为null，进行下一步，如果不为null，递归进行前序查找
- 判断当前节点的右节点是否为null，进行下一步，如果不为null，递归进行前序查找
- 如果执行到了这里说明没有查找到节点
注意这里实现的场景
- 如果节点是叶子节点，直接删除该节点
- 如果节点不是叶子节点，则删除该子树
实现思路
由于当前的二叉树，只能由父节点找到子节点，不能通过子节点找到父节点。所以在做删除置空操作时，是判断当前节点的子节点是否是要删除的节点，如果是判断当前节点是否为待删除节点时，将无法进行删除操作。
- 先判断根节点是否为null，如果是直接返回，当前树是空树；如果非空，判断根节点是否是要删除节点
- 判断当前节点的左节点是否不为null，且是要删除的节点，如果是则删除当前节点的左节点结束
- 判断当前节点的右节点是否不为null，且是要删除的节点，如果是则删除当前节点的右节点结束
- 如果当前节点的左节点不为null，进行左节点递归删除
- 如果当前节点的右节点不为null，进行右节点递归删除
基本说明
从数据存储来看，数组存储和树的存储方式可以相互转换。即数组可以转换成树，树也可以转换成数组。
注意：二叉树的节点序号，从0开始，这样可以和数组下标保持一致。
顺序存储二叉树的特点
- 顺序存储二叉树只考虑完全二叉树
- 第n个元素的左子节点的下标为2*n+1
- 第n个元素的右子节点的下标为2*n+2
- 第n个元素的父节点为(n-1)/2，其中这个地方n>0，0号节点是跟节点，没有父节点
- n表示二叉树中第几个元素，n从0开始
一个数组arr{1,2,3,4,5,6,7}，以二叉树前序方式进行遍历。
堆排序会用到顺序存储二叉树
如上图所示二叉树，我们对其进行如下分析：
- 当对该二叉树进行中序遍历时得到的队列是：[8,3,10,1,14,6]
- 该二叉树的6，8，10，14四个节点存在没有使用的左右指针
- 如果我们想充分利用各个节点的左右指针，让各个节点可以标识出自己的前驱、后继节点，该如何处理
- 解决方案就是线索二叉树
遍历二叉树得到的遍历队列，一个节点的前一个节点，称为前驱节点；后一个节点称为后继节点。
- n个节点的二叉树中含有n+1个空指针域。计算方式：2*n - (n-1) ；一个节点两个指针所以一共有2n个指针，n个节点的连接需要使用n-1个，所以还剩2*n - (n-1)个空指针域。
- 这种加上了线索的队列称为线索链表，相应的二叉树称为线索二叉树。根据线索性质的不同线索二叉树可以分为前序线索二叉树、中序线索二叉树、后序线索二叉树
如下示例，进行中序化二叉树
-
上面二叉树中有六个节点，存在七个空指针域分别是 8号的左右节点、10号的左右节点、14号的左右节点和6号的右节点。
-
对这个进行中序遍历，结果是8 , 3 , 10 , 1 , 14 , 6，所以对应节点的前驱后继关系也就知道了
- 节点8没有前驱节点，后继节点是3
- 节点3的前驱节点是8，后继节点是10
- 节点10的前驱节点是3，后继节点是1
- ...
-
如果一个节点没有普通左右子树，那就让其左右指针指向对应的前驱 后继节点，结果如下图。这就是对二叉树进行线索化
当线索化二叉树后，node节点的left和right属性有如下情况：
- left指向的可能是左子树，也可能是前驱节点
- right指向的可能是右子树，也可能是后继节点
思路
-
将根节点赋值给一个临时变量
-
判断当前节点是否为空，从当前节点开始开始找左节点是前驱节点的节点，这个时候当前节点是第一个起始节点。且当前节点的左节点为null
-
判断当前节点的右节点是否为后继节点，如果是则可以一直输出（因为如果是后继节点，则是在线索化时的遍历顺序），一直到右节点不是后继节点。
-
取当前节点的右节点作为当前节点，然后继续从第二步开始
重点就是理解下线索化的过程中的一些特点。
- 如果一个节点的右节点是后继节点类型的，那就是遍历的顺序
- 堆是一种完全二叉树
- 堆有大顶堆和小顶堆
- 如果一个树的每个节点的值都大于或等于其左右孩子节点的值，则称这个树为大顶堆
- 如果一个树的每个节点的值都小于或等于其左右孩子节点的值，则称这个树为小顶堆
大顶堆举例说明
将一棵大顶堆的树，按照顺序编号从0开始可以得到一个arr的数组，则该数组有如下特点：
- arr[i]>=arr[2*i+1] 且arr[i]>=arr[2*i+2]
- i是数组下标，也是树的编号，从0开始
小顶堆举例说明
将一棵小顶堆的树，按照顺序编号从0开始可以得到一个arr的数组，则该数组有如下特点：
- arr[i]<=arr[2*i+1] 且arr[i]<=arr[2*i+2]
- i是数组下标，也是树的编号，从0开始
堆排序基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好平均时间复杂度均为O(nlogn)，它是不稳定排序。
- 一般升序采用大顶堆，降序采用小顶堆
堆排序基本思想
按照从小到大排序。
- 将待排序序列构成一个大顶堆对应的数组
- 此时整个序列的最大值就是堆顶的根节点
- 将其与末尾元素进行交换，此时末尾就是最大值了
- 重复第一步，如此反复执行，便能得到一个有序序列了。
有一个数组[4,6,8,5,9]，要求使用堆排序法，将数组升序排序。
步骤一：构造初始堆。将给定无序序列构造成一个大顶堆
- 将无序序列构造成树结构
- 从最后一个非叶子节点开始，从左至右，从下往上进行调整
- 找到第二个非叶子节点4，由于[4,9,8] 中9元素最大，4和9交换
- 这时，交换导致了子树[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6
此时，就将一个无序序列构造成了一个大顶堆
步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾交换，得到第二大元素。如此反复进行交换、重建、交换
- 将堆顶元素9和末尾元素4进行交换
- 重新调整结构，使其继续满足堆定义
- 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
- 后序过程，继续进行调整、交换如此反复进行，最终使得整个序列有序。
路径和路径长度
在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的通路，成为路径。
通路中分支的数目成为路径长度。
若规定根节点的层数为1，则从根节点到第L层节点的路径长度为L-1
如上图：
- A1到A2，A1到A3，A1到A2在到A4，A1到A2在到A5的连线都是路径
- 其中A1到A2，A1到A3的路径长路为1；A1到A2在到A4，A1到A2在到A5的路径长度为2
节点的权和带权路径长度
若将树中节点设置一个有着某种意义的数值，则称这个数值为该节点的权。
从根节点到某一节点之间的路径长度与该节点的权的乘积是该点的带权路径长度。
如上图：
A1节点的权为1，A2节点的权为2，A3节点的权为3，A4节点的权为4，A5节点的权为5。
则A2节点的带权路径长度为 2*(2-1)=2；A5节点的带权路径长度为5*(3-1)=15
树的带权路径长度
树的带权路径是所有叶子节点的带权路径长度之和。记为WPL（weight path length），权值越大的节点离根节点越近的二叉树才是最优二叉树。
给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。
赫夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近。
将给定一个数列{13,7,8,3,29,6,1}转成一个赫夫曼树。
步骤分析：
- 将数列的每个元素看成一个只有一个节点的二叉树的节点。对这个数列进行从小到大排序。
- 取出根节点权值最小的两个二叉树
- 将取出的两个二叉树组成一个新的二叉树，新的二叉树的权是两个二叉树权值的和
- 将新的二叉树放进数列，并对数列重新排序
- 重复上面的步骤，直到数列元素的个数还有一个，那么这一个节点就是赫夫曼树的根节点。
赫夫曼编码是一种程序算法，是赫夫曼树在电讯通信中的经典应用之一。赫夫曼编码广泛的使用于数据文件压缩，其压缩率通常在20%～90%之间。赫夫曼码是可变字长编码（VLC）的一种。是Huffman在1952年提出的一种编码方法，称为最佳编码。
在通讯领域中处理信息的方式有定长编码和变长编码。
对于如下字符，包括字符间的空格一共是40个字符。
i like like like java do you like a java
按照ascii编码格式，上面四十个字符编码后如下
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97
105对应的i，32对应的是空格，后面依次是对应的ascii编码。
当字符在计算机计算或者计算机网络传输时使用的是二进制，所以上面的ascii编码对应的二进制如下
01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001
这个时候二进制编码的总长度是359，包括二进制编码之间的空格
对于如下字符，包括字符间的空格一共是40个字符。
i like like like java do you like a java
对上面的字符出现的进行统计得到如下结果
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
d:1表示字符d出现了1次
y:1表示字符y出现了1次
a:5表示字符a出现了5次
:9表示空格出现了9次
按照各个字符出现的次数进行编码，原则是出现的次数越多，则编码越小，比如空格出现了9次，编码为0，其他以此类推。则可以得到如下编码对应规则：
0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d
按照上面这个各个字符规定的编码，则最开始的40个字符在传输或者计算时就是这样
对于变长编码存在一个问题，就是字符的编码可能是其他字符编码的前缀，这个时候在解析的时候就会出现歧义性。比如上面的第一个1在进行匹配的时候，是认为它是字符a，还是字符i或者字符e或者其他字符的前缀。
字符的编码都不可能是其他字符编码的前缀，符合这个要求的编码叫做前缀编码。
对于如下字符，包括字符间的空格一共是40个字符。
i like like like java do you like a java
还是一开始的40个字符，依然统计各个字符出现的次数
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
d:1表示字符d出现了1次
y:1表示字符y出现了1次
a:5表示字符a出现了5次
:9表示空格出现了9次
按照上面字符出现的次数构建一棵赫夫曼树，字符出现的次数作为权值。可以得到如下一棵赫夫曼树
根据这个赫夫曼树，给各个字符进行编码，规则如下向左的路径为0，向右的路径为1；则得到这个字符的编码规则如下：
o: 1000 u: 10010 d: 100110 y: 100111 i: 101
a : 110 k: 1110 e: 1111 j: 0000 v: 0001
l: 001 : 01
按照这个编码规则，同样在传输开始的字符串时，对应的编码就是如下这个样子:
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
得到的这个编码在按照编码规则解析时没有歧义，同时这个时候长度为133，既保证了数据的原始信息，又减少了数据长度。
原来长度时359，这个时候长度时133，压缩了(359-133)/359=62.9%
有一点需要注意的是，这个赫夫曼树根据排序方法的不同，可能树也不一样，这样对应的赫夫曼编码也不完全一样，但是wpl是一样的，都是最小的。可以保证生成的赫夫曼编码长度是一样的。
将给出的一段文本，比如i like like like java do you like a java，根据赫夫曼原理对其进行压缩处理，首先构造一棵赫夫曼树。
- 统计每个字符出现的次数得到一个map映射（字符和字符出现的次数）
- 将map中的每个元素看作一个树节点，其中字符代表数据，次数代表树的权重
- 将所有的树节点构造成一棵赫夫曼树
对构造的赫夫曼树进行遍历，按照向左遍历路径位0，向右遍历路径位1的规则。遍历所有的叶子节点，得到所有叶子节点的字符和路径的一个map映射，这个映射就是赫夫曼编码表。
使用得到的赫夫曼编码表对源数据进行编码。
- 对源数据进行遍历，得到每个字符对应的路径（二进制形式的字符串）
- 将每个字符编码后的路径串在一起，每8位做为一个字节，构造得到一个新的压缩后的字节数组数据
- 这里注意每8位做为一组时，最后一组的长度可能不够8个
二进制字符串转int时涉及到计算机的二进制的原码、反码、补码
数据的解压，就是将得到的压缩数据进行展开操作。
- 对得到的压缩后数据字节数据进行遍历，将每个字节转成一个二进制数据，注意最后一个需要补高位
- 将每个字节的二进制数据字符串在一起
- 按照展开的字符串，开始从编码表里找出对应的真实字节数据
- 得到真实数据的字节数组
- 读取文件的数据流得到字节数组数据
- 使用字节数据得到赫夫曼编码
- 使用赫夫曼编码对源文件的字节数组数据进行压缩
注意：
对文件进行压缩，由于压缩后的文件可以被传输，所以文件的编码表也要被放进压缩文件中。这样在解压时才知道解压的规则
简单的方式可以直接通过FileOutpustStream.writeObject()；先将压缩后的数据写入到文件，在将编码规则也写到文件
- 读取压缩文件得到压缩后的字节数组数据
- 先后两次进行readObject获取压缩后文件数据和编码表
- 然后根据编码表压缩的数据进行展开操作
- 如果要处理的数据文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化，比如视频、ppt等
- 赫夫曼编码时按照字节来处理的，因此可以处理所有的文件
- 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显
有一个数列{7,3,10,12,5,1,9}，要求能够高效的完成对数据的查询和添加
使用数组
数组未排序：
- 优点 可以直接在数组末尾添加新的数据，速度快
- 缺点 查找速度慢
数组已排序
- 优点 可以使用二分查找，查找速度快
- 缺点 为了保证数组有序，在新添加数据时，在找到合适位置时，后面的数据需要整体移动，速度慢
使用链表
不管链表是否有序，查找速度都慢，添加数据速度比数组快。
使用二叉排序树
二叉排序树又称BST（Binary Sort（Search）Tree），也是一种二叉树。对于二叉排序树而言，任何一个非叶子节点都不小于它的左子节点，同时也不大于它的右子节点。
比如针对前面的数列{7,3,10,12,5,1,9}，它对应的二叉排序树为：
创建二叉排序树
- 创建一个二叉排序树
- 将数列挨个添加到该树上，如果根节点为空，则该节点就是这棵树的根节点
- 如果待添加的节点的数值小于当前节点的值
- 如果当前节点的左节点为空，则待添加节点就是当前节点的左子节点
- 否则向左递归
- 如果待添加的节点的数值不小于当前节点
- 如果当前节点的右节点为空，则待添加节点就是当前节点的右子节点
- 否则向右递归
遍历二叉排序树
对二叉排序树进行中序遍历，就会得到一个有序的数组
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑：
- 删除叶子节点
- 删除只有一个子节点的节点
- 删除有两个子节点的节点
删除叶子节点
- 找到要删除的节点 targetNode
- 找到 targetNode的 父节点 parent
- 确定 targetNode是 parent的左子节点还是右子节点
- 如果是左子节点 parent.left=null
- 如果是右子节点 parent.right=null
删除只有一个子节点的节点
- 找到要删除的节点 targetNode
- 找到 targetNode的 父节点 parent
- 确定 targetNode是 parent的左子节点还是右子节点
- 确定 targetNode的子节点是左节点还是右节点
- targetNode的子节点是左子节点
- targetNode是 parent的左子节点parent.left=targetNode.left
- targetNode是 parent的右子节点parent.right=targetNode.left
- targetNode的子节点是右子节点
- targetNode是 parent的左子节点parent.left=targetNode.right
- targetNode是 parent的右子节点parent.right=targetNode.right
- targetNode的子节点是左子节点
删除有两个子节点的节点
- 找到要删除的节点 targetNode
- 找到 targetNode的 父节点 parent
- 从targetNode的右子树找到最小的节点
- 使用一个临时变量temp将最小的节点保存起来
- 删除该最小的节点
- 使用temp替换targetNode
需求
使用给定的数列{1,2,3,4,5,6}创建一棵BST树，并分析存在的问题
- 该二叉排序树左子树全部为空，更像是一个链表
- 该二叉排序树插入数据没有影响
- 查询速度明显降低（因为需要依次比较），不能发挥BST的优势，因为还要比较左子树，其查询速度比单链表还慢
- 解决方案：平衡二叉树
平衡二叉树又称AVL树（Self-balancing binary search tree），可以保证查询效率较高。
特点
- AVL树是一个空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡二叉树
- 实现平衡二叉树的算法有：红黑树、AVL树、替罪羊树、Treap树、伸展树
需求
使用给定的数列{4,3,6,5,7,8}创建出对应的平衡二叉树。
问题
当最后一个节点8添加到树上时，这个时候 rightHeight() - leftHeight() > 1，这个时候不在是一棵AVL树。
处理
- 当前节点为根节点
- 创建一个新的节点newNode，设置值为当前节点的值
- 把新节点的左子树设置成当前节点的左子树
- 把新节点的右子树设置成当前节点的右子树的左子树
- 把当前节点的值替换成当前节点的右节点的值
- 把当前节点右子树设置成右子树的右子树
- 把当前节点的左子树设置为新节点
结果
优化处理过程
上面的处理步骤理解起来是比较绕的，从结果上来看，其实很简单，就是以当前节点右节点的值创建一个新的节点tmp。这个过程需要注意返回新的根节点，同时注意处理的步骤必须先处理新节点的左右子节点
- 以当前节点右节点的值创建一个新的节点tmp。tmp = new Node(curNode.right.value)
- 让tmp的左节点指向当前节点，tmp的右节点指向当前节点右节点的右节点。tmp.left=curNode; tmp.right=curNode.right.right;
- 更新当前节点的右节点。 curNode.right=curNode.right.left;
需求
使用给定的数列{10,12,8,9,7,6}创建出对应的平衡二叉树。
问题
当最后一个节点6添加到树上时，这个时候 leftHeight() - rightHeight() > 1，这个时候不在是一棵AVL树。
处理
- 当前节点为根节点
- 创建一个新的节点newNode，设置值为当前节点的值
- 把新节点的右子树设置为当前节点的右子树
- 把新节点的左子树设置为当前节点左子树的右子树
- 把当前节点的值设置为左子节点的值
- 把当前节点的左子节点设置为左子节点的左子节点
- 把当前节点的右子树设置为新节点
结果
优化处理过程
上面的处理步骤理解起来是比较绕的，从结果上来看，其实很简单，就是以当前节点左节点的值创建一个新的节点tmp。这个过程需要注意返回新的根节点，同时注意处理的步骤必须先处理新节点的左右子节点
- 以当前节点右节点的值创建一个新的节点tmp。tmp = new Node(curNode.left.value)
- 让tmp的右节点指向当前节点，tmp的左节点指向当前节点左节点的左节点。tmp.right=curNode; tmp.left=curNode.left.left;
- 更新当前节点的右节点。 curNode.left=curNode.left.right;
在某些情况下进行单旋转（左旋转或者右旋转）就可以将非平衡二叉树转成平衡二叉树，但是在某些情况下不能完成平衡二叉树的转换。比如如下数列：
int arr[] = {10,11,7,6,8,9}
int arr[] = {2,1,6,5,7,3}
问题
当节点9添加到树结构时，满足右旋转的规则，这个时候执行上面的右旋转方案。得到右边的结果也不是一个平衡二叉树。
处理
- 当前节点为根节点
- 当符合右旋转条件时
- 如果当前节点的左子树的右子树高度大于它的左子树高度即途中节点7的右子树高度（2）大于7的左子树高度（1）
- 先对当前节点的左子树进行左旋转
- 然后在对当前节点进行右旋转
- 当前节点为根节点
- 当符合左旋转条件时
- 如果当前节点的右子树的左子树高度大于它的右子树高度
- 先对当前节点的右子树进行右旋转
- 然后在对当前节点进行左旋转
结果
二叉树的效率较高，但是也存在一些问题。当将二叉树加载到内存中使用时，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多（比如1亿）就会存在如下问题：
- 海量数据存在数据库或文件中在构建二叉树时，需要多次进行I/O操作。海量节点，构建二叉树时速度有影响
- 海量节点，也会造成二叉树的高度很大，会降低操作速度
在二叉树中，每个节点最多有两个子节点的数据项。如果允许每个节点可以有更多的数据项和更多的子节点就是多叉树。
简单的多叉树有2-3树，2-3-4树。多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。
下面的2-3树是一个二叉树
B树通过重新组织节点，降低树的高度，并且减少I/O读写次数来提升效率。
2-3树就是一棵B树
- 如图B树通过重新组织节点，降低了树的高度
- 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页（页的大小通常为4K），这样每个节点只需要一次I/O就可以完全载入
- 将树的度M设置的1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素，B（B+）树广泛应用于文件存储系统以及数据库系统中
- 2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）
- 二节点对应一个键值，要么没有子节点，要么有两个子节点
- 三节点对应两个键值，要么没有子节点，要么有三个字节点
- 2-3树是由二节点和三节点构成的树
将数列{16,24,12,32,14,26,34,10,8,28,38,20}构成2-3树。
构建规则：
- 2-3树的所有叶子节点都在同一层
- 二节点对应一个键值，要么没有子节点，要么有两个子节点
- 三节点对应两个键值，要么没有子节点，要么有三个字节点
- 当按照规则插入一个树到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面的三个条件
- 对于三节点的子树的值大小仍然遵守BST的规则
除了2-3树，还有2-3-4树也是一种B树。如图：
B-tree树即B树，B是balance 平衡的意思。有的地方B-tree也被翻译成B-树。
对于前面提到的2-3树和2-3-4树都是B树。在Mysql中经常听到某中类型的索引是基于B树或者B+树，如图：
对上图的说明：
- B树的阶：节点的最多字节点个树。比如2-3树的阶是3，2-3-4树的阶是4
- B树的搜索，从根节点开始，对节点内的关键字序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子节点；重复，直到所对应的儿子指针为空，或者已经是叶子节点
- 关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据
- 搜索有可能在非叶子节点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
B+树是B树的变体，也是一种多路搜索树。
对上图的说明：
- B+树的搜索与B树也基本相同，区别是B+树只有达到叶子节点才命中（B树可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找
- 所有关键字都出现在叶子节点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字（数据）恰好是有序的
- 不可能在非叶子节点命中
- 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层
- B+树更适合文件索引系统
- B树和B+树各有自己的合适应用场景
B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针。
对上图的说明：
- B*树定义了非叶子节点关键字个数至少为（2/3）*M，即块的最低使用率为2/3，而B+数的块的最低使用率为1/2
- 从第1个特点可以看出，B*树分配新节点的概率比B+树要低，空间使用率更高
线性表局限于一个直接前驱和一个直接后继；树也只能有一个父节点；所以当需要表示多对多的关系时，就用到了图。
图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个节点之间的连线称为边，节点也称为顶点。
- 顶点
- 边
- 路径
- 无向图
- 有向图
- 带权图
图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，就是一个n*n的矩阵。
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边是不存在的，会存在空间的浪费损失。
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。
- 添加维护图的顶点
- 添加顶点之间的关系-边
所谓图的遍历就是对图节点的访问。遍历图有两种访问策略：
- 深度优先遍历
- 广度优先遍历
深度优先遍历（Depth First Search）
- 从初始节点出发，初始访问的节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点出发，访问它的第一个邻接节点
- 这样的访问策略是优先往纵向挖掘深入
- 显然深度优先遍历是一个递归过程
- 访问初始节点v，并标记节点v为已访问
- 查找节点v的第一个邻接节点w
- 若w存在，则继续执行步骤4，如果w不存在则回到第一步，从v的下一个节点继续
- 若w未被访问，则对w进行深度优先遍历（将w看作另一个v，然后进行步骤1、2、3...）
- 若w被访问过，则查找节点v的下一个节点转到步骤3
应用到这个图就是：
前提
- 坐标（x,y）的值如果为0 则表示x节点到y节点不存在路径
- 坐标（x,y）的值如果为1 则表示x节点到y节点存在路径
步骤
- 访问第一个起始节点，即输出节点A，获取起始节点的第一个邻接节点得到节点B
- 节点B，还没有被访问过，访问该节点，将该节点置为新的起始节点
- 获取节点B的第一个邻接节点，得到节点A，由于节点A访问过，获取节点B的下一个邻接节点得到节点C
- 节点C，还没有被访问过，访问该节点，将该节点置为新的启示节点
- 获取节点C的第一个邻接节点，得到节点A，由于节点A访问过，获取节点C的下一个邻接节点得到节点B，由于节点B也被访问过，继续获取，节点C没有下一个邻接节点了，从节点B的下一个节点继续
- 获取节点B的下一个邻接节点，得到节点D
- 节点D，还没有被访问过，访问该节点，将该节点置为新的起始节点
- 获取节点D的第一个邻接节点节点，得到节点B，由于节点B访问过，继续获取，节点D没有下一个邻接节点了，从节点B的下一个节点继续
- 获取节点B的下一个邻接节点，得到节点E
- 节点E，还没有被访问过，访问该节点，将该节点置为新的起始节点
- ...
广度优先遍历（Broad First Search）
图的广度优先遍历，类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点
- 访问初始节点v并标记节点v为已访问
- 节点v入队列
- 当队列非空时，继续执行，否则算法结束
- 出队列，取得队列头节点u
- 查找节点u的第一个邻接节点w
- 若节点u的邻接节点w不存在，则转到第3步，否则执行以下三个步骤
- 若节点w未被访问，则访问节点w并标记为已访问
- 节点w入队列
- 查找节点u的下一个邻接节点，转到第6步
应用到这个图就是：
前提
- 坐标（x,y）的值如果为0 则表示x节点到y节点不存在路径
- 坐标（x,y）的值如果为1 则表示x节点到y节点存在路径
步骤
- 输出节点A，并标记节点A为已访问
- 节点A入队列
- 获取节点A的第一个邻接节点得到节点B
- 节点B未被访问过，输出节点B，并标记节点B为已访问
- 节点B入队列
- 获取节点A的下一个邻接节点得到节点C
- 节点C未被访问过，输出节点C，并标记节点C为已访问
- 节点C入队列
- 获取节点A的下一个邻接节点，不存在了
- 当前队列非空，获取队列的头即节点B
- 获取节点B的第一个邻接节点，得到节点A，节点A已经访问过了，获取节点B的第二个邻接节点，得到节点C，节点C已经访问过了，获取节点B的第三个邻接节点，得到节点D
- 节点D未被访问过，输出节点D，并表姐节点D为已访问
- ...
二分查找算法只适用于从有序的数列中进行查找。二分查找法的运行时间为对数时间O(log2n)，即查找到需要的目标位置最多需要log2n步，假设从[0-99]这100个数中寻找目标数30，则需要查找的步数为log2 100，即最多需要7次
分治法字面解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题...直到最后子问题可以简单的直接求解，原问题的解即子问题解的合并。这个技巧是很多高级算法的基础，如排序算法（快速排序、归并排序），傅立叶变换（快速傅立叶变换）
分治算法可以求解一些经典的问题
- 二分搜索
- 大整数乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解决各个子问题
- 合并：将各个子问题的解合并为原问题的解
if |P|≤n0
then return(ADHOC(P))
//将P分解为较小的子问题 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) 递归解决Pi
T ← MERGE(y1,y2,…,yk) 合并子问题
return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
思路：
- 如果是只有一个盘子，那么直接从柱子A移动到柱子C
- 如果有n>=2个盘子，我们总可以看作是两个盘子，1个是最下面的盘子，另一个是上面的盘子
- 先把最上面的移动到辅助位置B
- 再把最下面的移动到C
- 再把辅助柱子上的移动到C
可以给盘子做个标号，从上到下分别为1,2,3,...,n，这样移动几号盘子，从哪里到哪里就清晰了。
背包问题：有一个背包，容量为4磅，现有如下物品
- 要求达到的目标为装入的背包的总价值最大，并且重量不超出
- 要求装入的物品不能重复即每种物品最多放一个（零一背包问题）
- 动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
- 动态规划算法和分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
- 与分治算法不同的是，适合于用动态规划算法求解的问题，经分解得到的子问题往往不是相互独立的（下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
- 动态规划可以通过填表的方式逐步推进，得到最优解
构造一个二维表格，遍历到第i个物品，根据w[i]（第i个物品的重量）和v[i]（第i个物品的价值）判断是否需要将该物品放入背包。C为背包容量，maxValue[i][j]表示前i个物品在背包容量为j时可以达到的最大价值，则可以有以下结果：
- maxValue[i][0]=maxValue[0][i]=0，表示当背包容量为0时，价值为0，当没有物品放入时价值为0
- 当w[i]>j时，maxValue[i][j]=maxValue[i-1][j]，当准备加入的第i个物品的重量大于当前背包容量时，直接使用上一个单元格的值
- 当j>=w[i]时，maxValue[i][j] = Math.max( maxValue[i-1][j] , v[i] + maxValue[i-1][j-w[i]] )，当准备加入的第i个物品的重量小于等于当前背包容量时，判断上一个单元格的值 和 当前物品的价值与在背包容量是j-w[i]情况下v[i-1]前i-1个物品的最大价值和的较大值作为当前的价值
- maxValue[i-1][j]：就是上一个单元格在背包容量为j时可以达到的最大价值
- v[i]：当前物品的价值
- maxValue[i-1][j-w[i]]：当装入i-1商品时，在背包容量为j-w[i]时可以达到的最大价值
应用解说
-
当背包容量为0，或者不放入任何物品时maxValue为0
-
遍历当背包容量为1磅时，遍历物品
- 当是吉他时，可以放此时最大价值为1500
- 当是音响时，w[i]音响的重量是4，放不下音响，即w[i]>j ，背包价值还是原来的1500
- 和假如放入音响价值1500，那么背包剩余容量还能放的价值也是0。放入音响后还剩的容量j-w[i]就是0（当前背包容量j是1，w[j]也是1）价值是0。
- 1500，和1500+0相等，所以当是音响时最大价值是1500
- 当是电脑时，w[i]电脑的重量是3，放不下电脑，即w[i]>j ，背包价值还是原来的1500
-
遍历当背包容量为2磅时，遍历物品
- 当是吉他时，可以放此时最大价值为1500
- 当是音响时，w[i]音响的重量是4，放不下音响，即w[i]>j ，背包价值还是原来的1500
- 当是电脑时，w[i]电脑的重量是3，放不下电脑，即w[i]>j ，背包价值还是原来的1500
-
遍历当背包容量为3时，遍历物品
- 当是吉他时，可以放此时最大价值为1500
- 当是音响时，w[i]音响的重量是4，放不下音响，即w[i]>j ，背包价值还是原来的1500
- 当是电脑时，w[i]电脑的重量是3，背包的容量和电脑相同，即j>=w[i]，判断在遍历到电脑之前，背包的最大价值 maxValue[i-1][j] 1500 和 假如放入电脑后电脑的价值和剩余背包容量再次之前的最大价值 maxValue[i-1][j-w[i]]的和两者谁大
- maxValue[i-1][j]=1500
- v[i]=2000
- maxValue[i-1][0]=0，放下电脑后容量还剩0
- 1500 < 2000+0
- 所以这个时候，背包的最大价值为2000
-
遍历当背包容量为4时，遍历物品
- 当是吉他时，可以放此时最大价值为1500
- 当是音响时，w[i]音响的重量是4，背包的容量和音响相同，即j>=w[i]，判断在遍历到音响之前，背包的最大价值 maxValue[i-1][j] 1500 和 假如放入音响后音响的价值和剩余背包容量再次之前的最大价值 maxValue[i-1][j-w[i]]的和两者谁大
- maxValue[i-1][j]=1500
- 音响的价值 v[i]=3000
- maxValue[i-1][0]=0，放下电脑后容量还剩0
- 1500 < 3000 + 0
- 所以这个时候，背包的最大价值是3000
- 当是电脑时，w[i]电脑的重量是3，背包的容量和电脑相同，即j>=w[i]，判断在遍历到电脑之前，背包的最大价值 maxValue[i-1][j] 3000 和 假如放入电脑后电脑的价值和剩余背包容量再次之前的最大价值 maxValue[i-1][j-w[i]]的和两者谁大
- maxValue[i-1][j]=3000
- 电脑的价值 v[i]=2000
- maxValue[i-1][0]=1500，放下电脑后容量还剩1，当背包容量是1时，背包最大价值是 1500
- 3000 < 2000 + 1500
- 所以这个时候，背包的最大驾驶是3500
有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你"，现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
思路：
遍历str1字符串，判断str1[i]是否等于str2[j]，如果相等i++;j++;继续判断，如果不相等i=i-j+1;j=0;继续遍历str1，直到str1遍历结束或者中间过程匹配成功。
- KMP是一个解决模式串在文本串是否出现过，如果出现过，求解首次出现位置的经典算法
- Knuth-Morris-Pratt 字符串查找算法，简称KMP算法，常用于在一个文本串S中查找一个模式串P的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
- KMP算法利用判断过的信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到前面匹配过的位置，省去了大量的计算时间
- 参考资料 https://www.cnblogs.com/zzuuoo666/p/9028287.html
有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
要求：使用KMP算法完成判断，不能使用简单的暴力匹配算法.
思路
-
首先使用str1的第一个字符串和str2的第一个字符串去比较，不符合，关键词向后移动一位
-
重复第一步，还是不符合，继续后移
-
一直重复，直到str1有一个字符与str2的第一个字符符合为止
-
接着str1和str2下标都向后移动一位，比较还是符合
-
重复第四步，遇到了str1有一个字符与str2对应的字符不相符
-
这时候，按照暴力匹配的想法就是继续从i-j+1的地方遍历str1，如下图（i是这个时候str1遍历到的位置，j是str2这个时候遍历到的位置）这是很不明智的，因为此时BCD已经比较过了，没有必要再做重复的工作。当空格与str2的D不匹配时，现在知道的是前面六个字符是"ABCDAB"。KMP算法的思想就是设法利用这个已知信息，不要把搜索位置移动回到已经比较过的位置，减少比较的次数，提高效率
-
使用如下这个部分匹配表把刚刚重复的步骤省略掉
这个匹配表的产生后面在介绍
-
现在两个字符串匹配的状态是：已知空格和D不匹配，前面六个是匹配的。查匹配表D前面的字符B是最后一个匹配的字符，B对应的部分匹配值是2，因此按照下面的公式算出向后移动的位数。
- 移动位数=已匹配的字符数 - 对应的部分匹配值即 移动位数= 6 -2 等于4。所以将str1向后移动四个
-
继续逐位比较str1和str2，遇到了空格和C不匹配。
-
这个时候已匹配的字符数为2（"AB"），对应的部分匹配值为0，所以移动的位数=2-0，结果等于2，于是将搜索词即str1向后移动2位。现在状态是如下图
因为这个时候空格和A不匹配，同时还没有意境匹配的字符数，继续后移一位如下结果
-
继续逐位比较，直到发现C与D不匹配。于是，移动位数=6-2，即将搜索词向后移动4位
-
继续逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。
如果还要继续搜索即找出全部匹配，那移动位数=7-0 ，再将搜索词向后移动7位
先介绍下前缀和后缀
部分匹配值就是前缀和后缀的最长的共有元素的长度。以ABCDABD为例：
- A 的前缀和后缀都是空集，没有共有元素，共有元素的长度为0
- AB 的前缀是A，后缀是B，没有共有元素，共有元素的长度为0
- ABC 的前缀为[A,AB]，后缀为[BC,C]，没有共有元素，共有元素的长度为0
- ABCD 的前缀为[A,AB,ABC]，后缀为[BCD,CD,D]，没有共有元素，共有元素的长尾0
- ABCDA 的前缀为[A,AB,ABC,ABCD]，后缀为[BCDA,CDA,DA,A]，共有元素是A，共有的元素的长度是1
- ABCDAB 的前缀为[A,AB,ABC,ABCD,ABCDA]，后缀为[BCDAB,CDAB,DAB,AB,B]，共有元素是"AB"，共有元素的长度是2
- ABCDABD 的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB]，后缀为[BCDABD,CDABD,DABD,ABD,BD,D]，没有共有元素，共有元素的长尾0
部分匹配的实质是：有时候字符串头部和尾部会有重复，比如"ABCDAB"，之中有两个"AB"，那么它的部分匹配值就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置
贪心算法是指在对问题进行求解时，在每一步选择中都采取最好或者最优的选择，从而希望能够导致结果是最好或者最优的算法。
贪心算法所得到的结果不一定是最优的结果，但是是正确的，同时是相对接近最优解的结果。
存在如下表的需要付费的广播电台，以及每个广播电台信号可以覆盖的地区。如何选择最少的广播电台，让所有的地区都可以接收到信号。
思路分析
穷举法
列出所有广播电台相互组合的情况，这被称为幂集。假设有n个广播电台，则所有广播电台相互组合的方式有2^n-1种情况，假设每秒可以计算10个子集，则情况如下：
贪心算法
目前并没有算法可以快速计算得到准备的值，使用贪心算法，可以得到非常接近的解，并且效率高。贪心算法的过程是这样：
- 遍历所有的广播电台，找到一个覆盖了最多地区的电台，将这个电台加入结果集合中。
- 对剩下的广播电台可以覆盖的区域进行清除删除操作，删除已经覆盖了的地区
- 对剩下的广播电台重复第一步，直到所有的地区都被覆盖
针对这个例子过程如下：
-
目前所有的广播电台，k1、k2、k3都可以覆盖三个地区，选择k1广播台（由于这里是任意选择第一个覆盖最多的元素，所以得到的最终结果可能不是最优的）
-
k1广播台覆盖了北京、上海、天津，将k2、k3、k4、k5电台覆盖的区域中的北京、上海、天津 删除
-
删除重复区域之后k2、k3、k4、k5覆盖情况如下，k2、k3、k5可以覆盖两个地区，选择k2广播台
-
k2广播台覆盖了广州、深圳，将k3、k4、k5电台覆盖区域中的广州、深圳 删除
-
删除重复区域之后k3、k4、k5覆盖情况如下，k3、k5可以覆盖两个地区，选择k3广播电台
-
k3广播电台覆盖了成都、杭州，将k4、k5电台覆盖区域中的成都、杭州 删除
-
删除重复区域之后k4、k5电台覆盖情况如下，k5可以覆盖一个地区，选择k5广播电台
-
这个时候目标区域已经被全部覆盖，结束
由上面的过程可以看到，对于覆盖区域数量相同的广播电台在选择时，没有具体的策略。这样最终所得到的结果不一定就是最优的结果，但是相对接近最优结果。
比如上面的过程最终选择了k1、k2、k3、k5四个广播电台覆盖了全部的地区，但是k2、k3、k4、k5也是可以覆盖全部地区的。
最小生成树（Minimum Cost Spanning Tree）简称MST。给定一个带权的无向连通图，选取图中的边，将图的顶点全部连通，同时保证所选取边的权值的和最小，那由这些边和顶点确定的树，就叫做最小生成树
特点如下：
- n个顶点，一定有n-1条边
- 包含全部顶点
- n-1条边都在图中
求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法。
普里姆算法用来求最小生成树。在包含n个顶点的连通图中，找出只有n-1条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。
普里姆算法如下：
- 设G=(V,E)是连通图，T=(U,D)是最小生成树，V和U都是是顶点集合，E和D都是边的集合
- 从图的顶点集合V中取顶点u开始构造最小生成树，取出顶点u放入集合U中，标记顶点visited[u]=1
- 若集合U中顶点ui与集合V中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边(ui,vj)加入集合D中标记visited[vj]=1
- 重复步骤2，知道U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
在胜利乡有七个村庄A，B，C，D，E，F，G，现在需要修路把7个村庄连通。各个村庄的距离表示权值，比如A到B是5。问如何修路保证各个村庄都能连通，并且路的总里程树最短。
尽可能选择少的线路，并且每条路线最小，保证总里程数最少
- 假设从图的顶点A开始，此时最小生成树有一个顶点A，与A直接连通的村庄有A-B=5，A-G=2，A-C=7，选择路线值最小的2即确定了顶点G
- 现在最小生成树的顶点有A-G，与A-G直接连通的村庄有A-B=5，A-C=7，G-B=3，G-E=4，G-F=6，选择路线值最小的3，即确定了顶点B。注意这个时候最小生成树A-G是一个整体，所以A-G的连通是内部情况，不算是外部直接连通的村庄
- 现在最小生成树的顶点有A-G-B，与A-G-B直接连通的村庄有A-C=7，G-E=4，G-F=6，B-D=9，选择路线值最小的4即确定了顶点E。注意这个时候已经访问过的顶点间的路是最小生成树的内部，所以A-B，G-B不在展示出来
- 现在最小生成树的顶点有A-G-B-E，与A-G-B-E直接连通的村庄有A-C=7，G-F=6，B-D=9，E-C=8，E-F=5，选择路线值最小的5即确定了顶点F。
- 现在最小生成树的顶点有A-G-B-E-F，与A-G-B-E-F直接连通的村庄有A-C=7，B-D=9，E-C=8，F-D=4，选择路线值最小的4即确定了顶点D。
- 现在最小生成树的顶点有A-G-B-E-F-D，与A-G-B-E-F-D直接连通的村庄有A-C=7，E-C=8，选择路线值最小的7即确定了顶点C。
- 这个时候最小生成树的顶点和图的顶点相同了，说明已经把图的顶点全部连起来了，结束。
克鲁斯卡尔算法是用来求加权连通图最小生成树的算法。基本思想：
- 按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
某城市新增7个站点A，B，C，D，E，F，G，现在需要修路把七个站点连通。各个站点的距离表示权值，比如A到B是12公里。问如何修路保证各个站点都能连通，并且总的修建公里数最短？
- 第一步选择边E-F，因为权值最小是2
- 第二步选择边C-D，因为权值最小是3
- 第三步选择边D-E，因为权值最小是4
- 第四步选择边B-F，因为剩下的边中，虽然C-E边权值为5，但是如果选择这条边的话，就构成了一个回路，所以这个边不能选，同理边C-F也不能选
- 第五步选择边E-G，因为权值最下是8
- 第六步选择边边A-B，因为剩下的边中，虽然存在G-F和B-C，但是会构成回路，所以不能选
该算法稍微麻烦的地方就是选择一条边之后，和现在已经确定的边会不会构成回路。
思路如下：
记录顶点在最小生成树的终点，顶点的终点是最小生成树中与它连通的最大顶点。
每次添加一条边到最小生成树时，判断该边的两个顶点的终点是否重合，如果重合则说明会构成回路。
如上图：
在最C-D-E-F这个最小连通生成树中，最大的顶点是F。所以
顶点C的终点是F，顶点D的终点是F，顶点E的终点是F，顶点F的终点是F。这个时候将权值最小的边是C-E，C的终点和E的终点相同都是F，如果添加到最小生成树中会形成回路。也就是说加入到最小生成树的边的两个顶点不能指向同一个终点，否则会构成回路。
迪杰斯特拉算法是荷兰的科学家迪克斯特拉提出的，因此又叫做迪克斯特拉算法。用于计算一个顶点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。
图的顶点集合V{v1,v2,v3,vi...}
- 设置出发顶点为v，顶点集合V{v1,v2,v3,vi...}，v到集合各个顶点的距离构成距离集合Dis，Dis{d1,d2,d3,di...}，Dis集合记录着v到图中各顶点的距离（到自身可以看作0，v到vi的距离为di）
- 从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时v到vi是最短路径
- 更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个（同时更新顶点的前驱节点为vi，表明是通过vi到达的）
- 重复执行2，3步，直到其他顶点的最短路径被找到完
战争时期，胜利乡有七个村庄（A，B，C，D，E，F，G），现在有六个邮差从G点出发，需要分别把邮件送到A，B，C，D，E，F六个村庄。各个村庄的距离表示图的权，比如A-B距离是5公里。问G到其他各个村庄的最短距离是多少？如果从其他点出发又是多少？
- G是出发点，G到其他各个顶点{A,B,C,D,E,F,G}的距离Dis是{2,3,N,N,4,6,0}，选择最小的值2，说明G到A的最短距离是2，将A从顶点集合移出，2从距离集合移出
- 现在开始更新Dis，
- B点 G到B的距离为3，A到B距离为5，从G到B比从G到A再到B小，不用更新
- C点 G到C的距离为N，A到C的距离为7，从G到C比从G到A再到C小，更新到C的距离为9（7+2），前驱节点为A
- D点 G到D的距离为N，A到D的距离为N，不用更新
- E点 G到E的距离为4，A到E的距离为N，不用更新
和迪杰斯特拉算法一样，弗洛伊德算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。弗洛伊德算法计算图中各个顶点之间的最短距离；迪杰斯特拉用于计算图中某一个顶点到其他顶点的最短路径。
弗洛伊德算法和迪杰斯特拉算法比较：
- 迪杰斯特拉算法通过选定的被访问顶点，求出出发顶点到其他顶点的最短距离
- 弗洛伊德算法每一个顶点都是出发访问点，求出从每一个顶点到其他顶点的最短路径
设顶点vi到顶点vk的最短路径为Lik，顶点vk到vj的最短路径为Lkj，顶点vi到vj的路径为Lij，那么vi到vj的最短路径为min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径。
以上图表为例。当前各顶点之间的距离和各顶点的前驱顶点情况如下：
以顶点A为中间顶点更新各顶点之间距离和顶点的前驱
- 以A为中间点，起点为A，遍历到达其他终点的情况
- 从A到A再到B，不比从A到B距离近，不更新；同样的从A到A再到G，不比从A到G距离近，不更新
- 以A为中间点，起点为B，遍历到达其他终点的情况
- 从B到A再到A，不比从B到A距离近，不更新
- 从B到A在到B，不比从B到B距离近，不更新
- 从B到A再到C，小于从B到C，更新从B到C的距离，同时更新前驱节点关系
- 从B到A再到D，不比从B到D距离近，不更新
- 从B到A再到E，不比从B到E距离近，不更新
- 从B到A再到F，不比从B到F距离近，不更新
- 从B到A再到G，不比从B到G距离近，不更新
- 以A为中间点，起点为C，遍历到达其他终点的情况
...
以A为中间点，所有情况遍历结束的结果如下：
同样以B，C，D。。。为中间点对两个表进行更新。结束后的距离表就是要的结果。
将马随机放在国际象棋的8X*的棋盘的某个方格中，马按走棋规则（马走日）进行移动。要求每个方格只能走一次，走遍棋盘上全部64个方格。
- 创建一个二维数组的棋盘
- 将当前位置设置为已经访问，然后根据当前位置，计算马还能走哪些位置（最多八个位置），将这些位置放到一个集合中
- 遍历集合中存放的所有位置，看看哪个可以走通，如果走通就继续，如果走不通就回溯
- 判断是否完成了任务，使用实际走的步数和应该走的步数比较
使用贪心算法进行优化。
获取得到马在当前位置还能走哪些位置，然后对这些位置遍历，会有回溯次数较多的可能。所以获取所有能走的位置的所有能走位置，然后对其进行从小到大排序。这样在遍历会大大提升回溯次数，提高效率。
