图 - 最小生成树

2022/12/24

最小生成树相关定理和算法
- 切分定理
- Kruskal 算法
- Prim 算法

生成树指的是无向图中，具有该图的 全部顶点 且 边数最少 的连通子图。
最小生成树指的是加权无向图中总权重最小的生成树。

切分定理

图的搜索算法

2022/12/15

并查集是用来检查两个顶点之间的连通性。而找出图所有的顶点呢、找出它两个顶点之间的路径等都需要深度优先搜索算法或广度优先搜索算法。

深度优先搜索算法

Depth First Search DFS => always use stack .

	时间复杂度	空间复杂度
DFS 遍历所有节点	$$O(V+E)$$	\[O(V)\]
DFS 遍历两点之间所有路径	$$O((2^V)∗(V+E))$$	$$O((2^V)∗V)$$

V 表示顶点数，E 表示边数。

练习题 - 力扣 797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j] 存在一条有向边）。

示例1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

注意：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即不存在自环）
graph[i] 中的所有元素互不相同
保证输入为有向无环图（DAG）

本题可用 DFS / 递归或回溯的方法做。这里给出 DFS 的解法

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function(graph) {
    let answer = [];
    const n = graph.length;
    (function dfs(start = 0, arr = []) {
        arr.push(start);
        if(start === n - 1) {
            answer.push(arr.slice());
            return;
        }
        for(let i = 0; i < graph[start].length; i++) {
            dfs(graph[start][i], arr.slice());
        }
    })()
    return answer;
};

广度优先搜索算法

Breath First Search BFS => always use queue .

“广度优先搜索” 最高效的用途是：当在 权重相等且均为正数的图中，它可以快速的找到两点之间的最短路径

遍历「图」中所有顶点
针对权重相等且均为正数的「图」，快速找出两点之间的最短路径

	时间复杂度	空间复杂度
`BFS` 遍历所有顶点	$$O(V+E)$$	$$O(V)$$
`BFS` 求两点之间最短路径	$$O(V+E)$$	$$O(V)$$

V 表示顶点数，E 表示边数。

上题也可用 BFS 做（不建议）：

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function(graph) {
    let ans = [];
    const n = graph.length;
    if(!graph || n === 0) {
        return ans;
    }
    let path = [0];
    let queue = [path];
    while(queue.length) {
        let cur = queue.shift();
        let node = cur[cur.length - 1];
        for(let next of graph[node]) {
            let t = cur.slice();
            t.push(next);
            if(next == n - 1) {
                ans.push(t.slice());
            } else {
                queue.push(t.slice());
            }
        }
    }
    return ans;
};

图的储存与并查集的实现

2022/12/12

本文为学习笔记，学习资料来源如下：
作者：爱学习的饲养员
链接：https://leetcode.cn/leetbook/read/graph/npniph/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

图的类型有很多，常见的有：无向图、有向图、加权图。

无向图的图中任意两个顶点之间的边都是没有方向的。
有向图的图中任意两个顶点之间的边都是有方向的。
加权图的图中的每条边都有一个权重。

图的定义和相关术语

「图」是由顶点和边组成的一种非线形数据结构。

图的存储

在程序中运用图论相关算法的第一步，我们需要先学会如何把图储存起来。

矩阵存图法

图中的顶点我们已经编好了号，那么我们需要储存的和图相关的信息，就只剩下点与点之间的连边了。

一个很直观的想法就是用一个二维数组来存图，下标代表点，值代表连边的情况。这就是所谓的矩阵存图法，也被称作为邻接矩阵存图法。

更具体地，我们一般使用 bool 数组来储存点与点之间的连边信息：

如果 con[i][j] 的值为 true ，表示点 i 与点 j 之间连了一条从 i 指向 j 的边。
如果 con[i][j] 的值为 false ，表示点 i 与点 j 之间没有连边。

基本操作的复杂度：

