使用VitePress搭建的文档网站

Appearance

部分数据结构和算法笔记 ​

哈希表与数组的对比 ​

  1. 数组进行插入操作时效率比较低
  2. 数组进行查找操作的效率
    1. 如果是基于索引进行查找操作效率非常高
    2. 基于内容查找效率非常低
  3. 删除操作效率也不高 因为删除了之后需要将后续的移动位置

哈希表扩容的思想

  1. 为什么要扩容

    1. 目前我们是将所有的数据项放在长度为 7 的数组中的
    2. 使用的是链地址法，loadFactor可以大于 1，所以这个哈希表可以无限制的进行插入新数据
    3. 随着数据量的增多，每一个 index 对应的 bucket 会越来越长，也就造成效率的降低
    4. 在合适的情况对数组进行扩容

  2. 如何进行扩容

    1. 可以将容量增大两倍
    2. 但是这种情况下，所有的数据项一定要同时进行修改（重新调用哈希函数，）
    3. 这是一个耗时的过程，但是如果数组需要扩容，那么这个过程是必要的

  3. 什么情况下扩容

    1. 比较常见的是loadfactor>0.75的时候进行扩容

判断一个数是否是质数

jsx
const p = (num) => {
  for (let i = 2; i < num - 1; i++) {
    if (num % i === 0) {
      return false
    }
  }
  return true
}

为什么要使用树结构来保存数据呢？ ​

树结构和数组/链表/哈希表对比起来有什么有点？

数组链表
优点
根据下标值访问的效率很高插入和删除操作的效率很高
但是如果我们希望根据元素来查找对应的位置呢？
比较好的方法是先对数组进行排序，再进行二分查找
缺点
需要先对数组进行排序，生成有序数组，才能提高查找效率查找效率很低
对数组进行插入和删除时，有大量位移操作，效率很低即使插入和删除效率很高，但是如果要插入的是再中间位置，还是需要从头先找到对应的数据

哈希表 ​

优点

  • 插入/查询/删除的效率很高 缺点
  • 空间利用率不高，底层使用的是数组，并且某些单元也是没有被利用的
  • 哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素
  • 不能快速找出哈希表中的最大值或者最小值

树结构 ​

  • 不能说树结构比其他结构都要号，因为每种数据结构都有自己特定的应用场景
  • 但是树结构确实综合了上面的结构的优点 而且为了模拟某些场景，我们使用树结构会更方便
  • 因为树结构的非线性，可以表示一对多的关系
  • 比如文件的目录结构

树的术语 ​

  • 树：n >= 0 个节点构成的有限集合 当 n = 0 时，称为空树
  • 对于任何一棵非空树 n > 0 ，具备以下性质
    • 树中有一个称为 根的特殊节点，用 r 表示
    • 其余节点可分为 m(m>0)个互不相交的有限集合 t1，t2，每个集合本身又是一棵树，称为原来的树的子树
  1. 节点的度：节点的子树个数
  2. 树的度：树的所有节点中最大的度数
  3. 叶节点：度为 0 度节点
  4. 父节点
  5. 子节点
  6. 兄弟节点
  7. 路径和路径长度
  8. 节点的层次：规定根节点在 1 层，其它任一节点的层数是其父节点的层数加 1
  9. 树的深度：树中所有节点中最大层次

二叉树的特性 ​

二叉树有几个重要的特性，在笔试题中较为常见：

  • 一个二叉树第 i 层的最大节点数为：2^(i-1),i>=1
  • 深度为 k 的二叉树有最大节点总数为：2^k-1,k>=1
  • 对于任何非空二叉树 t，若 n0 表示叶节点的个数，n2 树度为 2 的非叶节点个数，那么两只满足关系 n0 = n2+1

了解 ​

  • 完美二叉树，也称为满二叉树
  • 在二叉树中，除了最下层的叶节点外，每层节点都有 2 个子节点；
  • 完全二叉树
    • 除二叉树最后一层外，其它各层的节点数都达到最大个数
    • 且最后一层从左向右的叶节点连续存在，只缺右侧若干节点
    • 完美二叉树是特殊的完全二叉树

二叉树的存储 ​

二叉树的存储方式是数组和链表； 如果是完全二叉树，使用数组是可以的，但是如果是非完全二叉树，使用数组，则会造成资源的浪费； 二叉树最常见的方式还是使用链表存储

  • 每个节点封装成一个 Node，Node 中包含存储的数据，左节点的引用，右节点的引用。

二叉搜索树 ​

  • 二叉搜索树是一棵二叉树，可以为空
  • 如果不为空，满足以下性质
    • 非空左子树的所有健值小于其根节点的键值
    • 非空右子树的所有键值大于其根节点的键值
    • 左、右子树本身也是二叉搜索树

二叉搜索树的特点 ​

  • 相对较小的值总是保存在左节点上，相对较大的值保存在右节点上

树的遍历 ​

  • 遍历一棵树是指访问树的每个节点，也可以对每个节点进行操作，例如进行简答的打印
  • 树和线性结构不同，线性结构通常是从前到后的顺序遍历
  • 树的遍历主要是下面几种
    1. 先序
    2. 中序
    3. 后续
  • 树的递归遍历 就是函数栈的调用

先序遍历 ​

  1. 访问根节点
  2. 先遍历左子树
  3. 再遍历其右子树

中序遍历 ​

  1. 遍历其左子树
  2. 访问根节点
  3. 遍历其右子树

