数据结构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 数据结构

数据结构15-散列表

[toc] 散列思想散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。 假如有 89 名选手参加学校运动会。为了方便记录成绩，每 ...
2020-12-23 数据结构

数据结构14-跳表

[toc] 跳表（Skip list）二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。把改造之后的数据结构叫作跳表（Skip list），这是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、 ...
2020-11-27 数据结构

数据结构13-二分查找

[toc] 二分查找（Binary Search）二分查找（Binary Search）算法，也叫折半查找算法。 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 假设数据大小是 ...
2020-11-27 数据结构

数据结构12-排序之优化

[toc] 如何选择合适的排序算法？ 线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。 时间复杂度是 O(nlogn) 的排序算法不止一个，已经讲过的有归并排序、快速排序，后面讲堆的时候还会讲到堆排序。堆排序和快速排序都有比较多的应用，比如 J ...
2020-11-26 数据结构

数据结构11-排序之线性排序(桶排序、计数排序、基数排序)

[toc] 三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。 这几种排序算法 ...
2020-11-26 数据结构

数据结构10-排序之归并&快排

[toc] 归并排序和快速排序都用到了分治思想，非常巧妙。这两种排序算法适合大规模的数据排序。 归并排序（Merge Sort）如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 归并排序使用的就是分治思想。分治 ...
2020-11-26 数据结构

数据结构09-排序之冒泡&插入&选择

[toc] 排序冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序. 展示动态排序网站：https://visualgo.net/zh 冒泡排序（Bubble Sort）冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如 ...
2020-11-26 数据结构
1234…7