【Princeton】算法习题(1):Union-Find

【Princeton】算法习题(1):Union-Find

week1的面试题(Interview Question)、编程作业(Percolation)及配套书籍中的部分课后习题详解(仅供参考)。

面试题

  1. 给定包含$n$个成员的社交网络和一个日志文件,日志中记录了$m$个网络中某对成员成为朋友关系的时间点。要求设计一种算法,来确定所有成员都相互成为朋友关系的那个时间点。(时间复杂度不超过$m\log n$,空间复杂度不超过$N$)

    日志的格式假设为:时间 p q(如 201907170122 1 2),则解决该问题的程序如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdOut;
    import edu.princeton.cs.algs4.WeightedQuickUnionUF;

    public class SocialNetworkUF {

    private In inputs; // 输入流
    private final WeightedQuickUnionUF networkUF; // 以加权Quick-Union为数据结构

    public SocialNetworkUF(int n, In inputs) {
    this.inputs = inputs;
    networkUF = new WeightedQuickUnionUF(n);
    }

    public String getEarliestConnectedTime() { // 确定网络全连接的最早时间点
    String earliestTime = null;
    while (!inputs.isEmpty()) {
    String line = inputs.readLine();
    if (line != null && !line.trim().equals("")) {
    String[] lineArray = line.split(" "); // 将读取到的一行日志进行切分
    if (lineArray.length == 3) {
    String timeStamp = lineArray[0];
    int p = Integer.parseInt(lineArray[1]);
    int q = Integer.parseInt(lineArray[2]);

    if (networkUF.connected(p, q))
    continue;
    networkUF.union(p, q);
    if (networkUF.count() == 1) { // 只剩下一棵树
    earliestTime = timeStamp;
    break;
    }
    }
    }
    }
    return earliestTime;
    }

    public static void main(String[] args) {
    In inputs = new In(args[0]);
    int n = inputs.readInt();
    SocialNetworkUF networkUF = new SocialNetworkUF(n, inputs);
    String earliestTime = networkUF.getEarliestConnectedTime();
    StdOut.println("The earliest connected time of the social network is:" + earliestTime);
    }
    }
  2. 更改Union-Find中的find方法,使每次调用该方法时,返回的都是连通分量中的最大元素。(union、connected、find方法的复杂度都要控制在$\log$以内)

    在Weighted-Quick-Union的基础上,更改union方法始终以值最大的节点作为根节点,具体的实现如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdOut;

    public class WeightedBiggestQuickUnionUF {
    private int[] id;
    private int[] sz;
    private int count;

    public WeightedBiggestQuickUnionUF(int N) {
    count = N;
    id = new int[N];
    for (int i = 0; i < N; i++)
    id[i] = i;

    sz = new int[N];
    for (int i = 0; i < N; i++)
    sz[i] = 1;
    }

    public int count() {
    return count;
    }

    public int find(int p) {
    while (p != id[p])
    p = id[p];
    return p;
    }

    public boolean connected(int p, int q) {
    return find(p) == find(q);
    }

    public void union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot)
    return;

    if (sz[pRoot] < sz[qRoot]) { // 总是以值较大的作为根节点
    if (pRoot > qRoot) {
    int tmp = pRoot, tmpSize = sz[pRoot];
    pRoot = qRoot;
    sz[pRoot] = sz[qRoot];
    qRoot = tmp;
    sz[qRoot] = tmpSize;
    }
    id[pRoot] = qRoot;
    sz[qRoot] += sz[pRoot];
    } else {
    if (pRoot < qRoot) {
    int tmp = qRoot, tmpSize = sz[qRoot];
    qRoot = pRoot;
    sz[qRoot] = sz[pRoot];
    pRoot = tmp;
    sz[pRoot] = tmpSize;
    }
    id[qRoot] = pRoot;
    sz[pRoot] += sz[qRoot];
    }
    count--;
    }

    public static void main(String[] args) {
    In inputs = new In(args[0]); // uf.txt
    int n = inputs.readInt();
    WeightedBiggestQuickUnionUF uf = new WeightedBiggestQuickUnionUF(n);

    while(!inputs.isEmpty()) {
    int p = inputs.readInt();
    int q = inputs.readInt();
    if (uf.connected(p, q))
    continue;
    uf.union(p, q);
    }

    for (int i = 0; i < n; i++)
    StdOut.println("The root of the node " + i + " is " + uf.find(i));
    }
    }
  1. 给定一个包含$n$个整数的集合$S = {0, 1, \cdots, n-1}$,要求设计一种数据结构及算法,最坏情况下该算法能够在复杂度不超过$\log$下,完成下列操作:

    • 从集合$S$中删除某个数$x$
    • 找出$x$的继任者$y$:$y \ge x$且它是$S$中的最小值

    假设$n=10$,那么

    • $x = 6$–>$y = 7$
    • $x = 5$–>$y = 7$
    • $x = 3$–>$y = 4$
    • $x = 4$–>$y = 7$,同时$x = 3$–>$y = 7$

    由此可见,该题是上一题的引申,每次删除操作可看作一次union操作。用$-1$来表示继任者不存在的情况,则整个程序如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    import edu.princeton.cs.algs4.StdOut;

    public class Successor{
    private int[] id;
    private int[] sz;
    private int count;

    private final int n;
    private boolean[] isRemove; // 记录移除情况

    public Successor(int n) {
    count = n;
    this.n = n;
    id = new int[n];
    isRemove = new boolean[n];
    for (int i = 0; i < n; i++)
    id[i] = i;

    sz = new int[n];
    for (int i = 0; i < n; i++)
    sz[i] = 1;
    }

    public int count() {
    return count;
    }

    public int find(int p) {
    while (p != id[p])
    p = id[p];
    return p;
    }

    public boolean connected(int p, int q) {
    return find(p) == find(q);
    }

    public void union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot)
    return;

    if (sz[pRoot] < sz[qRoot]) {
    if (pRoot > qRoot) {
    int tmp = pRoot, tmpSize = sz[pRoot];
    pRoot = qRoot;
    sz[pRoot] = sz[qRoot];
    qRoot = tmp;
    sz[qRoot] = tmpSize;
    }
    id[pRoot] = qRoot;
    sz[qRoot] += sz[pRoot];
    } else {
    if (pRoot < qRoot) {
    int tmp = qRoot, tmpSize = sz[qRoot];
    qRoot = pRoot;
    sz[qRoot] = sz[pRoot];
    pRoot = tmp;
    sz[pRoot] = tmpSize;
    }
    id[qRoot] = pRoot;
    sz[pRoot] += sz[qRoot];
    }
    count--;
    }

    public void remove(int p) { // 删除元素
    if (isRemove[p]) // 还未被移除
    throw new IllegalArgumentException("The element has been removed!");

    if (p > n) // 防止越界
    throw new IllegalArgumentException("Array access out of bounds!");

    isRemove[p] = true;
    if (p + 1 < n)
    union(p, p+1);
    }

    public int getSuccessor(int p) { // 寻找继任者
    int successor = find(p);
    if (isRemove[successor]) // 继任者已被移除
    return -1;
    else
    return successor;
    }

    public static void main(String[] args) {
    Successor successor = new Successor(10);
    int[] a = {6, 5, 3, 4, 8, 9, 7, 2, 0};

    for (int i = 0; i < a.length; i++) {
    successor.remove(a[i]);
    StdOut.println("The successor of " + a[i] + " is " + successor.getSuccessor(a[i]));
    }
    }
    }
  2. 设计一个时间复杂度最坏也能保持在$N^2$以内的3-SUM算法。

    将数组内的值进行升序排序后,利用二分查找可将3—SUM算法的复杂度降低到$N^2 \log N$。在HashMap中的进行查找的时间复杂度为常数级别,因此可利用它将3—SUM算法的复杂度控制在$N^2$以内,具体的实现过程如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class ThreeSumQuadratic {
    public static int count(int[] a) {
    Arrays.sort(a); // 排序
    int N = a.length;
    int cnt = 0;

    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < N; i++) {
    map.put(a[i], i);
    }

    for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
    Integer index = map.get(-a[i] - a[j]);
    if (index != null && index > j)
    cnt++;
    }

    return cnt;
    }
    }
  3. 设计满足如下要求的锥形数组(bitonic array)查找算法。所谓锥形数组,指的是数组中的值先呈升序再呈降序排序。

    • 最坏情况下进行$\sim 3\log N$次比较操作的算法
    • 最坏情况下只进行$\sim 2\log N$次比较操作的算法(证明不存在低于该复杂度的算法)

    复杂度为$\sim 3\log N$的查找算法是用三次二分查找,第一次查找数组中的最大值,之后在左右两边的升序和降序序列中分别进行查找,具体的实现见下面的standardSearch。不考虑其中的最大值,在左右两边直接进行二分查找则能够实现复杂度为$\sim 2\log N$的查找算法,具体见fastSearch(参考):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    public class BitonicArraySearch {
    private static int leftSearch(int[] a, int key, int lo, int hi) { // 在升序序列上进行二分查找
    int mid = 0;
    while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (key < a[mid])
    hi = mid - 1;
    else if (key > a[mid])
    lo = mid + 1;
    else
    return mid;
    }
    return -1;
    }

    private static int rightSearch(int[] a, int key, int lo, int hi) { // 在降序序列上进行二分查找
    int mid = 0;
    while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (key > a[mid])
    hi = mid - 1;
    else if (key < a[mid])
    lo = mid + 1;
    else
    return mid;
    }
    return -1;
    }

    public static int normalSearch(int[] a, int key) { // 上界为3log N的查找算法
    int lo = 0;
    int hi = a.length - 1;
    int mid = 0;
    while (lo < hi) {
    mid = lo + (hi - lo) / 2;
    if (a[mid] < a[mid + 1])
    lo = mid + 1;
    else
    hi = mid;
    }

    if (key > a[mid]) // key大于数组中的最大值,则key不存在
    return -1;

    int result = leftSearch(a, key, 0, mid - 1);
    if (result == -1)
    result = rightSearch(a, key, mid + 1, a.length - 1);

    return result;
    }

    public static int fastSearch(int[] a, int key) {
    int lo = 0;
    int hi = a.length - 1;
    int mid = 0;
    int result = -1;
    while (lo < hi) {
    mid = lo + (hi - lo) / 2;
    if (key < a[mid]) {
    result = leftSearch(a, key, lo, mid - 1);
    if (result == -1)
    result = rightSearch(a, key, mid + 1, hi);
    } else {
    if (a[mid] < a[mid + 1])
    lo = mid + 1;
    else
    hi = mid;
    }
    }
    return result;
    }
    }
  4. 有一些鸡蛋及和一栋$N$层的大楼,某个鸡蛋如果从大楼的第$T$层扔下,则刚好不会破碎。在下面给出的鸡蛋数量及实验次数内,要求设计相应的实验策略,来测得鸡蛋的$T$值。

    • 1). $1$个鸡蛋,不多于$T$次实验
    • 2). $\sim \log N$个鸡蛋,不多于$\sim \log N$次实验
    • 3). $\sim \log T$个鸡蛋,不多于$\sim 2\log T$次实验
    • 4). $2$个鸡蛋,不多于$\sim 2\sqrt N$次实验
    • 5). $2$个鸡蛋,不多于$\sim c\sqrt T$次实验($T$为某个常数)

    各个实验策略如下(参考):

    • 1). 从第$1$层开始进行实验,到第$T$层该鸡蛋会碎,实验次数为$T$
    • 2). 二分查找,实验次数最多为$\log N$
    • 3). 依次到第$1, 2, 4, \cdots, 2^k$层扔,如果鸡蛋在$2^k$层碎了,则$2^{k-1}\le T \le 2^k$,这时已经进行了$\log T$次实验,之后在$[2^{k-1}+1,2^k)$区间进行的二分查找,需要$\log T$次实验,因此最多需要$2\log T$次。
    • 4). 将楼层分为$[1, \sqrt n - 1], [\sqrt n, 2\sqrt n - 1], \cdots,[\sqrt k, (k+1)\sqrt n - 1]$这$\sqrt n$个区间,用第一个鸡蛋在各区间的起始楼层进行实验,当该鸡蛋在第$k\sqrt n$层破碎后,就用另一个鸡蛋从$(k-1)\sqrt n + 1$开始逐层进行实验,由此实验次数最多为$2\sqrt n$
    • 5). 用第一个鸡蛋依次到第$1, 4, 9, \cdots, k^2$层扔,如果鸡蛋在$k^2$层碎了,则$(k-1)^2\lt T \le k^2$,这时已经进行了$\sqrt T$次实验,之后用第二个鸡蛋在$[(k-1)^2+1,k^2)$区间逐层进行实验,最多需要进行$2\sqrt T -2$次,因此最多总共需要$3\sqrt T$次实验