添加一条边的时间复杂度为 $\Theta(1)$ 。
判断两个点之间是否有边相连的时间复杂度为 $\Theta(1)$ 。
遍历一个点的所有出边的复杂度为 $\Theta(n)$

矩阵存图法各种操作的时间复杂度相对来说都较为优秀，但是其劣势在于：存下一个图需要 $O(n^2)$ 的空间复杂度，这在面对点与点之间的连边数远远小于 $\Theta(n^2)$ 的稀疏图时，就有很多空间被浪费了。

我们之前的讨论，针对的是无权有向图，那么如果面对的是有权图，或者无向图，我们该如何进行存储呢？

对于有权图的情况：我们只需要将 bool 数组改为 int 数组，两点之间有连边，就将对应元素的值改为边权即可。当然这种情况下，需要将数组初始化为一个不可能的边权（部分题目存在边权为 0 的情况）
对于无向图的情况：只需 con[i][j] = con[j][i] = true

邻接表存图法

矩阵存图的最大的劣势，就是在面对稀疏图时，有很多空间没有储存有效信息（对于一个图，我们往往更加关注哪些点之间有连边，而不关注哪些点之间没有连边），被浪费掉了。一个优化的思路是：我们不再考虑储存每一个点对之间的连边信息，而只考虑那些有连边的点对。这样我们就能够保证所储存下来的信息都会是有效的。

针对上述思路，对于一个有 n 的点的图，我们可以利用 n 个链表，第 i 个链表里存着所有从 i 直接连向的点。

基本操作的复杂度：

添加一条边需要新建一个结构体，并且插入链表中，时间复杂度为 $\Theta(1)$ 如果我们添加的是无向边，那么需要添加两次。
判断两个点之间是否有边相连：如果我们想要知道图中是否存在一条从 i 连向 j 的边，那么我们需要遍历点 i 的所有出边，判断终点是否为 j 。因此，判断两个点之间是否有边相连的时间复杂度，与遍历一个点的所有出边的时间复杂度相同，为 $\Theta(出度)$
遍历一个点的所有出边时间复杂度为 $\Theta(出度)$ 。从实现上来看，遍历一个点的所有出边，等价于遍历第 i 个节点对应的链表。

由于邻接表只储存了连接的边的信息，所以其空间复杂度为 $\Theta(m)$ （一般我们用 m 来表示图中边的数量）

链式前向星存图法

链式前向星存图和邻接表存图的方式总体思路是相同的，只是在实现的方式上有所不同。链式前向星更像是数组模拟链表的一种运用。 在算法竞赛中广泛应用。

链式前向星存图与邻接表存图，虽然实现方式差异较大，但实际的时间复杂度是一样的。

并查集

「并查集」的主要作用是用来解决网络中的连通性。

父节点：顶点的直接父亲节点。
根节点：没有父节点的节点，本身可以视为自己的父节点。

设计并查集数据结构：

union 函数：合并两个顶点，并将他们的根结点保持一致。
find 函数：找到给定顶点的根结点。

并查集有两个实现方式：

Quick Find ：它指的是实现「并查集」时，find 函数时间复杂度很低为 O(1)，让 union 函数就需要承担更多的责任，它的时间复杂度为 O(N)。
Quick Union ：它指的是实现「并查集」时，相对于 Quick Find 的实现方式，我们通过降低 union 函数的职责来提高它的效率，但同时，我们也增加了 find 函数的职责。

Quick Find

// 并查集 - Quick Find 的实现
class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
  }
  find(x) {
    // 主要工作都分配给了 union函数，其已经将对应的根元素分好
    return this.root[x];
  }
  union(x, y) {
    let rootx = this.find(x),
      rooty = this.find(y);
    if (rootx !== rooty) {
      // 如果根元素不同，则将根元素换为 y 的
      for (let i = 0; i < this.root.length; i++) {
        if (this.root[i] === rootx) this.root[i] = rooty;
      }
    }
  }
  // 判断是否联通
  connected(x, y) {
    return this.find(x) == this.find(y);
  }

  // 测试专用
  show() {
    return this.root;
  }
}

