zdaiot

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

搜索引擎中爬虫的工作原理是——解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。那同一个网页链接可能包含在多个页面中，导致爬虫的过程中，重复抓取相同的页面。那如何避免这些重复的爬取呢？最简单的方法是记录爬取的网页链接（URL），每次爬取一个网页之前，在记录中进行查询。

不过，应该如何记录已经爬取的网页链接呢？需要用什么样的数据结构呢？

算法解析

这个问题要处理的对象是网页链接，也就是URL。数据结构需要满足如下几个条件：

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

关于图，之前提过两种针对无权图的搜索算法——深度优先搜索和广度优先搜索算法。那针对有权图，该如何计算两点之间的最短路径（经过的边的权重和最小）呢？经常使用地图软件时，会自动帮我们规划处最优路线。这个过程就涉及到本节要介绍的最短路径算法（Shortest Path Algorithm）。

算法解析

解决实际问题时，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。对于这个问题，可以把地图抽象成图。把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。对应的代码如下：

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

public class Graph { // 有向有权图的邻接表表示
  private LinkedList<Edge> adj[]; // 邻接表
  private int v; // 顶点个数

  public Graph(int v) { // 为图建立数据结构
    this.v = v;
    this.adj = new LinkedList[v];
    for (int i = 0; i < v; ++i) {
      this.adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t, int w) { // 添加一条边
    this.adj[s].add(new Edge(s, t, w));
  }

  private class Edge {
    public int sid; // 边的起始顶点编号
    public int tid; // 边的终止顶点编号
    public int w; // 权重
    public Edge(int sid, int tid, int w) {
      this.sid = sid;
      this.tid = tid;
      this.w = w;
    }
  }
  // 下面这个类是为了dijkstra实现用的
  private class Vertex {
    public int id; // 顶点编号ID
    public int dist; // 从起始顶点到这个顶点的距离
    public Vertex(int id, int dist) {
      this.id = id;
      this.dist = dist;
    }
  }
}

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

本节开始进入高级篇。相对于基础篇“开篇问题 - 知识讲解 - 回答开篇 - 总结 - 课后思考”这样的文章结构，高级篇的组织结构为“问题阐述 - 算法解析 - 总结引申 - 课后思考”。也就是高级篇会围绕一个实际软件开发的问题，在阐述具体解决方法的过程中，将涉及的知识点给你详细讲解出来。

本节主要解决的问题是，如何确定代码源文件的编译依赖关系？一个完整的项目往往有很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp。

编译器通过分析源文件或者程序员事先写好的编译配置文件（比如Makefile文件），来获得局部依赖关系。对于前者，那编译器该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

本节主要涉及动态规划的一些理论知识。你需要解决这几个问题：什么样的问题可以用动态规划解决？解决动态规划问题的一般思考过程是什么样的？贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？

“一个模型三个特征”理论讲解

什么样的问题适合用动态规划来做，其实这有一套成熟的理论，叫作”一个模型三个特征“理论。

一个模型理论指的是动态规划适合解决的问题的模型。这个模型可以定义为”多阶段决策最优解模型“。我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段，每个决策阶段都对应着一组状态。然后需要寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

对于搜索引擎，除了利用 Trie 树实现搜索引擎的关键词提示功能外，还经常用到拼写纠错功能。如下图所示，那这个功能是如何实现的呢？

如何量化两个字符串的相似度？

计算机只认识数字，那么如何量化两个字符串之间的相似程度呢？这需要用到著名的量化方法——编辑距离（Edit Distance）。它指的是将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；对于两个完全相同的字符串来说，编辑距离就是 0。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

双十一有很多促销活动，比如“满200元减50元”。假如购物车有 n 个（n>100）商品，要从中选几个，在凑够满减条件前提下，让选出的商品价格总和最大程度地接近满减条件（200）元。这怎么使用代码解决呢？这就需要用到今天讲到的动态规划（Dynamic Programming）。

动态规划学习路线

动态规划比较适合来求解最优问题，比如求最大值、最小值等。它可以显著降低时间复杂度，提高代码执行效率。不过，跟递归类似，它求解问题的过程不太符合人类常规的思维方式。

这次，主要分为三节来讲解：

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

除了前面讲过的深度优先算法利用的是回溯算法，正则表达式匹配、编译原理中的语法分析通常也用到了回溯算法。另外，数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等数学问题也都使用的是回溯算法解决。

如何理解“回溯算法”？

借助贪心算法，每次面对岔路口时，都做出当前看起来最优的选择，期望这一组选择可以使得我们的人生达到“最优”。但是，贪心算法并不一定能得到最优解。那怎么才能得到人生的最优解呢？《蝴蝶效应》电影讲述的是主人公为了达到自己的目标，一直通过回溯的方法，回到童年，在关键的岔路口，重新做选择。

笼统的来说，回溯算法很多时候都应用在“搜索”这类问题上，这里的搜索并不止狭义上图的搜索算法，而是在一组可能的解中，搜索满足期望的解。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

基础的数据结构和算法前面基本学完了，接下来几节，将会涉及到几种更加具体的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。准备来说，它们是算法思想，并不是具体的算法，常用来指导我们设计具体的算法和编码等。

这几个算法思想原理虽然简单，但是我们要结合具体的问题，感受这些算法是怎么工作的，是如何解决问题的，要在问题中体会这些算法的本质。

本节先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。

今天我们主要学习下霍夫曼编码，看看它是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

MapReduce、GFS 和 Bigtable并列为Google大数据处理的三驾马车。其中MapReduce在倒排索引、PageRank 计算、网页分析等搜索引擎相关的技术中都有大量的应用。实际上，它的本质就是今天我们要学的算法思想——分治算法。

如何理解分治算法

分治算法（divide and conquer）的核心思想就是分而治之。也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

这个定义看起来有点类似于递归。区别在于分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分层算法的递归实现中，每一层递归都会涉及这样的三个操作：

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

很多网站，大都有敏感词过滤功能。其实这些功能的基本原理是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“*”把它替代掉。

虽然前面讲过好几种字符串匹配算法，都可以处理这些问题。但是这些算法对于这个应用场景效率很低。那如何才能实现一个高性能的敏感词过滤系统呢？这就要用到今天的多模式串匹配算法。

基于单模式串和 Trie 树实现的敏感词过滤

单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。