编程作业:渗透问题

描述

给定一个由$N \times N$个方格组成的方形水槽,其中每个方格是随机开启或关闭。相邻的开启方格可形成一条通路。如果存在一条从水槽顶端到底端的通路,则称该水槽是渗透(Percolation)的。

渗透与否

假设其中的各方格开启的概率为$p$,该问题想要研究$p$的大小与整个系统渗透的概率之间的关系。经过实验,当水槽的大小分别为$20\times20$、$100\times100$时,可以得到以下面的两个曲线:

曲线

要求编程建立一个模型,来验证当整个系统渗透时,方格的开启概率$p$的取值区间。

分析

用Union-Find算法来解决该问题,将各方格抽象为节点,并用使用二维数组进行索引,二维数组索引值从$1$开始。

为了方便判断整个系统是否渗透,可以在顶部和底部分别添加一个虚节点,它们分别与系统的顶层及底层所有已开启的节点连接。如此,只要判断顶部和底部的虚节点是否连通,即可知整个系统是否渗透。

渗透模型

注意到,由于底部的虚节点与底层所有已开启的节点都是连通的,因此在整个系统渗透后,将产生如下图所示的“倒灌(backwash)”问题:

backwash

该问题会导致对系统中某个节点开启与否的检查结果变得不准确,解决的一个简单办法是同时维护两个水槽系统,一个包含顶部及底部虚节点,另一个只包含顶部虚节点。