测试：

const uf = new UnionFind(10);
// 1-2-5-6-7 3-8-9 4
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(6, 7);
uf.union(3, 8);
uf.union(8, 9);
uf.show(); // [ 0, 7, 7, 9, 4, 7, 7, 7, 9, 9 ]
uf.connected(1, 5); // true
uf.connected(7, 5); // true
uf.connected(4, 9); // false
uf.union(9, 4);
uf.connected(4, 9); // true

Quick Union

class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
  }
  // 递归寻找根节点
  find(x) {
    while (x !== this.root[x]) x = this.root[x];
    return x;
  }
  // 将根节点划归为一个
  union(x, y) {
    let rootx = this.find(x),
      rooty = this.find(y);
    if (rootx !== rooty) this.root[rootx] = rooty;
  }
  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  // 测试专用
  show() {
    return this.root;
  }
}

测试：

const uf = new UnionFind(10);
// 1-2-5-6-7 3-8-9 4
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(6, 7);
uf.union(3, 8);
uf.union(8, 9);
uf.show(); // [ 0, 2, 5, 8, 4, 6, 7, 7, 9, 9 ]
uf.connected(1, 5); // true
uf.connected(7, 5); // true
uf.connected(4, 9); // false
uf.union(9, 4);
uf.connected(4, 9); // true

	构造函数	find 函数	union 函数	connected 函数
Quick Find 时间复杂度	$O(N)$	$O(1)$	$O(N)$	$O(1)$
Quick Union 时间复杂度	$O(N)$	$O(H)$	$O(H)$	$O(H)$

N 为顶点的个数，H 树的高度。

总体来说，Quick Union 是比 Quick Find 更加高效的。

按秩合并的「并查集」

我们已经实现了 2 种「并查集」。但它们都有一个很大的缺点，这个缺点就是通过 union 函数连接顶点之后，可能所有顶点连成一条线形成，这就是我们 find 函数在最坏的情况下的样子。

解决方案便是按秩合并。这里的「秩」可以理解为「秩序」。之前我们在 union 的时候，我们是随机选择 x 和 y 中的一个根节点/父节点作为另一个顶点的根节点。但是在「按秩合并」中，我们是按照「某种秩序」选择一个父节点。

这里的「秩」指的是每个顶点所处的高度。我们每次 union 两个顶点的时候，选择根节点的时候不是随机的选择某个顶点的根节点，而是将「秩」大的那个根节点作为两个顶点的根节点，换句话说，我们将低的树合并到高的树之下，将高的树的根节点作为两个顶点的根节点。这样，我们就避免了所有的顶点连成一条线，这就是按秩合并优化的「并查集」。

所以，按秩排序根本上就是对 Quick Union 中的 union 函数进行优化

实现代码：

class UnionFind {
  constructor(len) {
    // 保存数据及其对应的父节点
    this.root = Array(len).fill(0).map((_, i) => i);
    // 保存高度
    this.rank = Array(len).fill(1);
  }
  find(x) {
    while(x !== this.root[x]) x = this.root[x];
    return x;
  }
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      if(this.rank[rootx] > this.rank[rooty]) {
        this.root[rooty] = rootx;
      } else if(this.rank[rootx] < this.rank[rooty]) {
        this.root[rootx] = rooty;
      } else { // ===
        this.root[rootx] = rooty;
        this.rank[rooty] += 1;
      }
    }
  }
  connected(x, y) {
    return this.find(x) === this.find(y)
  }
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(logN)$	$O(logN)$	$O(logN)$

路径压缩优化的「并查集」

从前面的「并查集」实现方式中，我们不难看出，要想找到一个元素的根节点，需要沿着它的父亲节点的足迹一直遍历下去，直到找到它的根节点为止。如果下次再查找同一个元素的根节点，我们还是要做相同的操作。

