《啊哈！算法》速读笔记

[JChehe]

基本概念

时间复杂度：

外链：https://www.jianshu.com/p/f4cca5ce055a

空间复杂度

是指一个程序运行所需内存的空间大小，利用程序的空间复杂度可以对程序运行所需要的内存大多少有个预估判断。一个程序的执行除了存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括两部分：

• 固定部分：这部分空间的大小与输入、输出数据的个数多少、数值无关，主要包括指令空间（代码空间）、数据空间（常量、变量）等所占用的空间，这部分属于静态空间。
• 可变空间：这部分空间主要包括动态分配的空间，以及递归栈所需的空间等，该空间大小与算法有关。一个算法所需的存储空间用f(n)表示，S(n)=O(f(n))，其中 n 为问题的规模，S(n) 表示空间复杂度。

第一章——排序

来自：http://bigocheatsheet.com/

最快最简单的排序——桶排序

原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

代码（注：实例代码主要体现算法思路，不进行验证等额外操作）：

function bucketSort(arr) {
  const buckets = []
  const result = []
  const max = Math.max(...arr)
  // 初始化每个桶为 0
  for (let i = 0; i <= max; i++) {
    buckets[i] = 0
  }
  // 计数
  for (let i = 0; i <= max; i++) {
    buckets[arr[i]] += 1
  }
  // 根据每个桶的次数进行输出
  for (let i = 0; i <= max; i++) {
    const bucket = buckets[i]
    for (let j = 0; j < bucket; j++) {
      result.push(i)
    }
  }
  return result
}

let arr = [2, 3, 1, 2, 4, 8]
console.log(bucketSort(arr))

邻居好说话——冒泡排序

基本思想：每次比较两个相邻元素，如果它们的顺序错误则把对它们进行交换。若有 n 个数进行排序，只需将 n-1 个数归位。也就是说要进行 n-1 趟操作。而每趟都需要从第 1 位开始进行相邻两个数的比较，将较小（大）的数往后挪一位，两两比较与挪位，直至最后一个尚未归位的数。

代码：

function bubbleSort(arr, direction = 1) {
  let didSwap = false // 若未发生交换，则直接判定为排序完成
  for (let i = 0; i < arr.length - 1; i++) {
    didSwap = false
    for (let j = 0; j < arr.length - i; j++) {
      let curVal = arr[j]
      let nextVal = arr[j + 1]
      if (curVal < nextVal) {
        arr[j] = nextVal
        arr[j + 1] = curVal
        didSwap = true
      }
    }
    if (!didSwap) {
      return
    }
  }
}

最常用的排序——快速排序

快排之所以比冒泡快，是因为每次交换都是跳跃式的。每次排序的时候设置一个基准点，将小于或等于基准点的数全部放到基准点的左边，将大于或等于基准点的数全部放到基准点的右边。由于总的比较次数与交换次数较少，速度自然就提高了。当然，最坏情况下，仍可能是相邻的两个数进行交换。快速排序是基于“二分”的思想。

代码：

function quickSort(arr, left, right) {
  if (left > right) {
    return
  }
  
  let temp = arr[left]
  let i = left
  let j = right

  while (i !== j) {
    // 顺序很重要，要从右往左找
    while (arr[j] >= temp && i < j) {
      j--
    }
    // 再从左往右找
    while (arr[i] <= temp && i < j) {
      i++
    }
    // 当哨兵i和哨兵j没有相遇时，交换两个数在数组中的位置
    if (i < j) {
      let t = arr[i]
      arr[i] = arr[j]
      arr[j] = t
    }
  }
  
  // 将基准数归位
  arr[left] = arr[i]
  arr[i] = temp

  quickSort(arr, left, i - 1) // 继续处理左边，这是一个递归的过程
  quickSort(arr, i + 1, right) // 继续处理右边，这是一个递归的过程
}

const arr = [1, 5, 8, 4, 2, 10]
quickSort(arr, 0, arr.length - 1)