后续遍历 ​

  1. 遍历其左子树
  2. 遍历其右子树
  3. 访问根节点

二叉搜索树搜索 ​

  1. 获取节点
  2. 循环搜索 key
js
search(key) {
  // 1. 获取跟节点
  let node = this.root
  // 2. 循环搜索key
  while (node !== null) {
    // 如果要搜索的节点比当node小
    if (key < node.key) {
      // 那就将node.left赋值给node
      node = node.left
    } else if (key > node.key) {
      // 反之亦然
      node = node.right
    } else {
      // 如果相等，就说明搜索成功
      console.log(node)
      return true
    }
  }
  // 3. 没有找到
  return false
}

二叉搜索树的删除 ​

删除节点要从查找要删除的节点开始，找到节点后，需要考虑三种情况，

  1. 该节点上叶节点（没有子节点，比较简单）
  2. 该节点有一个子节点（也相对简单）
  3. 该节点有两个子节点（情况比较复杂）

从删除入手：

  1. 查找要删除的节点，如果没有找到，不需要删除
  2. 找到要删除的节点，
    • 删除叶子节点
    • 删除只有一个子节点的节点
    • 删除有两个子节点的节点

删除两个子节点的节点的寻找规律 如果要删除的节点有两个子节点，甚至子节点还有子节点，这种情况下，我们需要从下面的子节点中找到一个节点，来替换当前节点；

  1. 比 current小一点的节点，一定是 current左子树的最大值
  2. 比 current大一点的节点，一定是 current右子树的最小值

在二叉搜索树中，这两个特别的节点，有两个特别的名字：

  • 比 current小一点的节点，称为 current 节点的前驱
  • 比 current大一点的节点，称为 current 节点的后继

二叉搜索树的删除总结 ​

二叉搜索树的删除非常棘手 ​

因为它非常复杂，一些程序员都尝试着避开删除操作

  • 部分人的做法是在 Node 类中添加要给布尔值，
  • 要删除一个节点就让此字段设置为true
  • 进行其他操作之前，会判断这个节点是否标记删除
  • 这样相对简单，并且删除不会改变原有的结构
  • 但是在二叉搜索树的存储中，还保留着那些本该被删除的节点
  • 但是这个方法会造成很大的空间浪费，特别是针对数据量较大的情况
  • 而且作为程序员要学会通过这些复杂的操作，锻炼自己的逻辑

二叉搜索树的缺陷 ​

  • 如果插入的数据是有序数据，例如 9-8-7-6-5-4-3，就会使得所有的数据分布在节点的左侧，

非平衡树 ​

  • 比较好的二叉搜索树，应该是左右分布均匀的；
  • 但是插入连续数据后，分布的不均匀，称这种树为非平衡树
  • 对于一颗平衡二叉树来说，插入/查找等操作的效率是O(logN)
  • 对于一颗非平衡二叉树，相当于编写了一个链表，查找的效率就变成了O(N)

红黑树的规则 ​

  1. 节点上红色或黑色
  2. 根节点上黑色
  3. 每个叶子节点都是黑色的空节点
  4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
  5. 从任一节点到其每个叶子到所有路径都包含相同数目的黑色节点

变色

旋转

图的术语 ​

顶点：图中的一个节点

边：顶点和顶点之间的连线

相邻顶点：由一条边连接在一起的顶点称为相邻顶点

度：一个顶点的度是相邻顶点的数量

路径：是顶点 v1,v2...vn 的一个连续序列

简单路径：不包含重复顶点的路径

回路：第一个顶点和最后一个顶点相同的路径

无向图：所有的边都没有方向

有向图：所有的边都有方向

无权图：边是没有权重的

有权图：边是有权重的

图的表示方式 ​

一种比较常见的表示图的方式：邻接矩阵

  • 让每个节点和一个整数相关联，改整数作为数组的下标值
  • 使用一个二维数组来表示顶点之间的连接

常用排序算法 ​

简单排序:冒泡-选择-插入 高级排序:希尔-快速

冒泡排序的思路 ​

效率相对其他的效率较低,但是较为简单

思路:

  • 对未排序各元素从头到尾依次比较相邻的两个元素大小关系
  • 如果左边的队员高,则两队员交换位置
  • 向右移动一个位置,继续比较下面的的两个队员
  • 当走到最右端时,最高的队员一定在最右边
  • 按照这个思路,从最左端重新开始,这次排到倒数第二个位置即可
  • 依此类推,就可以完成数据的排序

选择排序的思路 ​

选择排序对冒泡排序进行改进

  • 将交换的次数由 O(N^2)减少到 O(N)
  • 但是比较多次数依然是 O(N^2)

思路：

  • 选定第一个索引位置，然后和后面元素依次比较
  • 如果后面的位置，小于第一个索引位置，则交换位置
  • 经过一轮的比较后，可以确定第一个位置是最小的
  • 然后使用同样的方法把剩下的元素逐个比较
  • 可以看出，选择排序第一轮会选出最小值，第二轮会选出第二小的值，以此类推

插入排序的思路 ​

插入排序是简单排序中效率最好的的一种

插入排序的和核心是局部有序，那局部有序是？ 例如在一个队列中，选择其中一个作为标记的队员 这个被标记的队员左边的所有队员已经是局部有序的 这意味着，一部分人是按顺序排列好的，有一部分还没有顺序

希尔排序 ​

希尔排序相当于是插入排序的升级版

快速排序 ​

快速排序其实是冒泡排序的升级版