如果我们在找到根节点之后，将所有遍历过的元素的父节点都改成根节点，那么我们下次再查询到相同元素的时候，我们就仅仅只需要遍历两个元素就可以找到它的根节点了，这是非常高效的实现方式。可以使用递归算法，这种优化我们称之为「路径压缩」优化，它是对 Quick Union 中的 find 函数进行优化。

// 相对于 Quick Union 的代码，只需要更改 find 函数
find(x) {
    if (x == this.root[x])  return x;
    return this.root[x] = this.find(this.root[x]);
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(logN)$	$O(logN)$	$O(logN)$

基于路径压缩的按秩合并优化的「并查集」

这个优化就是将「路径压缩优化」和「按秩合并优化」合并后形成的「并查集」的实现方式。
union 函数是合并的函数，合并的时候按秩合并。find 函数是查找函数，查找的同时，路径压缩。

代码：

class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
    this.rank = Array(len).fill(1);
  }
  // 路径压缩优化版本的 find 函数
  find(x) {
    if (x === this.root[x])  return x;
    return this.root[x] = this.find(this.root[x]);
  }
  // 按秩合并优化的 union 函数
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      if(this.rank[rootx] > this.rank[rooty]) {
        this.root[rooty] = rootx;
      } else if(this.rank[rootx] < this.rank[rooty]) {
        this.root[rootx] = rooty;
      } else { // ===
        this.root[rootx] = rooty;
        this.rank[rooty] += 1;
      }
    }
  }
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(\alpha(N))$	$O(\alpha(N))$	$O(\alpha(N))$

并查集的实现总结

在「并查集」数据结构中，其中心思想是将所有连接的顶点，无论是直接连接还是间接连接，都将他们指向同一个父节点或者根节点。此时，如果要判断两个顶点是否具有连通性，只要判断它们的根节点是否为同一个节点即可。

在「并查集」数据结构中，它的两个灵魂函数，分别是 find 和 union 。find 函数是为了找出给定顶点的根节点。 union 函数是通过更改顶点根节点的方式，将两个原本不相连接的顶点表示为两个连接的顶点。对于「并查集」来说，它还有一个重要的功能性函数 connected。它最主要的作用就是检查两个顶点的「连通性」。find 和 union 函数是「并查集」中必不可少的函数。connected 函数则需要根据题目的意思来决定是否需要。

「并查集」的代码是高度模版化的。熟记「基于路径压缩+按秩合并的并查集」的实现代码。

题目 - 并查集

参考文献

leetbook - 图

图 - 单源最短路径

2022/12/07

单源最短路径相关算法
- Dijkstra 算法
- Bellman-Ford 算法
- 拓扑排序之 Kahn 算法

Rust数据结构之链表

2022/09/09

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

Rust实现斐波那契数列

2022/09/04

代码实现：

fn fibonacci(n: u32) -> u32 {
    if n == 1 { 1 }
    else if n == 2 { 1 }
    else { fibonacci(n-1) + fibonacci(n-2) }
}

测试：

use std::io;

fn main() {
    // 生成 n 阶斐波那契数列。
    println!("输入 n ：");
    let mut inp:String = String::new();
    io::stdin().read_line(&mut inp).expect("input error!");
    let inp: u32 = inp.trim().parse().unwrap();

    println!("{}阶斐波那契数列: {}", inp, fibonacci(inp));
}
fn fibonacci(n: u32) -> u32 {
    if n == 1 { 1 }
    else if n == 2 { 1 }
    else { fibonacci(n-1) + fibonacci(n-2) }
}

输出：

F:\rust\learn-repo\guessing_game>cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.04s
     Running `target\debug\guessing_game.exe`
输入 n ：
10
10阶斐波那契数列: 55

Promise A+ 规范（译）

2022/08/16

Promise 代表异步操作的最终结果。与 Promise 交互的主要方式是通过其 then 方法，该方法注册回调以接收 Promise 的最终值或 Promise 失败的原因。