根据提示,抽象好整个系统后,可用蒙特卡洛(Monte Carlo)法进行分析:

  1. 将所有的网格初始化为关闭状态,之后随机开启一些方格,直到系统渗透;
  2. 统计出开启的方格数量,与方格总数的比值即是作为$p$值;
  3. 进行$T$次实验,得到足够多的$p$值后,算出所有$p$的平均值$\overline x$和方差$s^2$
  4. 根据如下公式可以计算出置信度为$95%$的的渗透阈值范围:$$[\overline x - \frac{1.96s}{\sqrt{T}}, \overline x + \frac{1.96 s}{\sqrt{T}}]$$

实现

Percolation.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

private static final boolean BLOCK = false;
private static final boolean OPEN = true;

private final int n; // 容器大小
private boolean[][] grid; // 容器
private int openedNum; // 记录已开放数量
private final WeightedQuickUnionUF gridUF; // 加权Quick-Union
private final WeightedQuickUnionUF gridUFBacklash; // 解决backlash问题

public Percolation(int n) { // 初始化
if (n <= 0)
throw new IllegalArgumentException("The Value of n is illegal!");

this.n = n;
grid = new boolean[n][n];
openedNum = 0;
gridUF = new WeightedQuickUnionUF(n * n + 2); // 加上两个虚节点
gridUFBacklash = new WeightedQuickUnionUF((n * n + 1)); // 只包含上虚节点

for (int i = 0; i < n; i++) // 初始化
for (int j = 0; j < n; j++)
grid[i][j] = BLOCK;
}

