For full text search please use the '?' prefix. e.g. ? Onboarding

《Hello算法》学习笔记

电子书地址

原码、反码、补码

  • 原码：符号位+真值
  • 反码：正数的反码是其本身，负数的反码是符号位不变，其余位取反
  • 补码：正数的补码是其本身，负数的补码是反码+1(所以存在溢出的可能)

负数的原码不能直接用于计算, 比如1 + (-2):

  • 1的原码是0000 0001
  • -2的原码是1000 0010
  • 1 + (-2) = 0000 0001 + 1000 0010 = 1000 0011 = -3

而补码可以解决这个问题:

  • 1的补码是0000 0001
  • -2的补码是1111 1101
  • 1 + (-2) = 0000 0001 + 1111 1101 = 1111 1110
  • 对补码取反得原码(同样, 符号位除外): 1000 0001= -1

此外, 0有+0和-0两种表示, 但补码却是唯一的, 即0000 0000

  • 正零: 0000 0000
  • 负零补码: 1000 0000 -> 1111 1111 -> 10000 0000, 多余的1位溢出了, 这个字节里与正零完全一致

浮点数编码

记一个 32 比特长度的二进制数为： b31b30b29...b1b0b_{31}b_{30}b_{29}...b_{1}b_{0} 根据 IEEE 754 标准，32-bit 长度的 float 由以下三个部分构成。

  • 符号位S：占 1 位, 对应b31b_{31}
  • 指数位E：占 8 位, 对应b30b29...b23b_{30}b_{29}...b_{23}
  • 分数位N ：占 23 位, 对应b22b21...b0b_{22}b_{21}...b_{0}

计算方法:

val=(−1)S×2E−127×(1+N223)\tt val = (-1)^S \times 2^{E-127} \times (1 + \frac{N}{2^{23}})

注: 数字从低位到高位是从右到左的, 而内存是从低地址到高地址的, 低位存在低地址, 高位存在高地址, 那么么在内存中, 数字是反着存的, 这就是小端序 (但如果只是文字描述, 完全取决于描述者), 比如上述图片中计算方法可知就是按大端序存的, 即内存低位存数字高位, 但是保证了内存中的顺序与人眼看到的顺序一致.

所以float能存的最大数是2254−127×(2−2−23)≈3.4×10382^{254-127} \times (2 - 2^{-23}) \approx 3.4 \times 10^{38}

字符编码

  • ASCII, 0-127
  • Unicode
    • 将所有字符存储为等长的编码
    • 变长编码(UTF-8)

UTF-8编码

  1. 长度为1字节的字符, 最高位为0, 后面7位为字符编码
    • ASCII在Unicode字符集中占前128个码点, 所以是兼容的(即二进制不变)
  2. 长度为N字节的字符, 最高位为N个1(与后N-1个字节最高位为1), 所以看最高位即可知道用了几个字节(所以是变长), 然后在后面跟"0"
    • 其后面的每个字节最高位也都设为"10"(即最高位是1, 后面跟个0, 与第一个字节的区别就在于是N个1还是1个1)

所以看"法"字:

  1. 用了三个字节
  2. 第一个字节就一定是三个1, (即1110), 后面两个字节最高位都是10
  3. 11100110 10110011 10010101

数组和链表, 列表

  • 数组是连续的内存空间, 所以可以随机访问, o(1)
    • 不需要额外的空间来存储链表节点间的引用（指针），因此空间效率更高。
    • 但连续空间会导致内存浪费
    • 扩容需要时间成本
    • 具有更高的缓存命中率
  • 链表是离散的内存空间, 所以不能随机访问, 只能顺序访问 o(n)
  • 数组插入和删除元素需要移动后续元素, o(n)
    • 链表只需要修改指针, o(1), 但是如果是先查询再增删, 也是o(n)
  • 链表有几个扩展
    • 双向链表: 每个节点有两个指针, 一个指向前一个节点, 一个指向后一个节点
    • 循环链表: 最后一个节点的指针指向第一个节点
    • 跳表: 每个节点有多个指针, 指向后面的节点, 可以快速跳过一些节点, o(logn)
  • 链表用指针, 所以不需要存储同类型元素
  • 数组需要根据类型算偏移量, 所以需要存储类型元素
  • 列表不是数组, 可由动态数组或链表实现
  • 列表增删元素仍然是o(n)

单调队列

以k为步长滑动窗口, 找出每一次滑窗的最大/小值: 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

以单调递增为例, 我们用浮力做比较:

  1. 单调递增希望队头和队尾分别为最小最大值
  2. 如果一个新物体较重, 那么把它扔进池子里, 必然会沉到底, 此时有两种选择:
    1. 比它轻的自然浮上去
    2. 比它轻的都会它压扁, 从池子里消失, 我们选择这个方案