该规范详细说明了 then 方法的行为，提供了一个可互操作的基础，所有符合 Promises/A+ 的 Promise 实现都可以依赖该基础来提供。因此，规范应该被认为是非常稳定的。尽管 Promises/A+ 组织可能偶尔会通过微小的向后兼容更改来修改此规范以解决新发现的极端情况，但只有在仔细考虑、讨论和测试后，我们才会集成大的或向后不兼容的更改。

最后

核心 Promises/A+ 规范不涉及如何创建、履行或拒绝 Promise，而是选择专注于提供可互操作的 then 方法。

1、术语

promise 是具有 then 方法的对象或函数，其行为符合本规范。
thenable是定义 then 方法的对象或函数。
value是任何合法的 JavaScript 值（包括 undefined、thenable 或 promise）。
exception是使用 throw 语句抛出的值。
reason 是一个值，表示一个 promise 被拒绝的原因。

2、要求

Promise 状态

Promise 必须处于以下三种状态之一： pending, fulfilled, or rejected。·

处于 pending 状态时，Promise 可以转换到fulfilled 或 rejected 状态。
处于 fulfilled 状态时，Promise 不得转换到其它状态。
- 必须有一个value，并且这个值一定不能改变。
处于 rejected 状态时，Promise 不得转换到其它状态。
- 必须有一个reason，并且这个值一定不能改变。

这里的不得转换意味着其不可变的属性（即 ===），但并不意味着深度不变（深度嵌套的值可变）。

`then` 方法

Promise 必须提供 then 方法来访问其当前或最终的 value或 reason。
Promise 的 then 方法接受两个参数：

1	`promise.then(onFulfilled, onRejected)`

onFulfilled 和 onRejected 都是可选参数，并且如果它们不是函数，则必须忽略它。

如果 onFulfilled 是一个函数
- 它必须在 promise 完成后调用，promise 的 value 作为它的第一个参数
- 在 promise 完成之前不能调用它
- 不能多次调用它。
如果 onRejected 是一个函数
- 它必须在 promise 被拒绝后调用，promise 的 reason 是它的第一个参数
- 在 promise 被拒绝之前不能调用它
- 不能多次调用它
在执行 execution context 堆栈（仅包含平台代码）之前，不得调用 onFulfilled 或 onRejected。 ^[1]
onFulfilled 和 onRejected 必须作为函数调用（即没有 this 值）。 ^[2]
then 可能会在同一个 Promise 上被多次调用
- 当 Promise 被实现，所有相应的 onFulfilled 回调必须按照它们对 then 的调用顺序执行。
- 当 promise 被拒绝时，所有相应的 onRejected 回调必须按照它们对 then 的发起调用的顺序执行。
then 必须返回一个 promise ^[3]
1
promise2 = promise1.then(onFulfilled, onRejected);
- 如果 onFulfilled 或 onRejected 返回一个值 x，运行Promise解决程序 [[Resolve]](promise2, x)。
- 如果 onFulfilled 或 onRejected 抛出一个意外 e，promise2 必须以 e 为 reason 被 rejected。
- 如果 onFulfilled 不是一个函数并且 promise1 处于 fulfilled 状态，promise2 必须以与 promise1 同样的 value 转变到 fulfilled 状态。
- 如果 onRejected 不是一个函数并且 promise1 处于 rejected 状态，promise2 必须以与 promise1 同样的 reason 转变到 rejected状态。

`Promise` 解决程序

promise解决程序是一个抽象的操作，它把一个 promise 和一个 value 作为输入，我们将这个表示为 [[Resolve]](promise, x)。如果 x 是一个 thenable ，它将会试图让 promise 采用 x 的状态，前提是x的行为至少有点像一个 promise。否则，它将会用值 x 执行 promise。
对这些 thenable 的处理使得与 promise 实现方式能够去互相操作。只要它们公开了符合 Promise/A+ 的 then 方法。它还使得 promises/A+ 实现方式能够采用合理的 then 方法去“同化”不一致的实现方式。
为了运行[[Resolve]](promise, x)，执行以下步骤：