private void validate(int row, int col) { // 验证索引值
if (row < 1 || col < 1 || col > n || row > n)
throw new IllegalArgumentException("The index of row/column is illegal!");
}

private int map2Dto1D(int row, int col) { // 坐标转换
return (row - 1) * n + col;
}

public void open(int row, int col) { // 打开某节点

validate(row, col);

if (!grid[row - 1][col - 1]) {
grid[row - 1][col - 1] = OPEN; // 开启并计数
openedNum++;

int position = map2Dto1D(row, col);
if (row == 1) {
gridUF.union(0, position); // 如果是第一行的节点,与上方虚节点0相连
gridUFBacklash.union(0, position);
}

if (row > 1 && grid[row - 2][col - 1]) { // 判断节点上方是否开放
gridUF.union(position - n, position);
gridUFBacklash.union(position - n, position);
}

if (row < n && grid[row][col - 1]) { // 判断节点下方是否开放
gridUF.union(position + n, position);
gridUFBacklash.union(position + n, position);
}

if (col > 1 && grid[row - 1][col - 2]) { // 判断节点左方是否开放
gridUF.union(position - 1, position);
gridUFBacklash.union(position - 1, position);
}

if (col < n && grid[row - 1][col] == OPEN) { // 判断节点右方是否开放
gridUF.union(position + 1, position);
gridUFBacklash.union(position + 1, position);
}

if (row == n) // 如果是最后一行的节点,与下方的虚节点(n×n + 1)相连
gridUF.union(position, n*n + 1);
}
}

