数据结构32-拓扑排序 - 副本 (2)

[toc] ...
2021-03-09 数据结构

数据结构32-拓扑排序 - 副本

[toc] ...
2021-03-09 数据结构

数据结构32-拓扑排序

[toc] ...
2021-03-09 数据结构

数据结构32-拓扑排序 - 副本 (3)

[toc] ...
2021-03-09 数据结构

数据结构31-动态规划实战

[toc] 搜索引擎中的拼写纠错功能利用 Trie 树，可以实现搜索引擎的关键词提示功能，这样可以节省用户输入搜索关键词的时间。实际上，搜索引擎在用户体验方面的优化还有很多，比如你可能经常会用的拼写纠错功能。当你在搜索框中，一不小心输错单词时，搜索引擎会非常智能地检测出你的拼写错误，并且用对应的正确 ...
2021-03-09 数据结构

数据结构29-动态规划理论

[toc] 一个模型三个特征一个模型：多阶段决策最优解模型。一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。 三个特征： 最优子结构 最优子结构指的是，问题的最优解 ...
2021-03-09 数据结构

数据结构19-递归树

[toc] 递归树与时间复杂度分析递归代码的时间复杂度分析起来很麻烦，除了用递推公式这种比较复杂的分析方法，还可以借助递归树来分析递归算法的时间复杂度。 递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为 ...
2021-03-02 数据结构

数据结构18-红黑树

[toc] 平衡二叉查找树平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1。完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。 发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题 ...
2021-01-02 数据结构

数据结构20-堆和堆排序

堆 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 第一点，堆必须是一个完全二叉树。完全二叉树要求除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。 第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，还 ...
2021-01-02 数据结构

数据结构22-深度和广度优先搜索

[toc] 深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。 public class Graph { // 无向图 private int v; // 顶点的个数 private LinkedList<Integer> adj[]; // 邻接表 ...
2021-01-02 数据结构

数据结构21-图的表示

[toc] 图 图中的元素我们就叫作顶点（vertex）。 图中的一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边（edge）。 无向图中顶点相连接的边的条数叫作顶点的度（degree）。 有向图中，度分为入度（In-degree）和出度（Out-degree）：顶点的入度，表示有多少条 ...
2021-01-02 数据结构

数据结构23-字符串匹配

[toc] BF (Brute Force) 算法BF 算法( Brute Force )，中文叫作暴力匹配算法，也叫朴素匹配算法。 在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n& ...
2021-01-02 数据结构

数据结构24-Trie树

[toc] Trie 树Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。 这样一个问题可以有多种解决方法，比如散列表、红黑树，或者前面几节的一些字符串匹配算法，但是，Trie 树在这个问题的解决上，有 ...
2021-01-02 数据结构

数据结构25-AC自动机

[toc] AC自动机实现一个高性能的敏感词过滤系统 基于单模式串和 Trie 树实现的敏感词过滤BF 算法、RK 算法、BM 算法、KMP 算法，还有 Trie 树。前面四种算法都是单模式串匹配算法，只有 Trie 树是多模式串匹配算法。 单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也 ...
2021-01-02 数据结构

数据结构26-贪心算法

[toc] 贪心算法（greedy algorithm）贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。 假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 ...
2021-01-02 数据结构

数据结构27-分治算法

[toc] 分治算法分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。 分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法 ...
2021-01-02 数据结构

数据结构28-回溯算法

[toc] 深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单，但是应用却非常广泛。它除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。 理解“回溯算法”笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。不过 ...
2021-01-02 数据结构

数据结构30-动态规划入门案例

[toc] 动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。 大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是 ...
2021-01-02 数据结构

数据结构17-二叉树基础

[toc] 二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？ 树（Tree）比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有 ...
2020-12-26 数据结构

数据结构16-哈希算法的应用

[toc] 什么是hash不管是“散列”还是“哈希”，这都是中文翻译的差别，英文其实就是“Hash”。所以，我们常听到有人把“散列表”叫作“哈希表”“Hash 表”，把“哈希算法”叫作“Hash 算法”或者“散列算法” 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映 ...
2020-12-26 数据结构
12