如果 promise 和 x 指向同一个对象，则以 TypeError 作为原因拒绝 promise
如果 x 是一个 promise，采用它的状态： ^[4]
1. 如果 x 处于pending，则 Promise 必须保持pending，直到 x 变为 fulfilled 或 rejected
2. 当 x 是 fulfilled，使用相同的 value 实现 promise
3. 当 x 是 rejected，以同样的 reason 拒绝 promise
除此之外，如果 x 是一个对象或函数
1. 令 then 为 x.then ^[5]
2. 如果检索属性 x.then 导致抛出异常 e，则以 e 为 value 拒绝 promise
3. 如果 then 是一个函数，则使用 x 作为 this、第一个参数 resolvePromise 和第二个参数 rejectPromise 调用它，其中：
  - 使用 value y 调用 resolvePromise 时，运行 [[Resolve]](promise, y)
  - 使用 reason r 调用 rejectPromise 时，使用 r 拒绝 promise
  - 如果同时调用了 resolvePromise 和 rejectPromise，或者对同一个参数进行了多次调用，则第一次调用优先，并且任何进一步的调用都将被忽略。
  - 如果调用 then 抛出异常 e:
    - 如果已调用 resolvePromise 或 rejectPromise，则忽略它。
    - 否则，以 e 为 reason 拒绝 promise
4. 如果 then 不是函数，则用 x 实现 promise
如果 x 不是对象或函数，使用 x 实现promise

如果一个参与了 thenable 循环链的 thenable 去 resolve promise，这样 [[Resolve]](promise, thenable) 的递归性质最终会导致 [[Resolve]](promise, thenable) 会被再次调用，遵循上述算法将会导致无限递归。我们鼓励去实现（但不是必需的）检测这样的递归，并以 TypeError 作为 reason 去 reject Promise。 ^[6]

1.这里的“平台代码”指的是引擎，环境和 promise 实现代码。实际上，这个要求保证了 onFulfilled 和 onRejected 将会异步执行，在事件循环之后，用一个新的堆栈来调用它。这可以通过“宏任务”机制（如 settimeout或 setimmediate ）或“微任务”机制（如 mutationobserver 或 process.nextick）来实现。由于 Promise 实现被视为平台代码，因此它本身可能包含一个任务调度队列或“trampoline”，并在其中调用处理程序。 ↩
2.也就是说，在 strict 模式下，这（指的是this）在它们内部将会是 undefined；在普通模式下，它将会是全局对象。 ↩
3.如果实现满足所有要求，则实现可能允许 promise2 == promise1。每个实现都应该记录它是否能够生成 promise2 == promise1 以及在什么条件下。 ↩
4.一般来说，只有当 X 来自当前的实现时，才知道它是一个真正的 promise。本条款允许使用特定于实现的方法来采用已知一致承诺的状态。 ↩
5.此过程首先存储对 x 的引用，然后测试该引用，然后调用该引用，避免多次访问 x.then 属性。这些预防措施对于确保访问器属性的一致性非常重要，访问器属性的值可能在两次检索之间发生更改。 ↩
6.实现方式中不应当在 thenbale 链中的深度设置主观的限制，并且不应当假设链的深度超过主观的限制后会是无限的。只有真正的循环才能导致TypeError。如果遇到由无限多个不同 thenable 组成的链，那么永远递归是正确的行为。 ↩

基本算法 - 数学

2022/07/07

最大公约数、最小公倍数

最大公约数 gcd

1	`const gcd = (a, b) => a ? gcd(b%a, a) : b;`

最小公倍数 lcm

依赖于最大公约数 gcd

1	`const lcm = (a, b) => a * b / gcd(a,b);`