public boolean isOpen(int row, int col) { // 判断某个节点是否打开
validate(row, col);
return grid[row - 1][col - 1];
}

public boolean isFull(int row, int col) { // 判断某个节点是否渗透
validate(row, col);
int position = map2Dto1D(row, col);
return gridUFBacklash.connected(0, position);
}

public int numberOfOpenSites() { // 开放节点值
return openedNum;
}

public boolean percolates() { // 系统是否渗透
return gridUF.connected(0, n * n + 1);
}
}

PercolationStats.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {

private final int trials; // 实验次数
private final double[] fractions; // 分值记录

private double mean; // 平均值
private double stddev; // 标准差

public PercolationStats(int n, int trials) { // 初始化
if (n <= 0 || trials <= 0)
throw new IllegalArgumentException("Some of the argument is illegal!");

this.trials = trials;
fractions = new double[trials];

for (int i = 0; i < trials; i++) {
Percolation p = new Percolation(n);

while (true) {
int row, col;
row = StdRandom.uniform(n) + 1; // 随机列
col = StdRandom.uniform(n) + 1; // 随机行
p.open(row, col);

if (p.numberOfOpenSites() >= n && p.percolates()) {
fractions[i] = (double) p.numberOfOpenSites() / (n * n);
break;
}
}
}
}

public double mean() { // 平均值
mean = StdStats.mean(fractions);
return mean;
}

public double stddev() { // 标准差
stddev = StdStats.stddev(fractions);
return stddev;
}

public double confidenceLo() { // 置信区间
return mean - 1.96 * stddev / Math.sqrt(trials);
}

public double confidenceHi() {
return mean + 1.96 * stddev / Math.sqrt(trials);
}

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int trials = Integer.parseInt(args[1]);

PercolationStats ps = new PercolationStats(n, trials);
StdOut.print("mean = " + ps.mean() + "\n");
StdOut.print("stddev = " + ps.stddev() + "\n");
StdOut.print("95% confidence interval = [" + ps.confidenceLo() + ", " + ps.confidenceHi() + "]\n");
}
}

课后习题

1.5.12/13 修改quick-union/加权quick-union算法中,在find方法中添加循环来将各节点直接连接到根节点而实现路径压缩。

将find方法更改如下:

1
2
3
4
5
6
7
8
9
10
11
public int find(int p) {
int root = p;
while (root != id[root])
root = id[root];
while (p != root) {
int newp = id[p];
id[p] = root;
p = newp;
}
return root;
}

1.5.14 实现根据高度加权的quick-union算法,即较矮的树总被连接到较高的树上。

将较矮的树union到较高的树时,不会改变树的高度,只有当两棵树的高度相同时,union后的高度才会加一。因此整个算法的具体实现如下;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class HeightWeightedQuickUnionUF {
private int[] id;
private int[] height;

public HeightWeightedQuickUnionUF(int N) {
id = new int[N];
height = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
height[i] = 0;
}
}

public int find(int p) {
while (p != id[p])
p = id[p];
return p;
}

public boolean connected(int p, int q) {
return find(p) == find(q);
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);

if (pRoot == qRoot)
return;

if (height[pRoot] < height[qRoot]) {
id[pRoot] = qRoot;
} else if (height[pRoot] > height[qRoot]) {
id[qRoot] = pRoot;
} else {
id[qRoot] = pRoot;
height[pRoot]++;
}
}
}

参考资料

  1. Algorithms-Coursera
  2. 算法(第四版)

Tip:本文涉及的图片及资料均整理翻译自普林斯顿大学的Robert Sedgewick教授在Coursera上讲授的的Algorithms课程以及他撰写的配套书籍的《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:
2019.07.25 完成初稿

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×