0
64
40735
9
2
数据结构 有向无环图-邻接表数据结构 算法 1.Kahn算法 Kahn算法实际上用的是贪心算法思想，思路非常简单、好懂。 定义数据结构的时候，如果 s 需要先于 t 执行，那...
如何量化两个字符串的相似度？ 编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个...
“一个模型三个特征”理论讲解 什么是“一个模型”？它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。 什么是“三个特征”？它们分别是最优子结构...
0-1 背包问题 备忘录 动态规划-二维数组 动态规划-一维数组 0-1 背包问题升级版 回溯算法 动态规划-二维数组 动态规划-一维数组
如何理解“回溯算法”？ 回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。...
如何理解分治算法？ 分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递...
如何理解“贪心算法”？ 第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大...
字符串匹配算法 单模式串匹配算法 是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。 多模式串匹配算法 就是在多个模式串和一个主串之间做匹配，也就是...
什么是“Trie树” Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。 T...
BF算法 BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。 我们在主串中，检查起始位置分别是0、1、2…n-m且长度为m的n...
无向图 广度优先搜索（BFS） 它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。 深度优先搜索（DFS）
如何理解“图”？ 图中的元素我们就叫作顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边（edge）。 无向图 我们就拿微信举例子...
堆的应用一：优先级队列 优先级队列，顾名思义，它首先应该是一个队列。队列最大的特性就是先进先出。不过，在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高...
堆定义 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每...
什么是“平衡二叉查找树”？ 平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。 如何定义一棵“红黑树”？ 根节点是黑色的； 每个叶子节点都是...
二叉查找树 它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要...
树 节点的高度=节点到叶子节点的最大路径（边数） 节点的深度=根节点到这个节点所经历的边的个数 节点的层数=节点的深度+1 树的高度=根节点的高度 二叉树 二叉树，顾名思义，...
什么是哈希算法？ 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 哈希算法需要满足的要求 从...
为什么散列表和链表经常会一起使用？ 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按...
如何设计散列函数 散列函数的设计不能太复杂 散列函数生成的值要尽可能随机并且均匀分布 装载因子过大了怎么办？ 对于没有频繁插入和删除的静态数据集合来说，我们很容易根据数据的特...
发简信