最大值 / 最小值

最大值 max ，输出给定所有数字的最大数字，如果没有参数，则返回 -Infinity。

const max = (...args) => {
  if(args.length === 0) return -Infinity;
  let _max_ = args[0];
  for(const a of args) {
    _max_ = _max_ > a ? _max_ : a;
  }
  return _max_;
}

// use
max(1,2,3,4,5,890,34,12,56757,12) // 56757
// or
max(...[1,2,3,4,5,890,34,12,56757,12]) // 56757

最小值 min ，输出给定所有数字的最小数字，如果没有参数，则返回 Infinity。

const min = (...args) => {
  if(args.length === 0) return Infinity;
  let _min_ = args[0];
  for(const a of args) {
    _min_ = _min_ < a ? _min_ : a;
  }
  return _min_;
}

// use
min(1,2,3,4,5,890,34,12,56757,12) // 1
// or
min(...[1,2,3,4,5,890,34,12,56757,12]) // 1

检查存在性

existy 检查数据是否 存在 ，即是否不等于 null 或 undefined。

1
2
3

const existy = x => x != null
// or
// const existy = x => x != undefined

注：松散不等于 != 会将 null 和 undefined 判定为一个东西，即 null == undefined

判断是否为 truthy

在 JavaScript 中，truthy（真值）指的是在布尔值上下文中，转换后的值为 true 的值。被定义为假值以外的任何值都为真值。（即所有除 false、0、-0、0n、""、null、undefined 和 NaN 以外的皆为真值）。

1	`const truthy = x => x !== false && x != null && x !== 0 && x !== 0n && x === x && x !== "";`

falsy 函数同理:

1	`const falsy = x => x === false \|\| x == null \|\| x === 0 \|\| x === 0n \|\| x === "" \|\| x !== x ;`

生成随机数

随机生成 $m-n$ 之间的整数值

// 保证 m < n
function random(m, n) {
  return Math.round(Math.random() * (n-m) + m);
}

斐波那契数列 - 生成器版本

function* createFibonacci() {
  let a = 1, b = 1;
  while(1) {
    yield a;
    b = a+b;
    a = b-a;
  }
}

let fibonacci = createFibonacci();
fibonacci.next() // { value: 1, done: false }
fibonacci.next() // { value: 1, done: false }
fibonacci.next() // { value: 2, done: false }
fibonacci.next() // { value: 3, done: false }
fibonacci.next() // { value: 5, done: false }
fibonacci.next() // { value: 8, done: false }
fibonacci.next() // { value: 13, done: false }

TypeScript

2022/07/01

TypeScript 知识点

/blog/TypeScript.png

函数式编程之递归的几种方式

2021/09/06

函数式编程提倡使用递归，而不是循环。递归在某些场合下更优雅、更简洁。

但是使用递归有时候会遇到一些问题，比如说栈溢出。

这里总结了几种解决栈溢出问题的几种解决方案，比如最有效的尾递归（tail call），以及不使用尾递归的其它两种方式。

首先，要解决问题就得先有问题；这里使用例子来分析递归的几种方法：

判断一句话中有几个元音字母
- 这里给出判断是否元音字母的函数

const isVowel = letter => {
    const vowel = new Set(['a','e','i','o','u','A','E','I','O','U']);
    return vowel.has(letter)
}

普通递归

首先想到的应该是循环的方法（至少我是），循环更简单易懂，也好写：

// loop
function loopCountVowel(sentence) {
    let ans = 0;
    for (let i = 0;i<sentence.length;i++){
        if(isVowel(sentence[i]))
            ans++;
    }
    return ans;
}
loopCountVowel(
    "Create and share beautiful images of your source code."
)//22

接着，我们来写普通的递归方法，这个也很容易想到：

// recursion
function recursionCountVowel(sentence) {
    let first = isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length <= 1) return first;
    return first + recursionCountVowel( sentence.slice(1) )
}
recursionCountVowel(
    "Create and share beautiful images of your source code."
)// 22