第二章——栈、队列、链表

队列

队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作，称为“出队”，在队列的尾部（tail）进行插入操作，称为“入队”。当队列中没有元素时（即head==tail），称为空队列。即遵循“先进先出”（First In First Out）原则。

数据结构

struct queue {
  int data[100]; // 队列的主体，用于存储内容
  int head; // 队首
  int tail; // 队尾
}

栈

栈限定为只能在一端进行插入和删除操作的数据结构。

栈的实现只需要一个一维数组和一个指向栈顶的变量 top。我们通过 top 来对栈进行插入和删除操作。

案例：回文。

回文：正读反读均相同的字符序列。

判断是否是回文：将当前栈中的字符依次出栈，看看是否与 mid 之后的字符一一匹配。

栈还可以用来进行验证括号的匹配。

第三章——枚举！很暴力

采用暴力枚举的时候也需要仔细分析问题，我们只是将枚举 C 改为通过 A + B 来算出 C，就将 O(N^3) 的算法优化到了 O(N^2)。

第四章——万能的搜索

深度优先搜索（Depth First Search，DFS）

关健在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。

深度优先搜索的基本模型：

void dfs(int step) {
  判断边界
  尝试每一种可能 for (i = 0; i < n; i++) {
    继续下一步 dfs(step + 1)
  }
  返回
}

广度优先搜索（Breadth First Search，BFS）

1. 首先将根结点放入队列中。
2. 从队列中取出第一个结点，并检验它是否为目标。
   • 如果找到目标，则结束搜索并回传结果。
   • 否则将它所有尚未检验过的直接子结点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
4. 重复步骤2。

着色法

以某个点为源点对其邻近的点进行着色。

问：地图红有多少个独立的小岛？
答：只需对地图上的每个大于 0 的点都进行一遍深度优先搜索即可。其实这就是求一个图中独立子图的个数。这个算法就是鼎鼎大名的 Floodfill 漫水填充法（也称种子填充法）。

Floodfill 在计算机图形学中有着非常广泛的应用，比如图像分割、物体识别等等。实际应用：Windows 的“画图”软件的油漆桶工具、Photoshop 魔法棒选择工具等。

第五章——图的遍历

图的存储

图的邻接矩阵存储法：数组中第 i 行第 j 列表示的就是顶点 i 到顶点 j 是否有边。1 表示有边，∞ 表示没有边，这里我们将自己到自己（即 i 等于 j）设为 0。该二维数组沿主对角线对称，因为这个图是无向图。

图的邻接矩阵存储法

深度优先遍历的主要思想：首先以一个未被访问过的顶点作为起始点，沿当前顶点的边做到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有顶点都被访问过。

广度优先遍历的主要思想：首先以一个未被访问过的顶点作为起始点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。

第七章——开启“树”之旅

树和图的区别？
树其实就是不包含回路的连通无向图。

树的特性：

1. 一棵树中任意两个结点有且仅有唯一一条路径连通。
2. 一棵树如果有 n 个结点，那么它一定恰好有 n - 1 条边。
3. 在一棵树中加一条边将会构成一个回路。

术语：

• 根结点：没有父结点的结点。一棵树有且只有一个根结点。
• 叶结点：一个结点没有子结点。
• 内部结点：一个结点既不是根结点也不是叶结点。
• 深度：从根到该结点的层数（根为第一层）。

树的应用场景：足球世界杯的晋级图、家族的族谱图、公司的组织结构图、书的目录、操作系统（Windows、Linux、Mac）的目录。

二叉树：每个结点最多有两个子结点。
满二叉树：一棵深度为 h 且有 2^h - 1 个结点的二叉树。二叉树中每个内部结点都有两个子结点。所有叶结点均有同样的深度。
完全二叉树：若设二叉树的高度为 h，除第 h 层外，其他各层（1~h-1）的结点都达到最大个数，第 h 层从右向左连续缺若干个结点。也就是说如果一个结点有右子结点，那么它一定也有左子结点。