-
【题目】4、栈与队列（二）
目录 739. 每日温度 654. 最大二叉树739. 每日温度题目描述739. 每日温度 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为： 要想观测到更高的气温，至少需要等待的天数。 如果气温在这之后都不会升高，请在该位置用 0 来代替。 例如， 给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]， 你的输出应该 results = [1, 1, 4, 2, 1, 1, 0, 0...…
-
【题目】3、栈与队列
目录 基本概念 155.最小栈 20.有效的括号 232.用栈实现队列 239.滑动窗口最大值基本概念栈 先进后出，后进先出 对称队列、双端队列 先进先出，后进后出 顺序155.最小栈题目描述155. 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 ...…
-
【题目】2、链表
目录 链表相关算法建议 203.移除链表元素 237.删除链表中的节点 206.反转一个单链表 2.两数相加 160.相交链表 86.分隔链表 234.回文链表 141.环形链表 21.合并两个有序链表 23.合并K个升序链表链表相关算法建议一、解题建议一定要多画图二、解题技巧虚拟头结点 快慢指针 多指针 ……三、常用代码要非常熟练链表节点的插入、删除 反转（翻转）一个链表 快慢指针求中心节点 计算链表的长度 ……203.移除...…
-
【题目】1、数组排序
目录 88.合并两个有序数组 75.颜色分类 16.16.部分排序 977.有序数组的平方88.合并两个有序数组题目描述 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素 来源：力扣（Le...…
-
【进阶】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...…