这种递归的方式似乎很好，但是当数据量大的时候，或者更复杂的时候，会引起栈溢出(stack overflow)。造成栈溢出的原因是由于函数运行时，上面的递归会把一个个的函数都一股脑地塞进栈（stack）里，等到递归遇到限定条件停止时，才会一次把所有存在栈里的函数拿出来运算。栈或者说内存大小是有限的，如果递归过深就会把栈撑满，撑爆，溢出；解决栈溢出的方法就是尾递归，如下：

尾递归(PTC)

proper tail calls,PTC，即正确的尾递归。

普通的递归导致溢出的根本原因是，一股脑地把所有的函数都存在栈里，等到最后才拿出来运算。函数保存在栈里的根本原因是函数没有运算结束，上一个函数需要依靠下一个函数的结果。所以，只要解决这个问题即可。

尾递归就是避免把不必要的函数一直保存在栈里，在函数尾部避免使用两个或以上的自身递归调用和其它和下一个函数绑定的数据。只在尾部调用自己，使本函数返回后是完成状态，这样才会使其及时脱离栈。

即把计算结果当作参数而不是返回值。

需要注意的是，在ES6标准里，js才能支持尾递归，且必须在严格模式下才行！

"use strict";
// tail calls
function PTCCountVowel(count, sentence) {
    count += isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count;
    return PTCCountVowel(count, sentence.slice(1))
}
console.log(PTCCountVowel(
    0,
     "Create and share beautiful images of your source code."
)//22

由于第一个参数count 在每次调用时都应该是0，所以可以使用柯里化省去这一参数：

"use strict";
function PTC(count) {
    return function inner(sentence) {
        count += isVowel(sentence[0]) ? 1 : 0;
        if(sentence.length < 2) return count;
        return inner(sentence.slice(1))
    }
}

const PTCCountVowel = PTC(0);

PTCCountVowel(
    "Create and share beautiful images of your source code."
)//22

CPS

如果不依赖尾调用，那么还有其它方式避免栈溢出，这里介绍两种方式。

其一就是CPS（Continuation-Passing Style），这种方法比较难理解，也难写，效率也不高，并且可能会有堆内存存储问题。并不建议使用此方法。

代码例子：

"use strict";
function CPS(sentence, count = v => v) {
    let first = isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count(first);
    return CPS(sentence.slice(1), function f(v) {
        return count(first + v);
    })
}

CPS(
    "Create and share beautiful images of your source code."
)//22

Trampolines

第二种方法是Trampolines，单词的意思是蹦床，描述为栈里的函数像是蹦床一样进去一个，出来一个，一上一下，避免都堆在栈里。

function trampoline(fn) {
    return function trampolined(...args) {
        let result = fn(...args);
        while (typeof result == "function") {
            result = result();
        }
        return result;
    }
}
const countVowel = trampoline(function f(count, sentence){
    count += isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count;
    return function fn() {
        return f(count, sentence.slice(1))
    }
})

countVowel(
    0,
    "Create and share beautiful images of your source code."
)//22

Hexo

切分定理

深度优先搜索算法

练习题 - 力扣 797. 所有可能的路径

广度优先搜索算法

图的定义和相关术语

图的存储

矩阵存图法

邻接表存图法

链式前向星存图法

并查集

Quick Find

Quick Union

按秩合并的「并查集」

路径压缩优化的「并查集」

基于路径压缩的按秩合并优化的「并查集」

并查集的实现 总结

题目 - 并查集

参考文献

1、术语

2、要求

Promise 状态

then 方法

Promise 解决程序

最大公约数、最小公倍数

最大值 / 最小值

检查 存在性

判断是否为 truthy

生成随机数

斐波那契数列 - 生成器版本

普通递归

尾递归(PTC)

CPS

Trampolines

并查集的实现总结

`then` 方法

`Promise` 解决程序

检查存在性