现在来实现上面那个题, 而不是每3个数组里做一次遍历:

  1. 放入1 => [1]
  2. 放入3, 3比1重, 1被3压扁, 消失 => [3]
  3. 放入-1, -1比3轻, 浮起来 => [3, -1]
  4. 放入-3, -3比-1轻, 浮起来 => [3, -1, -3]
  5. 放入5, 同样, 沉到沉的位置, 此处就是最底部 => [5]
  6. 放入3, 3比5轻, 浮起来 => [5, 3]
  7. 放入6, 沉到底 => [6]
  8. 放入7, 沉到底 => [7]

题目感兴趣的是每一步的最大值, 我们直接取每一步的队头元素即可:[3, 3, 5, 5, 6, 7] (从第三步起)

注意, 因为步长原因, 所以在往后走的过程中, 队头的元素可能已经不在步长范围内了, 就需要手动删除, 而且这还是个递归的过程, 删除后的新队头也可能超出步长了.

function maxSlidingWindow(nums, k) {
    let res = [];
    let queue = [];
    for (let i = 0; i < nums.length; i++) {
        // 队头元素已经不在窗口里了
        if (i - queue[0] >= k) {
            queue.shift();
        }
        // 队尾元素比当前元素小, 那么它不可能成为最大值, 消除掉
        while (queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        // 当前元素入队
        queue.push(i);
        // 队头元素就是当前窗口的最大值
        if (i >= k - 1) {
            res.push(nums[queue[0]]);
        }
    }
    return res;
}

单调队列有什么用? 任何需要用到滑动窗口里的极值的场景, 比如:

跳房子, 每个格子有特定的分数: score = [1, -1, -6, 7, -17, 7], 每次最多跳k步, 求跳到最后一步的最大分数.

这是一个典型的动态规划问题, 跳到第i格有k种方法, 你需要的是其实是得分最高的: dp[i] = max(dp[i - 1], dp[i - 2], ..., dp[i - k]) + score[i], 但是每次都遍历的话, 时间复杂度是o(nk), 所以可以用单调队列优化, 因为这个maxblablabla的, 正好是我们的例题中的场景, 这样我们先把这样一个队列求出来, 在计算状态转移公式的时候, 直接取队头即可.

哈希表

哈希表仅凭一个key就能定位在表中的位置, 如果是用数组来实现的话: 可见,核心是有一个能将key转化成index的函数, 即哈希函数

哈希冲突

输入空间大于输出空间, 必然有会产生相同的哈希值, 即哈希冲突:

  • 扩容: 能降低冲突频率, 但是扩容会产生一系列迁移和重计算存储位置的消耗, 非必要不要采用扩容的方案
    • Redis的rehash(每次插入键值对时，都会检查是否需要扩容。如果满足扩容条件，则进行扩容。)
    • java中 元素数据/桶数量 > 0.75时, 扩容为原来的两倍,(load factor)
  • 链式地址(separate chaining):
    • 在一个桶位内存多个元素, 用链表存储(简单模拟的话也可以用列表)
    • 查找到数组中对应位置后, 再遍历链表(或列表)
    • 缺点:
      • 查找效率变低(o(n), 可转为AVL树或红黑树等平衡树, 查找效率为o(logn))
      • 占用空间变大
  • 开放寻址(open addressing):
    • 当发生冲突时, 按一定规则寻找下一个空位, 直到找到空位为止(如线性探测法, 二次探测法, 双重散列法)
    • 线性探测: 如果发现当前位置有元素, 则不断以预设的步长寻找下一个空位
      • 容易产生聚集现象, 只要数组中连续的区域越长, 那么它可能产生的冲突就越多, 这样会产生更长的区域, 恶性循环
      • 根据步长往后查询时, 如果碰到空桶, 就会认为数组截止了, 所以删除元素不能真删除, 而是打个标tombstone
      • 但是就会出现tombstone过多的问题, 于是可以在查询过程中标记第一个墓碑, 在查询结束后, 把当前值与墓碑交换位置
        • 影响的是下次查询, 而非本次查询
        • 查询次数越多, 从0开始的索引拥有的墓碑就越少,即无效桶就越少
    • 二次探测(平方探测):
      • 仍然是线性探测, 线性探测的步长为i, 二次探测的步长为i^2
      • 一定程度上解决聚焦效应, 但是会存在浪费很多桶位的情况, 因为平方值不可能达到每个索引位
    • 双重散列(多次哈希): 即依次使用用多个哈希函数f1(x),f2(x),f3(x)...f_1(x),f_2(x),f_3(x)...进行探测, 直到找到一个空桶
      • 与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

真实世界的选择:

  • Python 采用开放寻址。字典 dict 使用伪随机数进行探测。
  • Java 采用链式地址。自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树以提升查找性能。
  • Go 采用链式地址。Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能。

二叉树

  • 广度优先遍历, 就是按层遍历
    • 使用队列实现层遍历, shift出来的时候丢到数组里
  • 深度优先遍历有三种方式 
    * 前序遍历: 先访问根节点, 然后访问左子树, 最后访问右子树
* 中序遍历: 先访问左子树, 然后访问根节点, 最后访问右子树
* 后序遍历: 先访问左子树, 然后访问右子树, 最后访问根节点

/* 前序遍历 */
function preOrder(root) {
    if (root === null) return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.push(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
function inOrder(root) {
    if (root === null) return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.push(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
function postOrder(root) {
    if (root === null) return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.push(root.val);
}

用数组表示完美二叉树:

  • 意思是你知道了根节点的位置, 就可以知道左子树和右子树的位置.
  • 但是完美二叉数相当少, 还有一种"完全二叉树"的概念, 就是除了最后一层外, 其他层都是满的, 最后一层从左到右排列, 这种二叉树也可以用数组表示

所以, 用线性数组能表达非线性的(完美/完全)二叉树的原因是, 有确定的计算公式, 假定当前元素的索引为i:

  • 左子树索引为2×i+12 \times i + 1
  • 右子树索引为2×i+22 \times i + 2
  • 父节点索引为⌊i−12⌋\lfloor \frac{i - 1}{2} \rfloor (表示下取整)

二叉搜索树

就是满足特定条件方便搜索的二叉树:

  • 左子树的所有节点值都小于根节点值
  • 右子树的所有节点值都大于根节点值
  • 左右子树也都是二叉搜索树

满足了此条件的树, 用中序遍历, 会得到自然升序的数组, 所以: 如果要删除一个元素, 就要用中序遍历找到下一个值, 然后替换掉要删除的元素 上例中, 删掉4, 显然需要用5来替换4的位置, 这个5就能用中序遍历找到

平衡二叉树, AVL树

  • 就是任一节点左右子树高度(叶节点到本节点的"边"的数量)差不超过1的二叉树
  • 节点的平衡因子balance factor定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0
  • AVL树是二叉搜索树 + 平衡二叉树, 即"平衡二叉搜索树"

可以这么理解, 极简情况下, 一个节点左边挂一个, 右边没挂, 那叫正常, 但是左边挂了两个, 右边没挂, 那就叫"失衡"了(所以平衡因子需要大于1才算失衡), 需要想办法把左边的一个挂到右边去, 而且还要保证左小右大的二叉搜索树特性

左边过长(平衡因子大于1)需要右旋 AVL树右旋 有孙子节点的, 需要把孙子节点挂到当前节点的左子树上(右旋挂左节点)

/* 右旋操作 */
#rightRotate(node) {
    const child = node.left;
    const grandChild = child.right;
    // 以 child 为原点，将 node 向右旋转
    child.right = node;
    node.left = grandChild;
    // 更新节点高度
    this.#updateHeight(node);
    this.#updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

右边过长需要左旋

如果用f0f_0表示失衡节点的平衡因子, f1f_1表示其子节点的平衡因子, 有四种旋转方式:

  • LL型: f0>1,f1≥0f_0 > 1, f_1 \ge 0, 右旋
  • RR型: f0<−1,f1≤0f_0 < -1, f_1 \le 0, 左旋
  • LR型: f0>1,f1≤0f_0 > 1, f_1 \le 0, 先左旋再右旋
  • RL型: f0<−1,f1≥0f_0 < -1, f_1 \ge 0, 先右旋再左旋

直接用这个公式去写代码即可. AVL树的插入和删除操作的时间复杂度都是O(logn), 因为每次操作都会重新平衡树(即自变动节点到root执行必要的旋转操作)

所以多用于大型存储, 高频查找, 低频增删的场景

红黑树

红黑树是一种自平衡二叉搜索树, 它通过每个节点增加一个存储位表示节点的颜色, 可以是红色或黑色:

  • 每个节点要么是红色, 要么是黑色
  • 根节点是黑色
  • 每个叶子节点(NIL节点, 空节点)是黑色
  • 如果一个节点是红色的, 则它的两个子节点都是黑色的
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

AVL树追求绝对平衡, 红黑树追求大致平衡

堆

  • 堆是完全二叉树(即只有最后一层不满, 且所有元素靠左)
  • 根节点值要么大于所有子节点(大顶堆), 要么小于所有子节点(小顶堆)
    • 所以堆不是搜索树, 因为左右子节点值没有大小约束
  • 堆是实现优先队列Priority Queue的基础数据结构, 相比线性队列, 它可以做到按你控制的权重出列
// Swift 的 Heap 类型同时支持最大堆和最小堆，且需要引入 swift-collections
var heap = Heap<Int>()

/* 元素入堆 */
heap.insert(1)
heap.insert(3)
heap.insert(2)
heap.insert(5)
heap.insert(4)

/* 获取堆顶元素 */
var peek = heap.max()!

不管你的插入顺序是怎样的, 堆顶元素始终是最大(或最小)的, 因为堆会自动调整顺序, 使堆顶元素始终是最大(或最小)的, 显然, 插入的时间复杂度是o(log(n))

入堆的过程:

  • 添加到堆底
  • 与parent比, 逐渐向上冒泡

所以如果有一个无序数组, 通过对每一个元素执行入堆的操作, 就能实现建堆(排序)的目的

堆顶元素出堆复杂一点:

  • 把堆底元素放到堆顶
  • 与左右子节点比,如果左右子节点都比自己大(或小), 就选大的(或小的)子节点, 与自己交换位置, 重复此过程, 直到堆顶元素比左右子节点都大(或小)
  • 向下冒泡

所以, 使用堆结构模拟的优先队列，每次入队都会触发上浮操作，每次出队都会触发下沉操作，但是上浮和下沉的次数最多就是完全二叉树的深度，而完全二叉树的深度为O(LogN)，也就是说堆结构维护的优先队列每次入队和出队的时间复杂度为O(LogN)，这要比使用有序数组维护的优先队列的入队出队的时间复杂度O(n)，大大提升了效率。

参考这篇文章实现一个自己的堆: column0 | column1 ------- | ------- push() | 元素入堆 pop() | 堆顶元素出堆 peek() | 访问堆顶元素 size() | 获取堆的元素数量 | isEmpty() | 判断堆是否为空 left(i) | 获取索引为i的节点的左子节点索引 right(i) | 获取索引为i的节点的右子节点索引 parent(i) | 获取索引为i的节点的父节点索引 siftUp(i) | 元素上浮 siftDown(i) | 元素下沉

// 实现一个堆
class Heap {
    constructor() {
        this.heap = [];
    }
    // 元素上浮
    siftUp(index) {
        while (index > 0) {
            const parentIndex = this.parent(index);
            if (this.heap[index] <= this.heap[parentIndex]) {
                break;
            }
            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    // 元素下沉
    siftDown(index) {
        while (this.left(index) < this.heap.length) {
            let maxIndex = this.left(index);
            const rightIndex = this.right(index);
            if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[maxIndex]) {
                maxIndex = rightIndex;
            }
            if (this.heap[index] >= this.heap[maxIndex]) {
                break;
            }
            this.swap(index, maxIndex);
            index = maxIndex;
        }
    }
    // 元素入堆
    push(value) {
        this.heap.push(value);
        this.siftUp(this.heap.length - 1);
    }
    // 堆顶元素出堆
    pop() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return top;
    }
    // 访问堆顶元素
    peek() {
        return this.heap[0];
    }
    // 获取堆的元素数量
    size() {
        return this.heap.length;
    }
    // 判断堆是否为空
    isEmpty() {
        return this.heap.length === 0;
    }
    // 获取索引为i的节点的左子节点索引
    left(index) {
        return index * 2 + 1;
    }
    // 获取索引为i的节点的右子节点索引
    right(index) {
        return index * 2 + 2;
    }
    // 获取索引为i的节点的父节点索引
    parent(index) {
        return Math.floor((index - 1) / 2);
    }
    // 交换堆中两个元素的位置
    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
}

top k问题

就是从n个元素中, 找出前k个最大(或最小)的元素, 比如说从1000个数字中找出前10个最大的数字

  • 如果k远小于n, 可以用排序, 然后取前k个, 时间复杂度是O(nlogn)
  • 如果k接近n, 可以用堆, 维护一个大小为k的堆, 时间复杂度是O(nlogk)
    • 其实就是从第k+1个元素起, 都跟堆顶比, 比它大就入堆, 比它小就不管, 这样堆顶始终是最大的k个元素
  • 如果k接近n, 也可以用快速排序的思想, 每次递归都把中间值放到正确的位置, 然后判断中间值的位置, 如果是k, 则找到了, 如果小于k, 则在右半部分继续递归, 如果大于k, 则在左半部分继续递归, 时间复杂度是O(n)

图

  • 相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高
    • 树是一对多, 图是多对多
  • 根据边是否具有方向，可分为无向图（undirected graph）和有向图（directed graph）
    • 无向图就是双向图
  • 根据所有顶点是否连通，可分为连通图（connected graph）和非连通图（disconnected graph）
    • 边通图一个顶点能到达其它任何一个顶点
  • 通常把连线标识为1, 如果标识为小于1的数, 则理解为权重
  • 术语:
    • 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。
    • 路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。
    • 度（degree）：一个顶点拥有的边数, 根据方向有入度和出度。
  • 表示:
    • 邻接矩阵, 用行和列的相关的点来标识是否相连
      • 查询很快, o(1)
      • 但不相连的顶点也都占了内存
    • 邻接表, 类似解决Hash冲突的链接地址, 把有关联的顶点全跟到一个链表上去
      • 查询很慢, o(n), 但是也可惜用AVL树优化到o(logn)

搜索

二分查找

  • 每次排除一半O(log2n)O(log_2n)
  • 仅适用于有序数据, 如果人为增加一次排序, 而不如在排序中直接查找
  • 仅适用于数组, 因为需要跳跃式访问元素, 只有数组有这个特性

给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。

哈希优化策略

  • 其实就是用target依次减每个元素, 看结果是否在数组中, 如果在, 则找到了
  • 但是每个"结果是否在数组中", 都是一个o(n)的操作, 所以总的时间复杂度是o(n^2), 这就是穷举法, 也可以理解为暴力法
  • 所以换个思路, 不去看结果在数组中, 而是用一个字典(map)把比过的数值和索引存起来, 比如{3, 5}, 表示元素3, 在索引5
  • 这样, 一旦17-9=8, 这个8在字典里(o(1)), 那么8和9就是需要找到值, 因此时间复杂度是o(n), 即遍历一轮即能找到 -> 用空间换时间(多了个map)

排序

选择排序

每次(n)选出剩余区间里的最小一个元素(n), 与最前面一个元素互换 (O(n2)O(n^2))

冒泡排序

两两对比, 不断交换, 与选择排序的区别就是相邻位不等就替换, 还是存一个极值, 与首位替换, 思路细微差别, 复杂度是一样的

插入排序

  • 就跟整理一副牌是一样的, 每次捡起一张牌(n), 插到已排序(即手上)牌堆里的正确位置(n) →O(n2)\to O(n^2)
  • 比前两种事实上要快一些, 因为前几轮的插入和排序只有几个元素, 并没有且不需要完整遍历, 只需要在已排序的牌堆里找到正确的位置即可

实际上，许多编程语言（例如 Java）的内置排序函数采用了插入排序，大致思路为：对于长数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

快速排序

  • 先任选一个pivot, 将数组分成左右两块(pivot不在内), 然后递归对左右两块做相同的操作, 直到数组长度为1, 即完成排序
    • 方法是从右往左搜小数(因为期望右边的都是大数), 从左往右搜大数, 然后交换, 直到左右指针相遇
  • pivot的选取可以优化, 避免每次选到最差的情况, 比如每次选到了最大/小的元素, 那么每次都会分成一块空, 一块n-1, 这样复杂度就变成了o(n^2)
  • 可以从头, 尾, 中各出一个值, 选其中位数做pivot, 保证至少两边都有元素

交换元素得到左右两个数组的方法不如用遍历一遍直接生成左右两个数组的方法, 更直观:

def q_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr.pop()
    left  = [item for item in arr if item <= pivot]
    right = [item for item in arr if item > pivot]
    return q_sort(left) + [pivot] + q_sort(right)

做同样是一个O(n)级别的遍历, 当然具体下来是2n, 效率有一定消耗, 但是在小数据量上效果已经相当好了, 同时, 它是演示快排的最佳代码, 因为够简单, 但是真正的快排是有高级用法的, 通过不断压缩边界来实现更快地收敛, 参考几种主流排序算法

归并排序

同样, 参考上篇文章, 这里回忆下关键点:

  1. 先拆分, 拆到最小, 然后合并, 合并的时候排序
  2. 合并的时候是两两合并, 永远比较两个数组的最前一位, 因为合并过程中, 每个数组都是有序的, 所以比较最前一位即可, 如此往复

比如1,7,10, 2,9,12, 先取到1, 剩下的数据是7打头和2打头, 自然取的是2, 然后是7, 9, 10, 12, 然后这个1,2,7,9,10,12继续与别的组用同一种方法合并, 直到合并到只剩一个数组, 即完成排序

堆排序

简版:

  1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
  2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

因为出堆是需要把堆底元素放到堆顶, 然后向下冒泡的, 这样会把下方的小元素持续冒上来.

桶排序

  • 解决的不是排序问题, 而是数据量过大, 怎么切分的问题
  • 但是对于类别有固定值的, 比如年龄, 性别, 评分, 这种数据(或区段), 桶排序可以非常高效地切分数据
  • 小量数据, 可以把所有取值可能性摊开成为桶, 遍历的值直接入桶:
    • 计数排序, 从最小值摊开到最大值, 每个值一个桶
    • 基数排序, 0到9, 共十个桶

计数排序

  • 先遍历数据找到最大值m, 这样, 你就可以建一个数组, 有m+1个元素, 那么它的索引就是对应的数值(0~m)
  • 然后遍历一遍原数组, 把每个元素放到对应索引的位置上, 这样就完成了排序
  • 如果要优化, 或者最小值不是0, 可以顺便把最小值也同时遍历出来, 这样区间就成了min~max
  • 需要知道有空间浪费

如果知道数据范围, 以及数据量确实不大, 计数排序几乎就是直接得出结果

基数排序

  • 如果不考虑尾数, 那么按最高位排序即可, 比如8000一定大于7000, 不管百十千位是什么
  • 但是如果有两个千位是8的数, 我们就要看下一位
  • 所以, 我们需要从最低位开始, 依次按位排序, 直到最高位, 这样就完成了排序
  • 因为高位是最后排的, 所以打乱的之前低位排好的顺序是不会打乱最终的大小的, 低位因为先排好了, 而算法又是按顺序遍历的, 所以可以保证高位相同的情况下, 次低位是按数字大小排序的

问题:

即使每次只比一个数字, 但是也要完整地比赛所有数字, 比如是1000个, 我既然要排序, 我何不直接比整个数字大小, 比一次就行了?

那是因为基数排序可以优化, 具体见我上面的参考文章, 简单来说, 就是只按数字排序的话, 是可以用桶排序的, 因为数字千千万万, 桶却只有10个(0-9), 这样你用(O(n))就能把所有数字放到桶里, 而在同一个桶的的数字是不需要排序的, 而如果你真的用别的真排序算法, 那至少是O(log(n))起了. 这样, 基数排序就优化成了O(n)

所以基数排序的核心其实是单个数字排序非常快, 而不是先排低位再排高位这个思路.

分治

  • 分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的时间复杂度，还有利于操作系统的并行优化。
  • 快排, 归并, 堆排, 基数排, 都是分治
  • 时间复杂度为O(log(n))的搜索算法通常是基于分治策略实现的，例如二分查找和树。
    • 本质上暴力搜索每轮只能排除一个选项，而分治搜索每轮可以排除一半选项。

快排里, 选个中值, 再左右各排各的, 这里有个习题, 也是差不多的思路, 已知一个堆, 用前序和中序遍历两种方法得到的序列分别是3, 9, 2, 1, 7和9, 3, 1, 2, 7, 求出这个堆的原始序列(假设数字没有重复)

思路:

  1. 前序遍历是从堆顶开始的, 中序遍历是从堆底左侧开始的, 所以在中序遍历里发现堆顶数字, 那么它左侧就是左子树, 右侧就是右子树
  2. 然后应用递归, 各自重建左右子树, 直到子树长度为1, 即完成重建

所以知道从前序遍历找堆顶, 从中序遍历找左右子树是核心, 不会像无头苍蝇一样找各种规律. 既然能分左右子树了, 想到递归那是顺理成章的事了. 会写快排就能重建堆, 因为只是具体排序方式不一样了而已.

/* 构建二叉树：分治 */
function dfs(preorder, inorderMap, i, l, r) {
    // 子树区间为空时终止
    if (r - l < 0) return null;
    // 初始化根节点(前序确定顶点)
    const root = new TreeNode(preorder[i]);
    // 查询 m ，从而划分左右子树(中序确定左右子树, 从而把子树拿去递归)
    const m = inorderMap.get(preorder[i]);
    // 子问题：构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题：构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
function buildTree(preorder, inorder) {
    // 初始化哈希表，存储 inorder 元素到索引的映射
    let inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}

回溯

  • 回溯算法非常适合用来解决由多个步骤组成的问题，其中每个步骤都有多个选项。
  • 回溯算法通过逐步尝试每一种选择，直到找到一个满足结束条件的解决方案。
  • 如果一种选择怎么样都无法满足条件(剪枝), 则回到上一个条件重新选择(回溯)
  • 回溯算法通常并不显式地对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。

回溯算法通常用于解决组合问题，例如八皇后问题和旅行商问题。

/* 回溯算法框架 */
function backtrack(state, choices, res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (let choice of choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

全排列

基于此框架实现一个全排列:

/* 回溯算法：全排列 I */
function backtrack(state, choices, selected, res) {
    // 当状态长度等于元素数量时，记录解
    if (state.length === choices.length) {
        res.push([...state]);
        return;
    }
    // 遍历所有选择
    choices.forEach((choice, i) => {
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.push(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop();
        }
    });
}

/* 全排列 I */
function permutationsI(nums) {
    const res = [];
    backtrack([], nums, Array(nums.length).fill(false), res);
    return res;
}
  1. 假如从0遍历, 先选择索引0处的值, 并标识索引0已被选
  2. 然后递归自己(把当前状态传过去), 显然又会从0开始遍历
    • 因为索引0已经被选了, 所以跳过, 然后选择索引1处的值, 并标识索引1已被选, 如此往复, 也就是说遍历是通过一个n2n^2的两层循环实现的, 用打标的思路让命中的索引不往往后移动
  3. 索引0后面遍历完了后, 撤销当前选择, 即不选零, 在最外层的循环里, 进入"首选1"的场景, 开始排列

注意, 一个"假如选择了A, 跑完流程, 再撤销选择A, 下一个循环里选择B", 如果这个"选择"没有需要被额外的空间存储, 那么是不需要进行"选择-撤销选择"的过程的, for循环里直接选择B即可

比如爬楼梯问题, 直接把"这次我走1步", 做了后, 走到底, 直接进入下一个选择, "这次我走2次", 并不需要"撤销这次我走1步"这个决定

/* 回溯 */
function backtrack(choices, state, n, res) {
    // 当爬到第 n 阶时，方案数量加 1
    if (state === n) res.set(0, res.get(0) + 1);
    // 遍历所有选择
    for (const choice of choices) {
        // 剪枝：不允许越过第 n 阶
        if (state + choice > n) continue;
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

/* 爬楼梯：回溯 */
function climbingStairsBacktrack(n) {
    const choices = [1, 2]; // 可选择向上爬 1 阶或 2 阶
    const state = 0; // 从第 0 阶开始爬
    const res = new Map();
    res.set(0, 0); // 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res);
    return res.get(0);
}

可以看到, 既没有选择, 也没有回退

N皇后

发现规律仍然是重中之重,

  1. 比如一旦你放了一个元素, 你就标识它为这一列已经被占用, 因为你想遍历的是行, 所以行是不需要打标的
  2. 如图所示, 它也隐含了两个45度摆放的棋盘, 分别在各自的"列"中也占用了, 你要做的就是把这些抽象出来的"列"用一个公式表达出来
  3. 在确定行的时候, 我们遍历列, 直接看这个位置对应的三个"列"是否被占用即可

下面的代码, 难点就在怎么判断两个对角线的列占用情况的数组有多少个, 以及每个位置对应的对应线列索引各是多少, 这两个地方. 

/* 回溯算法：n 皇后 */
function backtrack(row, n, state, res, cols, diags1, diags2) {
    // 当放置完所有行时，记录解
    if (row === n) {
        // ⚠️特别注意这里, 这里深拷贝了, 想想为什么
        // 因为下一行代码就是回溯了, state会恢复
        // 因为这是找"所有解"的问题, 即即使找到了解, 也要状态回退
        res.push(state.map((row) => row.slice()));
        return;
    }
    // 遍历所有列
    for (let col = 0; col < n; col++) {
        // 计算该格子对应的主对角线和次对角线
        // 能得出这两个公式基本就差不多了, 剩下的就是判断这两个数组对应的索引位置是否为true, 和旋转了皇后后去标识为true这两件事了
        const diag1 = row - col + n - 1;
        const diag2 = row + col;
        // 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试：将皇后放置在该格子
            state[row][col] = 'Q';
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 代码跑到这一行, 说明当前的选择无解, 需要回退
            state[row][col] = '#';
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

/* 求解 n 皇后 */
function nQueens(n) {
    // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    const state = Array.from({ length: n }, () => Array(n).fill('#'));
    // 三个关键数组:
    const cols = Array(n).fill(false); // 记录列是否有皇后
    const diags1 = Array(2 * n - 1).fill(false); // 记录主对角线上是否有皇后
    const diags2 = Array(2 * n - 1).fill(false); // 记录次对角线上是否有皇后
    const res = [];

    backtrack(0, n, state, res, cols, diags1, diags2);
    return res;
}

动态规划

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

  1. 爬楼梯问题和费波拉契数列两个问题, 当前解都与前两个状态的解有关, 这就是"更小的子问题"
  2. 这个关系就叫状态转移方程, 比如dpi=dpi−1+dpi−2dp_i = dp_{i-1} + dp_{i-2}
  3. 状态转移方程成立的条件是有初始值: dp0=1,dp1=2dp_0 = 1, dp_1 = 2

如果从顶点往回回溯, 会无数次重复计算dpi−1dp_{i-1}和dpi−1dp_{i-1}, 这样会产生指数或阶乘级的重复计算, 显然, 应该把计算过的值存储起来, 并从小往大, 复用低级别的解

滚动变量

然后, 还有更优化的方案, 既然只与(i-1, i-2)有关, 那么只需要存储这两个值即可, 并且不断变更即可, 这种技巧叫滚动变量:

function climing(n) {
    if (n < 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b]; // 等于向右移了一位, 值就是前两个值的和
    }
    return b;
}

可见, 动态规划一个大特征就是有大量的重叠子问题, 而回溯则基本没有, 因为回溯是暴力穷举

最优子结构

爬楼问题中, 每一个台阶都是等价的, 如果给每个楼梯标个cost, 那么你跨一步还是跨两步, 会影响cost的累积, 如果要你找一个cost最少的走法, 变动不是特别大:

  1. 走到某层, 就把cost累积起来, 这样向上走的时候就已经知道了当前值, 不需要回溯, 看未来两个楼层的大小就能决策了
  2. dpi=min(dpi−1,dpi−2)+costidp_i = min(dp_{i-1}, dp_{i-2}) + cost_i

说到这里的时候, 我有个疑惑, 如果选择了一条路, 那么没选的不是cost得不到累积吗? 事实上, i是累加的, 如果连续两个步骤都没有那个楼梯参与, 它就会完美地绕过了, 如果i+1的时候发现从它走是最优, 那么它的值就累计到下一个步骤去了, 如此往复, 不用担心用没累加过的cost和累加过的cost比的问题, 只有最初几步有这个问题.

假定这样一个数组: [1, 10, 12, 5, 7, 9, 13] 为了省事, 我直接列出每次走一步时的最小cost值:

  • [1, 10, 13=1+12] 此时10比13小, 那么下一步显然应该从10走
  • [1, 10, 13, 15=10+5]
  • [1, 10, 13, 15, 20=13+7]
  • [1, 10, 13, 15, 20, 24=15+9]
  • [1, 10, 13, 15, 20, 24, 33=20+13]

而如果这样一个数组呢; [1, 10, 2, 5, 17, 9, 13]

  • [1, 10, 3=1+2]
  • [1, 10, 3, 8=3+5]
  • [1, 10, 3, 8, 20=3+17]
  • [1, 10, 3, 8, 20, 17=8+9]
  • [1, 10, 3, 8, 20, 17, 30=17+13]

第二个例子中, 第二级楼梯直接被绕过了, 完全不影响, 只要你在某个台阶上原生cost值巨大, 那么它跟它有关的两次决策中就会被绕过, 这是正常的. 上例中, 17那一列, 加了一个小数3后, 得到20, 而它左右分别是8和9, 显然从8走到9也就只有17, 小于20, 再往下走, 这个20也就被跳过了

/* 爬楼梯最小代价：空间优化后的动态规划 */
function minCostClimbingStairsDPComp(cost) {
    const n = cost.length - 1;
    if (n === 1 || n === 2) {
        return cost[n];
    }
    let a = cost[1],
        b = cost[2];
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, Math.min(a, b) + cost[i]];
    }
    return b;
}

思考: 继续加约束, 如果不让两次连续跳1阶, 问有多少种方案呢?

  • 如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解
  • 适合用回溯解决的问题通常满足“决策树模型”，

背包问题

背包问题（Knapsack problem）是经典的动态规划问题之一，它描述了在给定一组物品和它们的重量和价值的情况下，如何选择物品放入背包，使得背包内物品的总价值最大，同时不超过背包的容量限制。

背包问题写长了, 单独成篇: 背包问题

贪心算法

贪心算法（greedy algorithm）是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

  • 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
  • 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。
function greedyChange(coins, amount) {
    const res = [];
    // 逆序搜索, 即永远选取面值最大的硬币
    // 个数不断增加, 直到爆掉为止, 换成小的面值
    for (let i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            res.push(coins[i]);
        }
    }
    return res;
}

其实贪心算法并不一定总是能得到最优解，如以下场景. 因为贪心选择并不总是全局最优的选择。然而，在某些情况下，贪心算法可以有效地找到最优解，例如：找零问题、哈夫曼编码、最小生成树等。

最大容量问题

一个序列, 每个值代表一个挡板的高度, 两个挡板间就可以盛水, 求最大盛水量.

思路: 首先选择两边的挡板, 有个初始容量, 然后观察:

  1. 如果你把高的挡板往中间移动, 容量必然变小, 因为移动了高板后,
    • 如果变成了更高或一样高度的板, 因为水位高度由矮板决定, 所以高度不会变高, 但是, 宽度变小了, 所以容量变小
    • 如果变成了更矮的板, 水位反而会更低, 加上宽度也在变小, 容量就更小了
  2. 但你把矮板向中间移动, 就有机会碰到更高的板, 虽然缩了宽度, 但是有机会碰到更高的板, 会增加水位, 所以不妨试一试, 与当前最高容量做对比, 也就是说, 这个移动是有意义的, 而移动高板是绝对没意义的.
function maxArea(height) {
    let l = 0, r = height.length - 1;
    let res = 0;
    while (l < r) {
        res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return res;
}

最大切分乘积问题

一个正整数, 表示成N个正整数之和, 求不同切分方案中正整数的最大乘积. 这个题主要是找到规律, 假如一个数切成1和n-1, 那么相乘后反而变成n-1了, 显然不合适, 那么2和n-2呢?

2(n−2)>n2n−n−4>0n>4\begin{aligned} 2(n-2)& > n \\ 2n - n - 4& > 0 \\ n& > 4 \end{aligned}

可知, 但凡一个数大于4, 就可以表示成至少两个正整数相加, 使得乘积大于原数, 也就是说, 大于4的数总可以表现为N个2, 3相加, 当然, 4也是不需要考虑的, 4=2+2=2×24=2+2=2\times2, 虽然没有使乘积变大, 但是也没有使乘积变小, 所以碰到4我们可以分解为2和2, 这样编程的时候可以少考虑一种情况, 仅此而已.

而判断是用2还是3呢?

  1. 2x2x2 < 3x3, 能拆成3的情况就不拆成2, 贪心flag.
  2. 2x2 > 3x1 (主要是有1参与了), 这是写代码时需要考虑的例外 算法如下:
  3. 不断用3拆分, 直到余数为0, 1, 2
  4. 余数为0, 那就是恰好拆完
  5. 余数为1, 那么把最后一个3换成2, 组成2x2
  6. 余数为2, 最后数直接就是2
/* 最大切分乘积：贪心 */
function maxProductCutting(n) {
    // 当 n <= 3 时，必须切分出一个 1
    // 这是题目要求, 不然不切乘积还大些
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // 贪心地切分出 3 ，a 为 3 的个数，b 为余数
    let a = Math.floor(n / 3);
    let b = n % 3;
    if (b === 1) {
        // 当余数为 1 时，将一对 1 * 3 转化为 2 * 2
        return Math.pow(3, a - 1) * 2 * 2;
    }
    if (b === 2) {
        // 当余数为 2 时，不做处理
        return Math.pow(3, a) * 2;
    }
    // 当余数为 0 时，不做处理
    return Math.pow(3, a);
}
Backlinks