-
【进阶】24、速览(数据结构与算法二)
目录 【进阶】1、排序 【进阶】2、排序（二） 【进阶】3、排序（三） 【进阶】4、排序（四） 【进阶】5、排序（五） 【进阶】6、并查集 【进阶】7、图 【进阶】8、图（二） 【进阶】9、图（三） 【进阶】10、图（四） 【进阶】11、图（五） 【进阶】12、图（六） 【进阶】13、递归(Recursion) 【进阶】14、递归(二 Recursion) 【进阶】15、回溯(Back Tracking) 【进阶】16、贪心、分治 【进阶】17、动态规划 ...…
-
【进阶】23、串
目录 串(Sequence) 蛮力（Brute Force） KMP KMP - next表 KMP - 性能分析串(Sequence)一、介绍本课程研究的串是开发中非常熟悉的字符串，是由若干个字符组成的有限序列 String Text = “thank” t h a n k 字符串 thank 的前缀（prefix）、真前缀（proper prefix）、后缀（suffix）、真后缀（proper...…
-
【进阶】22、跳表
目录 跳表(SkipList) 跳表实现 跳表的层数 跳表的复杂度分析跳表(SkipList)一、思考一个有序链表搜索、添加、删除的平均时间复杂度是多少？ O(n)能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至 O(logn)？ 链表没有像数组那样的高效随机访问（O(1) 时间复杂度），所以不能像有序数组那样直接进行二分搜索优化 那有没有其他办法让有序链表搜索、添加、删除的平均时间复杂度降低至 O(logn)？ 使用跳表（Skip...…
-
【进阶】21、布隆过滤器
目录 布隆过滤器（Bloom Filter） 代码实现布隆过滤器（Bloom Filter）一、思考如果要经常判断 1 个元素是否存在，你会怎么做？ 很容易想到使用哈希表（HashSet、HashMap），将元素作为 key 去查找 时间复杂度：O(1)，但是空间利用率不高，需要占用比较多的内存资源 如果需要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过？ 很显然，HashSet、HashMap 并不是非常好的选择 ...…
-
【进阶】20、动态规划（四）
目录 最长公共子串（Longest Common Substring） 0-1背包 0-1背包，恰好装满最长公共子串（Longest Common Substring）一、最长公共子串 - 题目最长公共子串（Longest Common Substring） 子串是连续的子序列 求两个字符串的最长公共子串长度 ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3二、最长公共子串 – 思路假设 2 个字符串分别是 str1、str2 i ∈ [1,...…
-
【进阶】19、动态规划（三）
目录 最长公共子序列（Longest Common Subsequence，LCS） 代码实现最长公共子序列（Longest Common Subsequence，LCS）一、问题求两个序列的最长公共子序列长度 [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，可能是 ✓ ABCBDAB 和 BDCABA > BDAB ✓ ABCBD...…
-
【进阶】18、动态规划（二）
目录 动态规划（Dynamic Programming） 最大连续子序列和 最长上升子序列（LIS） 最长上升子序列-二分搜索实现动态规划（Dynamic Programming）一、常规步骤动态规划中的“动态”可以理解为是“会变化的状态” ① 定义状态（状态是原问题、子问题的解） ✓ 比如定义 dp(i) 的含义② 设置初始状态（边界） ✓ 比如设置 dp(0) 的值③ 确定状态转移方程 ✓ 比如确定 dp(i) 和 dp(i – 1) 的关系二、...…
-
【进阶】17、动态规划
目录 动态规划（Dynamic Programming） 找零钱动态规划（Dynamic Programming）动态规划，简称DP 是求解最优化问题的一种常用策略 通常的使用套路（一步一步优化） ① 暴力递归（自顶向下，出现了重叠子问题） ② 记忆化搜索（自顶向下） ③ 递推（自底向上）找零钱假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？ 此前用贪心策略得到的并非是最优解（贪心得到的解是 5 枚硬币）假...…
-
【进阶】16、贪心、分治
目录 贪心(Greedy) 分治(Divide And Conquer) 大数乘法贪心(Greedy)一、贪心贪心策略，也称为贪婪策略 每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解贪心的应用 哈夫曼树 最小生成树算法：Prim、Kruskal 最短路径算法：Dijkstra二、最优装载问题（加勒比海盗）在北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海 有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失...…
-
【进阶】15、回溯(Back Tracking)
目录 回溯 八皇后问题(Eight Queens) 八皇后问题代码实现回溯回溯可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果） 每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试 树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用不难看出来，回溯很适合使用递归八皇后问题(Eight Queens)一、问题八皇后问题是一个古老而著名的问题 在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行、同...…
-
【进阶】14、递归(二 Recursion)
目录 上楼梯 汉诺塔（Hanoi） 递归转非递归 尾调用上楼梯楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法 ✓ 如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法 ✓ 如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法所以 f(n) = f(n – 1) + f(n – 2)/// 上n阶楼梯有多少种走法/// @para...…
-
【进阶】13、递归(Recursion)
目录 递归介绍 递归思想 斐波那契数列递归介绍一、递归现象从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？【从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』】GNU 是 GNU is Not Unix 的缩写 GNU → GNU is Not Unix → GNU is Not Unix is Not Unix → GNU is Not ...…
-
【进阶】12、图（六）
目录 Bellman-Ford FloydBellman-Ford一、算法原理Bellman-Ford 也属于单源最短路径算法，支持负权边，还能检测出是否有负权环 算法原理：对所有的边进行 V – 1 次松弛操作（ V 是节点数量），得到所有可能的最短路径 时间复杂度：O(EV) ，E 是边数量，V 是节点数量下图的最好情况是恰好从左到右的顺序对边进行松弛操作 对所有边仅需进行 1 次松弛操作就能计算出A到达其他所有顶点的最短路径最坏情况是恰好每次都从右到左的顺序对...…
-
【进阶】11、图（五）
目录 最短路径（Shortest Path） Dijkstra（迪杰斯特拉算法）最短路径（Shortest Path）一、有权图最短路径是指两顶点之间权值之和最小的路径（有向图、无向图均适用，不能有负权环）二、无权图无权图相当于是全部边权值为1的有权图三、负权边有负权边，但没有负权环时，存在最短路径A到E的最短路径是：A → B → E四、负权环有负权环时，不存在最短路径通过负权环， A到E的路径可以无限短 A → E → D → F → E → D → F →E → D → F ...…
-
【进阶】10、图（四）
目录 生成树（Spanning Tree） 切分定理 Prim算法 Kruskal算法生成树（Spanning Tree）一、生成树（Spanning Tree），也称为支撑树连通图的极小连通子图，它含有图中全部的 n 个顶点，恰好只有 n – 1 条边二、最小生成树（Minimum Spanning Tree）最小生成树（Minimum Spanning Tree，简称MST） 也称为最小权重生成树（Minimum Weight Spanning Tree）、最小支撑树 是所...…
-
【进阶】9、图（三）
目录 遍历 广度优先搜索BFS（Breadth First Search） 深度优先搜索DFS（Depth First Search） AOV网（Activity On Vertex Network） 拓扑排序（Topological Sort）遍历图的遍历从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次图有2种常见的遍历方式（有向图、无向图都适用）广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索深度优先搜索（Dept...…
-
【进阶】8、图（二）
目录 图的实现方案 图的基本接口定义 图的基本接口实现图的实现方案图有2种常见的实现方案 邻接矩阵（Adjacency Matrix） 邻接表（Adjacency List）一、邻接矩阵（Adjacency Matrix）1、邻接矩阵的存储方式一维数组存放顶点信息 二维数组存放边信息邻接矩阵比较适合稠密图不然会比较浪费内存2、邻接矩阵带权图二、邻接表（Adjacency List）1、邻接表存储方式2、邻接表带权图图的基本接口定义@protocol LCGraphProto...…
-
【进阶】7、图
目录 常见数据结构 图(Graph) 图(Graph)的分类常见数据结构线性结构：数组、链表、栈、队列、哈希表树形结构：二叉树、B树、堆、Trie、哈夫曼树、并查集图(Graph)一、介绍图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E) G:表示一个图，V是顶点集，E是边集 V:顶点集V有穷且非空 E:任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的二、应用举例图结构的应用极其广泛 社交网络 地图导航 ...…
-
【进阶】6、并查集
目录 并查集（Union Find） 并查集（Union Find）实现 并查集（Union Find）优化 总结 关于自定义类型并查集（Union Find）一、需求分析假设有n个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路设计一个数据结构，能够快速执行2个操作 查询2个村庄之间是否有连接的路 连接2个村庄数组、链表、平衡二叉树、集合（Set）？查询、连接的时间复杂度都是：O(n)并查集能够办到查询、连接的均摊时间复杂度都是 O(α(n)) ，α(n...…
-
【进阶】5、排序（五）
目录 计数排序（Counting Sort） 基数排序（Radix Sort） 桶排序（Bucket Sort）计数排序（Counting Sort）一、计数排序之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序 平均时间复杂度目前最低是 O(nlogn)计数排序、桶排序、基数排序，都不是基于比较的排序 它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O nlogn 更低 计数排序于1954年由Harold H. Seward...…
