# algorithm-master **Repository Path**: springweifuwu/algorithm-master ## Basic Information - **Project Name**: algorithm-master - **Description**: 引用 https://github.com/hollischuang/algorithm-master 学习 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-09-24 - **Last Updated**: 2025-09-24 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 算法学习 * 这个专栏是Hollis知识星球的朋友们练习算法的地方 * 欢迎广大网友参与分享算法学习经验 * 项目目前分为两部分 * solutions 目录 * 算法题解，格式是 md 格式文件，方便阅读 * 包括 * 算法平台的题解，如 Leetcode 等 * 算法书籍的题解，如 《剑指 Offer》 * codes 目录： * 数据结构和算法的实现代码 * 包括 * 各类网络公开课的代码 * 各类算法书籍的代码 * 备注 * 本项目选取的资源都来自官方公开免费资源 * 本项目所有内容不做商业用途 * 本项目大部分代码由贡献者自己编写，如有引用则注明出处 # 学习方式 ## 1. 面试刷题 >适合短期面试突击或日常刷题练手 * LeetCode：https://leetcode-cn.com/problemset/all * 牛客网：https://www.nowcoder.com ## 2. 基础知识 > 适合从零开始真正学习和掌握数据结构和算法知识 ### 网络公开课 #### 1) 数据结构与算法基础-java版（罗召勇） * 访问地址： https://www.bilibili.com/video/BV1Zt411o7Rn #### 2) 尚硅谷Java数据结构与java算法（Java数据结构与算法） * 访问地址 https://www.bilibili.com/video/BV1E4411H73v # 笔记 # 一、数据结构与算法基础-java版（罗召勇） >本课程为 DT 课堂颜群发布在 Bilibili 上的免费视频 《数据结构与算法基础-java版（罗召勇）》 https://www.bilibili.com/video/BV1Zt411o7Rn * 本项目中实现代码： codes/java_dataStructure_luozhaoyong # 1. 数据结构概述 ## 概念 * 数据结构：数据与数据之间的关系 * 两方面讨论： * 存储结构 * 顺序存储：存储在连续的存储单元 * 链式存储：不连续，每次存储都有数据和指针 * 逻辑结构 * 数据和数据本身之间的关系 * 集合结构：数据同属于一个集合 * 线性结构：元素之间一对一的关系 * 数组 * 栈 * 队列 * 单链表 * 循环链表 * 双链表 * 递归 * 排序算法 * 树形结构：元素之间一对多的关系 * 图形结构：元素之间多对多的关系 # 2. 算法概述 * 算法定义：解决问题的思路 * 算法的特性： * 输入：0 到多个输入 * 输出：至少 1 个输出 * 有穷性：有限的步骤里算出结果 * 确定性：一个输入对应一个输出，结果确定 * 可行性：能够解决实际问题 * 算法的基本要求： * 正确性：能够得出正确的结果 * 可读性：能够被看懂 * 健壮性：对于各种情形算法都有效 * 时间复杂度：消耗的时间 * 空间复杂度：占用的内存 # 3. 数组的基本作用 >顺序存储的线性结构称为数组 ## 数组的使用 * 下标从 0 开始，下标最大值为（数组长度-1） * 数组创建方式： * int[] arr = new int[3]; * int 规定了数组中元素的类型 * 3 规定了数组的长度 * arr[0] = 1; // 为数组中指定位置赋值 * int[] arr = new int[]{1, 2, 3 }; * 创建数组的同时给数组赋值 # 4. 数组元素的添加 ## 动态扩容 >解决数组元素不可变的问题 * 1) 新建一个数组，长度为原数组长度+1 * 2) 将原数组中的元素逐个赋值到新数组 * 3) 将目标元素添加到新数组的末尾 * 4) 用新数组替换原数组 # 5. 数组元素的删除 * 1) 创建一个新数组，长度为原数组长度-1 * 2) 将原数组中除要删除元素之外的元素，逐个赋值给新数组 * 3) 用新数组替换原数组 # 6. 面向对象的数组 * 在对象数组中创建一个数组成员变量，实际操作都在这个成员变量中进行 * 主要操作： * 向数组末尾添加元素 * 删除指定位置的元素 * 获取指定位置的元素 * 插入一个元素到指定位置 * 为数组中指定位置赋值 # 7. 查找算法之线性查找 * 遍历每一个元素，依次与目标值对比 # 8. 查找算法之二分法查找 * 适用范围：有序数组 * 步骤： * 1) 数组开始位置为 0，结束位置为数组长度 -1 * 2) 通过开始位置和结束位置获取中间位置的值 * 3) 将中间值与目标值对比 * 中间值 > 目标值：将结束位置左移到中间位置-1，继续向左查找更小的值 * 中间值 < 目标值：将开始位置右移到中间位置+1，继续向右查找更小的值 * 中间值 = 目标值：中间值就是要查找的值，返回中间值下标 * 4) 重复步骤 2 和 3，直至找出目标位置或者遍历完数组 # 10. 栈 ## 数组实现栈的思路 * 向数组末尾添加元素 * 从数组末尾取元素 * 依次实现下列方法： * push * pop * peek * isEmpty # 11. 队列 ## 数组实现队列的思路 * 在数组末尾加入元素 * 在数组开头取出元素 * 依次实现下列方法 * add * poll * isEmpty # 12. 单链表 * 定义节点类 Node，包含以下成员变量 * int data：节点内容/数据 * Node next：下一个节点，类型也是节点 * 为节点类添加下列方法 * append // 向链表末尾添加 * next // 获取当前节点的下一个节点 * getData // 获取节点的数据 * isLast // 判断当前节点是否为最后一个节点 # 13. 删除单链表中的节点 * 删除当前节点的后继节点 * 获取后继节点的后继节点 * 将当前节点的后继节点指向新的后继节点 * 原有后继节点与前置和后继节点都失去了联系，达到了删除效果 # 14. 在单链表中插入一个节点 * 让当前节点的后继节点指向要插入的节点 * 要插入的节点后继节点指向原后继节点 * 新的连接关系：当前节点-->插入节点-->原后继节点 # 15. 循环链表 * 链表最后一个节点的后继节点指向链表的头节点 * 实现下列方法 * next 获取后继节点 * getData 获取当前节点值 * after 插入一个新节点 # 16. 循环双链表 * 每一个节点都会记录其前置节点和后继节点 * 三个成员变量 * 上一个节点 * 下一个节点 * 当前节点数据 * 实现下列方法 * after 新增节点 * next 获取后继节点 * pre 获取前驱节点 * getData 获取当前节点值 # 17. 递归和斐波那契数列 * 递归就是在函数内部调用该函数本身 * 斐波那契数列：1 1 2 3 ... * 从第三项起，每一项的值都是前两项之和 # 18. 汉诺塔问题 * 三根柱子 + n 个盘子 * n 个盘子一开始都在第一根柱子上 * 每次只能移动一个盘子 * 用最少的步数将 n 个盘子从第一根柱子移动到第三根柱子 * 解决思路 * 求出只有 1 个盘子的情况 * 求出只有 2 个盘子的情况 * n 个盘子的情况都可以简化成 2 个盘子的情况 # 19. 算法的时间复杂度和空间复杂度 * 时间复杂度：运行时占用时间 * 空间复杂度：运行时占用内存 * 一个算法中语句需要执行的次数，称为语句频度，记为 T(N) * 随着执行次数增多，时间复杂度估算时可以忽略以下内容 * 忽略常数项 * 在坐标轴上画出曲线 * 随着 n 的增大 * 2n+20 和 2n 两条曲线会趋向重合 * 3n+10 和 3n 两条曲线会趋向重合 * 在 n 较大时，常数项的影响可以忽略 * 忽略低次项 * 在坐标轴上画出曲线 * 随着 n 的增大 * 2n^2 + 3n + 10 和 2n^2 两条曲线都趋向 n^2 * n^2 + 5n + 20 和 n^2 两条曲线都趋向 n^2 * 在 n 较大时，低次项的影响可以忽略 * 忽略系数 * 在坐标轴上画出曲线 * 随着 n 的增大 * 3n^2 + 2n 和 5n^2 + 7n 两条曲线趋向重合 * n^3 + 5n 和 6n^3 + 4n 两条曲线趋向重合 * 在 n 较大时，稀疏的影响可以忽略 * 大 O 表示法 * T(n) 表示算法中基本操作语句的重复执行次数是问题规模 n 的函数 * 如果有一个辅助函数 f(n) * 使得 n 趋近于无穷大时，T(n) 和 f(n) 的极限值为不等于 0 的常数 * 则称 f(n) 是 T(n) 的同数量级函数，记做 T(n) = O(f(n)) * O(f(n)) 称为算法的渐进时间复杂度，简称时间复杂度 * 常见的时间复杂度 * 常数阶 O(1) * 对数阶 O(log2n) * 线性阶 O(n) * 线性对数阶 O(nlog2n) * 平方阶 O(n^2) * 立方阶 O(n^3) * 次方阶 O(n^k) * 指数阶 O(2^n) * 随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法执行效率越低 * 计算时间复杂度的方法 * 常数 1 代替所有加法常数 * 只保留最高阶项 * 去掉最高阶项的系数 * 平均时间复杂度和最坏时间复杂度 * 通常只讨论最坏时间复杂度 # 20. 排序算法之冒泡排序 ## 常见排序算法总结 * 交换排序 * 冒泡排序 * 快速排序 * 插入排序 * 直接插入排序 * 希尔排序 * 选择排序 * 简单选择排序 * 堆排序 * 归并排序 * 基数排序 ## 冒泡排序 * 第一轮 * 从第 1 个元素开始，比较相邻两个元素，将较大的元素后移，直到最大的元素移动到数组末尾 * 第二轮 * 从第 1 个元素开始，比较相邻两个元素，将较大的元素后移，直到本轮最大的元素移动到数组倒数第二个位置 * 第三轮 * 从第 1 个元素开始，比较相邻两个元素，将较大的元素后移，直到本轮最大的元素移动到数组倒数第三个位置 * 第 n 轮 * 每轮都从第 1 个元素开始，比较相邻两个元素，将较大的元素后移 * 前一轮的最大元素不再参与下一轮比较，所以每一轮参与比较的元素都比上一轮少 1 个 * 每一轮中最大元素都会从前往后移，类似气泡冒出水面，所以称为冒泡排序 # 21. 排序算法之快速排序 * 1) 从数组中找出一个基准数 * 2) 数组定义左右两个指针分别向中间移动 * 3) 数组左侧的值比基准值大，则移到数组右侧 * 4) 数组右侧的值比基准值小，则移到数组左侧 * 5) 当左右两个指针重合时，当前轮排序结束 * 6) 指针重合的位置将数组分为两部分，分别对两部分递归调用快速排序 * 7) 重复上述步骤，直到排序完成 # 22. 排序算法之插入排序 * 将数组分为未排序和已排序两部分 * 从数组第二个元素位置开始 * 每次从未排序部分取出第一个数字 * 将其按规定顺序插入已排序部分 * 同时插入位置之后的数字依次后移 1 位 * 重复上述步骤，已排序部分逐渐向右扩大，直到所有数字都正确排序为止 # 23. 排序算法之希尔排序 * 插入排序的问题 * 如果待插入的数字，比已排序部分所有数字都小 * 那么已排序部分就要进行大量的元素后移操作，效率较低 * 希尔排序 * 取某个数字作为步长，按步长对数组进行插入排序 * 排序完成后，步长按规律递减 * 用新步长进行下一轮插入排序 * 重复上述步骤，直到步长变成 1，进行最后一轮普通的插入排序为止 # 24. 排序算法之选择排序 * 将数组看作有序和无序两部分 * 从第一个元素开始，在无序部分找出最小的元素 * 将最小的元素与无序部分的第一个元素交换位置 * 重复上述步骤，直到数组完全有序为止 # 25. 排序算法之归并排序 * 归并方法 * 原数组已经被分为两部分，每部分都各自有序 * 创建一个与原数组等长的临时数组 * 依次从两部分中取出元素进行对比，按照顺序放入临时数组 * 所有元素都放入新数组后，整个数组已经排好序 * 将临时数组重新赋值给原有数组 * 递归部分 * 将原数组折半划分为两部分 * 依次对两部分递归调用递归算法 * 直到数组不可再分 # 26. 排序算法之基数排序 * 思路 * 第一轮按所有元素的个位数字排序 * 第二轮按所有元素的十位数字排序 * 以此类推 * 当按照数组中元素的最大位数排序之后，最终得到 1 个有序的数组 * 举例 * 例如数组 [5, 1, 72, 36, 101] * 为便于理解，想象元素空缺的位数上都是 0 * 把数组写成如下形式 * 排序前的原始数组 [005, 001, 072, 036, 101] * 第一轮按个位排序 [001, 101, 072, 005, 036] * 第二轮按十位排序 [001, 101, 005, 036, 072] * 第三轮按百位排序 [001, 005, 036, 072, 101] * 每轮排序后，位数相同的数字，相对顺序不会改变 * 如第一次按照个位排序后，两个个位数字 1 和 5 * 1 在接下来的几轮排序过程中，总是位于 5 的前面 * 所有排序结束后，就得到了按照数字整体大小排列的数组 # 27. 基数排序之队列实现 * 26 节的基数排序中，我们使用二维数组来表示桶 * 桶中的元素有先进先出的特点，可以将二维数组换成队列 # 28. 树结构概述 ## 数据结构的特点： * 线性结构： * 顺序存储：添加删除耗时 * 链式存储：查找耗时 * 树结构： * 解决了顺序存储和链式存储的上述问题 ## 树的基本概念： * 根结点：起始节点 * 双亲节点（即父节点）：有子节点的节点 * 子节点：向上溯源，有双亲节点的节点 * 路径：从根结点到指定节点所要经过的所有节点 * 节点的度：子节点的个数 * 节点的权：节点的数值 * 叶子节点：没有子节点的节点，即度为 0 的树 * 子树：树中包含的树 * 层：把根结点看作第一层，根结点的子树为第二层，树有多少代，就有多少层 * 树的高度：树的最大层数 * 森林：多棵树组成一个森林 # 29. 二叉树概述： * 概念： * 任何一个节点，子节点的数量不超过 2，这棵树就是二叉树 * 二叉树的左右节点顺序不同，视为不同的两棵树 * 满二叉树： * 所有叶子节点都在最后一层 * 且总的节点个数为 2^n-1 * n 是树的高度 * 完全二叉树： * 所有叶子节点都在最后一层或倒数第二层 * 且最后一层的叶子节点在左边连续 * 倒数第二层的叶子节点在右边连续 * 数节点确认： * 从左向右从上到下数节点 * 数到最后一个节点 * 完全连续没有间断就是完全二叉树 # 30. 创建二叉树 ## 二叉树的存储结构 * 链式存储 * 创建二叉树 * 添加节点 * 查找节点 * 树的遍历 * 删除节点 * 顺序存储 ## 二叉树的形态 * 空树：无节点 * 左斜树：所有节点都在左侧 * 右斜树：所有节点都在右侧 # 31. 树的遍历 * 三种遍历形式： * 根据根结点的位置确定顺序 * 前序：根结点-->左节点-->右节点 * 中序：左结点-->根节点-->右节点 * 后序：左结点-->右节点-->根节点 # 32. 二叉树中节点的查找（链式存储） * 与二叉树遍历方法类似 # 33. 删除二叉树的子树（链式存储） * 递归删除 # 34. 顺序存储的二叉树介绍 * 顺序存储二叉树通常只考虑完全二叉树 ## 性质 * 第 n 个元素的左子节点是 2*n+1 * 第 n 个元素的右子节点是 2*n+2 * 第 n 个节点的父节点是 (n-1)/2 # 35. 顺序二叉树的遍历 * 与链式存储二叉树的遍历相似，以前序遍历为例 * 双亲节点 index * 左子节点 2*index+1 * 右子节点 2*index+2 * 需要传入一个参数，确定遍历的起点 # 36. 常用排序算法之堆排序 ## 堆的概念 * 大顶堆：每个节点都大于等于其左右孩子节点的值 * 小顶堆：每个节点都小于等于其左右孩子节点的值 ## 堆排序的应用 * 升序使用大顶堆 * 降序使用小顶堆 ## 如何将顺序存储的二叉树转成大顶堆 >从左至右，从上至下调整 * 0) 从最后一个非叶子节点开始调整 * 1) 将这个非叶子节点与其子节点对比，检查是否最大 * 2) 如果不是，交换二者位置 * 3) 交换位置后原有的堆结构发生了变化 * 4) 对调整后的最大非叶子节点重复步骤 1~3 * 5) 循环遍历一个顺序存储的二叉树，对每一个非叶子节点执行步骤 1~4 ## 堆排序的步骤（以大顶堆为例） * 1) 将大小为 n 的顺序存储二叉树调整成一个大顶堆 * 2) 将数组第 0 个数和第 n 个数交换 * 3) 将数组大小递减 1，对递减后的数组重复执行 1~2 # 37. 线索二叉树 * 顺序存储二叉树遍历到某个节点时，无法知道它的前驱节点和后续节点 * 利用二叉树节点的空链域存储前驱或者后继节点的指针，这些指针就称为线索 * 当某个节点没有左子节点时，将左指针指向它的前一个节点 * 当某个节点没有右子节点时，将右指针指向它的后一个节点 * 线索化二叉树时，可以通过标记的方式，说明指向的是前驱/后继节点还是孩子节点 # 38. 线索二叉树的代码实现 * 1) 创建两个变量，分别用于标识左子节点和右子节点的类型 * 默认 0 表示指针指向孩子节点 * 1 表示当前指针指向前驱或后继节点 * 2) 创建一个变量，临时存储前驱节点 * 3) 对左子节点和右子节点递归调用线索化方法 * 4) 对当前节点的进行线索化： * 如果左子节点为空，将空指针指向前驱节点，左指针类型标识改为 1 * 如果前驱节点的右子节点为空，将空指针指向当前节点，前驱节点的右指针类型标识改为 1 * 5) 线索化结束后，让前驱节点指向当前节点，供下一轮使用 # 39. 线索化二叉树的遍历 ## 思路： * 中序遍历，向左前溯，找到第一个被线索化的节点 * 不断输出后继节点的值，直到没有后继节点 * 找到最后一个后继节点的右子节点，继续下一轮查找和输出 ## 步骤 * 1) 不断前溯左子节点，直至找到第一个被线索化的节点 * 2) 从这个节点开始，不断查找后继节点并输出节点的值 * 3) 找到最后一个后继节点的右子节点，重复步骤 1 和 2，直到节点为空 # 40. 赫夫曼树概述 * 赫夫曼编码是数据压缩的重要方法 * 叶结点的带权路径： * 从根结点出发，到达某个叶结点时，经过的节点数量，乘以叶结点的权值 * 如叶子节点 A 的权值为 9，从根结点到达 A 节点，经过了 2 个节点，A 的权值就是 2*9=18 * 树的带权路径长度： * WPL：weighted path length * 树中所有叶子节点带权路径之和 * 最优二叉树： * WPL 最小时，称为最优二叉树，也叫赫夫曼树 * 权值越大的节点离根结点越近，这样才能保证带权路径尽可能小 # 41. 赫夫曼树的流程分析 * 1) 将数组中的每个元素都转化为二叉树，初始状态每棵二叉树只有一个节点 * 2) 将数组中的二叉树按根结点的权值正序排列 * 3) 从数组中取出根结点权值最小的两棵二叉树 * 将这两棵二叉树的根结点视为孩子节点，为它们创建一个父节点 * 父节点的权值是两个孩子节点的权值之和 * 新的父节点和原先的两棵二叉树组成了一棵新的二叉树 * 4) 将新创建的二叉树插入数组 * 5) 重复步骤 2~4，每次取出两个元素，放回一个元素，直到数组剩下一个元素为止 * 剩下的这个元素，就是整棵赫夫曼树的根结点 # 42. 代码实现赫夫曼树 * 1) 将数组中的所有元素转化为二叉树 * 2) 取出数组中根结点权值最小的两棵二叉树 * 3) 用两棵二叉树的根结点作为孩子节点，创建一棵新的二叉树 * 二叉树根结点的权值是两棵孩子节点权值之和 * 4) 移除数组中取出的两棵二叉树 * 5) 将新创建的二叉树放入数组 * 6) 当数组中的元素大于 1 时，循环执行步骤 2~5 # 43. 赫夫曼编码原理分析 * 通信和压缩领域应用非常广泛 ``` can you can a can as a can canner can a can ``` * 通信领域中信息的处理 * 定长编码： * ```99 97 110 32 121 ... 32 97 32 99 97 110 46``` * 单词-->ASIIC 编码-->每个数字都转成 8 位的字节 * ```01100011 01100001 ... 00101110``` * 缺点：固定长度，传输内容太多 * 非定长编码： * 计数：```r:1 s:1 .. n:8 :11 a:11``` * ```0=a, 1= , 10=n, 11=c ... 10=r``` * 将字符串中每个字符出现的次数表示出来 * 编码： * 出现次数多的字符用较少位的字节来表示 * 出现次数少的字符用较多位的字节来表示 * 前缀编码：字符的编码都不能是其他字符编码的前缀 * 前缀编码才能进行解码 * 赫夫曼编码： * 将字符串中每个字符出现的次数表示出来 *```r:1 s:1 .. a:11``` * 将字符作为节点的数据，出现次数作为节点的权值 * 出现次数多的字符靠近根结点，编码长度较短 * 将左连接定义为 0，右连接定义为 1，树的路径就有了编码 * 赫夫曼树的路径是唯一的，因此每个字符的编码都是唯一的 # 44~45. 数据压缩之创建赫夫曼树 ## 创建节点类 Node： * 属性： * int weight 权值，某个字符出现了多少次 * Node left 左子节点 * Node right 右子节点 * Byte data 当前节点对应的字符 * 采用包装类 Byte 可以定义空值 * 构造方法： *public Node(Byte data, int weight) ## 赫夫曼编码方法： * 共经历了 6 次形态转换 * 1) 字符串 --> 未压缩的 byte 数组 * 2) 未压缩的 byte 数组 --> 二叉树节点列表 * 3) 二叉树节点列表 --> 赫夫曼树 * 4) 赫夫曼树 --> 赫夫曼编码表 * 5) 字符数组 + 赫夫曼编码表 --> 二进制字符串 * 6) 二进制字符串 --> 压缩后的 byte 数组 ### 1. 字符串 --> byte 数组 * 调用 String 对象的 getBytes() 方法 ### 2. byte 数组 --> 二叉树节点列表 * 创建一个 HashMap，键类型是 Byte，值类型是 Integer * 遍历 byte 数组，通过 HashMap 存储并统计单个 byte 出现的次数 * 从 HashMap 中取出对应的键值对 * 以 Byte 值作为节点数据，出现次数作为节点权值 * 每个键值对都转为一个二叉树根节点 Node * 将所有二叉树节点存入列表备用 ### 3. 二叉树节点列表 --> 赫夫曼树 * 1) 遍历 Node 列表 * 2) 按 Node 权值 weight 降序对列表排序 * 3) 取出列表中权值最小的两个元素，即列表倒数两个元素 * 4) 将两个元素作为孩子节点创建一个父节点，父节点的权值是两个孩子节点权值之和 * 6) 同时将父节点的左右指针指向两个孩子节点 * 7) 从原列表中删除第 3 步中取出的两个权值最小的元素 * 8) 将新建的节点存入列表 * 9) 当列表中元素数量大于 1 时，重复步骤 2~6 * 10) 最终列表中只剩下一个元素，这个元素就是赫夫曼树的根结点 ### 4. 赫夫曼树 --> 赫夫曼编码表 * 1) 新建一个 HashMap 对象记录赫夫曼编码表 * 键：赫夫曼树上某个节点的键，即字符 * 值：赫夫曼树根节点到达当前字符的路径 * 到达左子树的路径用 0 表示，到达右子树的路径用 1 表示 * 路径变成一个由 0 和 1 组成的二进制字符串 * 这样每个节点得到的二进制字符串都是唯一的 * 2) 遍历赫夫曼树，将赫夫曼树上节点的相关信息转录到赫夫曼编码表 ### 5. 字符数组 + 赫夫曼编码表 --> 二进制字符串 * 1) 遍历原字符数组 * 2) 对照赫夫曼编码表，获取每个字符对应的赫夫曼编码 * 3) 将获取到的编码拼接到单个字符串 * 4) 最终字符数组转成了一个遵循赫夫曼编码表的二进制字符串 ### 6. 二进制字符串 --> 压缩后的 byte 数组 * 1) 以 8 为步长遍历二进制字符串 * 8 位二进制字符串 --> 十进制数字 --> byte 字符 * 将新的 byte 字符存入新的字符数组中 * 2) 最终得到一个按赫夫曼编码表压缩后的字符数组 # 46. 使用赫夫曼编码进行解码 * 共进行了 2 次形态变化 * 1) 字符数组 --> 二进制字符串 * 1.1) 遍历字符数组 * 1.2) 将每个字符都转为 8 位的二进制字符串 * 如果正整数不够 8 位，数字前用 0 填充 * 1.3) 将所有字符的二进制字符串拼接成一个完整的二进制字符串 * 2) 二进制字符串 + 赫夫曼编码表 --> 原字符数组 * 2.1) 将原赫夫曼编码表的键和值互换 * 即原先键是 Byte，值是 String * 互换后键是 String，值是 Byte * 2.2) 遍历二进制字符串，以各种可能的组合在赫夫曼编码表中查找原 byte * 2.3) 将 byte 存入列表后转成数组 # 47 使用赫夫曼编码压缩文件 * 1) 文件来源路径 --> 创建输入流 * new FileInputStream(文件来源路径) * 2) 创建和输入流指向文件大小一致的 byte 数组 * byte[] b = new byte[FileInputStream 对象.available()] * available() 在操作前得知数据流大小 * 3) 读取文件，关闭输入流 * 4) 调用赫夫曼编码方法对 byte 数组编码 * 5) 文件输出路径 --> 创建输出流 * new FileOutputStream(文件输出路径) * new ObjectOutputStream(FileOutputStream 对象) * 6) 将压缩后的 byte 数组写入文件 * 7) 将赫夫曼编码表写入文件 * 8) 关闭输出流 # 48. 文件的解压 * 1) 创建一个输入流对象，读取压缩文件 * new FileInputStream(压缩文件路径) * new ObjectInputStream(FileInputStream 对象) * 2) 读取压缩文件中的 byte 数组 * byte[] b = (byte[]) ObjectInputStream 对象.readObject() * 3) 读取压缩文件中的赫夫曼编码 * Map codes = (Map) ObjectInputStream 对象.readObject() * 4) 关闭输入流 * 5) 通过赫夫曼编码将读取出来的 byte 数组解码为原 byte 数组 * 6) 创建一个输出流对象 * new FileOutputStream(输出文件路径) * 7) 将解码后的 byte 数组写入文件 * FileOutputStream 对象.write(byte 数组) * 8) 关闭输出流 # 49. 二叉排序树 ## 线性结构 * 顺序存储，不排序 * 查找困难 * 顺序存储，排序 * 二分查找效率高 * 删除插入困难 * 链式存储 * 无论是否排序，查找都困难 ## 树形结构 * 二叉排序树，BST * 概念 * 也叫二叉查找树，二叉搜索树 * 对于排序树中的任何一个非叶子节点 * 左子节点比当前节点小 * 右子节点比当前节点大 * 查找和插入删除性能都较高 # 50. 创建二叉排序树 & 添加节点 * 待添加的节点 * 1) 如果当前节点为空 --> 赋给当前节点 * 2) 如果值比当前节点小 * 左子节点为空 --> 赋给左子节点 * 左子节点非空 --> 递归调用左子节点的添加方法 * 3) 如果值比当前节点大 * 右子节点为空 --> 赋给右子节点 * 右子节点非空 --> 递归调用右子节点的添加方法 * 二叉排序树的中序遍历正好是从小到大排列 # 51. 二叉排序树中查找节点 * 要查找的值 == 当前节点的值 --> 返回当前节点 * 要查找的值 < 当前节点的值 --> 递归调用左子节点的查找方法 * 要查找的值 > 当前节点的值 --> 递归调用右子节点的查找方法 # 52. 删除叶子节点 * 目标节点没有孩子节点 * 查找目标节点 * 查找目标节点的父节点 * 将目标节点与父节点断开连接 # 53. 删除只有一棵子树的节点 * 查找目标节点 * 查找目标节点的父节点 * 将目标节点的子树与父节点建立连接 # 54. 删除有两棵子树的节点 * 查找目标节点 * 查找目标节点的最小子树 * 删除目标节点的最小子树，并返回最小子树的值 * 用最小子树的值替换目标节点的值 # 55. 平衡二叉树概述 * 二叉排序树的问题 * 如果将连续递增或递减的数组转为二叉排序树 * 二叉排序树的节点都在同一边，查询效率与链表差不多 * 平衡二叉树 * 首先平衡二叉树是一棵二叉排序树 * 左子树和右子树高度差的绝对值不超过 1 * 左子树和右子树也是平衡二叉树 # 56. 构建二叉平衡树之单旋转 * 根据左右节点高度差的绝对值，判断当前节点是否为平衡二叉树 * 左左：(左子树高度 - 右子树高度) > 1 * 顺时针右旋 * 1) node --> newNode * 2) node.right --> newNode.right * 3) node.left.right --> newNode.left * 4) node.left.value --> node.value * 5) node.left.left --> node.left * 6) newNode --> node.right * 右右：(右子树高度 - 左子树高度) > 1 * 顺时针左旋 * 1) node --> newNode * 2) node.left --> newNode.left * 3) node.right.left --> newNode.right * 4) node.right.value --> node.value * 5) node.right.right --> node.right * 6) newNode --> node # 57. 构建平衡二叉树之双旋转 * node.left.left 高度 < node.left.right 高度 * 1) left 左旋转 * 2) node 右旋转 * node.right.right 高度 < node.right.left 高度 * 1) right 右旋转 * 2) node 左旋转 # 58. 多路查找树-计算机数据的存储原理 * 应用于内存，小数据量的树结构 * 二叉树 * 线索二叉树 * 赫夫曼树 * 二叉排序树 * AVL 树 * 应用于磁盘存储，数据量大的树结构 * 多路查找树 * 2-3 树和 2-3-4 树 * B 树和 B+ 树 ## 数据存储方式 * 内存 * 优点： * 电信号保存信息，不存在机器操作 * 访问速度快 * 缺点： * 造价高 * 断电后数据丢失 * 一般作为 CPU 告诉缓存 * 磁盘： * 优点 * 造价低，容量大 * 断电数据不丢失 * 缺点： * 存储介质特性和机械运动耗费时间，磁盘速度慢 * 磁盘的预读 * 为了减少 I/O 操作，磁盘通常不是按需读取 * 每次都会预读，顺序向后读取一定长度的数据放入内存 * 计算机科学中的局部性原理：一个数据被用到时，其附近的数据通常也会被用到 * 预读的长度一般为页（page）的整数倍 * 页 * 页是计算机管理存储的逻辑块 * 硬件及操作系统将主存和磁盘存储区分割为连续的大小相等的块 * 每个存储块为一页 * 页的大小一般为 4k * 主存和磁盘以页为单位交换数据 * B 树存储 * 利用磁盘预读原理，将一个节点的大小设为一个页 * 单个节点进行横向扩展 * 每个节点只需一次 I/O 就可以完全载入 * 二叉树与 B 树对比 * 二叉树 * 树高为 5 的二叉树 * 节点数=2^5-1 = 31 个 * B 树 * 树高为 2 * 第一层 1 个节点，横向扩展为 3 个节点 * 第二层 4 个节点，每个节点横向扩展为 7 个节点 * 节点树=1×3 + 4×7 = 31 * 同样的节点树，B 树只需要两层即可 * 如果将树的度，即子节点的个数，设为 1024 * 树高 2：1024^2 = 1,048,576 ≈ 100 万 * 树高 3：1024^3 = 1,073,741,824 ≈ 1 亿 * 树高 4：1024^4 = 1,099,511,627,776 ≈ 1000 亿 * 600 亿 < 1000 亿，至多 4 次 I/O 即可查询到 # 59. 2-3 树的插入原理 * B 树中所有的叶节点都在同一层 * 2-3 树是 B 树的一种特例 * 有两个子节点的节点叫做二节点 * 有三个子节点的节点叫做三节点 * 二节点要么有两个子节点，要么没有子节点 * 三节点要么有三个子节点，要么没有子节点 * 2-3 树有二节点和三节点 2 种情况 * 2-3-4 树有二节点、三节点和四节点 3 种情况 * 添加新节点 * 如果叶节点无法在同一层 * 先向上一层拆解 * 如果现有层都满了，则增加一层 # 60. B 树和 B+ 树原理 ## 概念 * 2-3 树、2-3-4 树、2-3-4-5 树，等等，统称为 B 树 * B 树中最大节点的数字，称为 B 树的阶 * 2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树 ## B+ 树 * 在 B 树之上的改变 * 非叶节点只存储索引信息，不存储数据 * 叶子节点最右边的指针指向下一个相邻的叶节点 * 所有叶节点组成一个有序链表 * 设计原理 * 更多的索引 --> 更快的查询 # 61. 哈希表概述 * 线性查找 * 逐个对比，数据量大时效率低 * 二分查找： * 效率更高 * 要求数组有序 * 存储位置 <--> 关键字 * 通过散列函数建立对应关系 # 62. 散列函数的设计 * 设计原则 * 计算简单 * 分布均匀 ## 常用方法 * 直接定址法 * 直接把关键字作为存储地址 * 可能有空间分布不均匀的问题 * 如果数字过大，甚至会超出编程语言的有效整数范围 * 数字分析法 * 通过特定规律，将数字转换成更方便存储的格式作为关键字 * 需要事先知道数字的格式 * 如手机号码只存后四位 * 平方取中法 * 将数字平方后取结果中间的数字作为关键字 * 如 13*13 = 169，取中间数字 6 * 取余法 * 对数字取余数作为关键字 * 按预计压缩范围来确定模数 * 随机数法 * 随机数函数产生数字作为关键字 * 一般不用，数字随机，不便归类 # 63. 散列冲突的解决方案 ## 开放地址法 * 遇到冲突时，从当前地址后面查找合适的位置 * 三种方式 * 线性探测法 * 在紧邻的位置放冲突的元素 * 举例 * x 位置已有元素，向后查找 x+1 * x+1 位置有元素，再向后找 x+2 * 问题：元素容易聚集在相邻的内存地址 * 二次探测法 * 第一次探测紧邻的位置 * 第二次探测地址数字的平方 * 举例： * x 位置被占用，向后查找 x+1 * x+1 位置被占用，再向后找 (x+1)^2 * 拓宽了探测步长，元素不容易聚集在一起 * 再哈希法 * 多个散列函数 * 通常 3 个散列函数可以解决大部分的冲突 * 如果仍然有冲突，可以再使用探测法 ## 链地址法 * 将冲突的元素在同个地址上存储为链表形式 * 节点内容：元素本身 * 节点指针：下一个元素的地址 * 优点：存储地址就是散列表计算结果，更为直观 * 实际应用中更多采用链地址法 # 64. 图结构 * 点和线构成 * 顶点 Vertex * 可以存储数据 * 边 edge * 连接顶点，表示点之间的关系 * 邻接顶点 * 两个顶点通过一条边就可以连接 * 路径 * 从某一个顶点出发，经过的所有顶点 * 无向图 * 边没有方向 * 有向图 * 边有方向 * 带权图 * 边加上有意义的值 * 如 A 城市到 B 城市的距离 * A --> B 是一个有向带权图 # 65. 图结构代码实现 ## 图的存储方式 * 链表 * 如果数据是对象，指针很难定义 * 数组 * 用列表存储顶点 * 用邻接表存储顶点之间的关系 * 类似链表的实现 * 节点内容代表顶点 * 指针指向下一个顶点 * 类似矩阵的实现 * 将顶点放到行列式中，任意两个顶点都能在矩阵中找到交叉点 * 用数字表示两个顶点之间的关系 * 如 0 表示不通，1 表示连通 # 66. 图的遍历原理 ## 深度优先 * 顺着路径一直查找，直到路径不通，再返回从第一个分叉的顶点处继续查找 * 栈实现 * 1) A 入栈，A 标记为已访问 * 2) 按顺序查找连接 * A --> B，连通，B 入栈，B 标记为已访问 * B --> C，连通，C 入栈，C 标记为已访问 * C --> D，不通，查找下一个 * C --> E，不通，E 之后没有其他顶点 * C 是栈顶元素，出栈 * B --> D，连通，D 标记为已访问，D 入栈 * D --> E，不通，E 之后没有其他顶点 * D 是栈顶元素，出栈 * B --> E，连通，E 入栈，E 标记为已访问 * E 之后没有其他元素 * E 是栈顶元素，出栈 * B 是栈顶元素，检查 B 有无其他可能的连接 * B 没有其他连接，出栈 * A 是栈顶元素，检查 A 有无其他可能的连接 * A 没有其他连接，出栈 ## 广度优先 * 把一个顶点所有的连接都找出来，再继续下一个顶点 * 队列实现 * 1) A 入队 * 2) 查找 A 的所有连接，按顺序入队 * A --> B，连通，B 入队 * A --> C，连通，C 入队 * A 无其他连接，A 出队 * 3) A 出队后，B 是队首元素，从 B 开始查找 * 4) 重复步骤 2~3，依次查找 B、C、D、E 所有顶点的所有连接 # 67. 图的遍历代码实现 * 1) 从第 0 个顶点开始查找 * 将第 0 个顶点标记为已访问 * 将第 0 个顶点压入栈中 * 2) 遍历顶点数组，按序检查邻近两个顶点之间的连通关系 * 如果邻近顶点连通 * 将目标顶点压入栈中，标记为已访问 * 出发顶点和目标顶点同时后移 1 位 * 如 A --> B 连通 * 将出发顶点从 A 顺延到 B，检查 B --> C 是否连通 * 如果邻近两个顶点不通，出发顶点不变，将目标顶点的指针后移一位 * 如 C --> D 不通，将目标顶点 D 后移一位，检查 C --> E 是否连通 * 3) 如果单条路径检查完毕，则弹出栈顶元素 * 4) 如果栈此时非空，将出发顶点指针指向新的栈顶元素 * 5) 重复执行步骤 2~4，直到栈为空