algorithm-tree-trie
字典树
概念
字典树,也称为前缀树(Trie树),是一种用于存储和管理一组字符串数据的树状数据结构。字典树的主要特点是能够有效地支持字符串的插入和查找操作,以及高效地完成具有相同前缀的字符串的检索。
字典树是一种多叉树结构,每个节点代表一个字符,根节点通常为空。从根节点到某个节点的路径上的字符连接起来即构成一个字符串。
模板
添加和搜索操作的模板
12345678910111213141516171819202122232425262728class Trie { class TrieNode { boolean end; // int cnt; // 维护节点数量 TrieNode[] children = new TrieNode[26]; } TrieNode root = new TrieNode(); void insert(String word) { TrieNode cur = root; for (char c : word.toCh ...
algorithm-string-kmp
KMP算法概念
KMP算法是一种用于字符串匹配的经典算法,它的全名是Knuth-Morris-Pratt算法,是由Donald Knuth、Vaughan Pratt和James H. Morris分别独立发明的。KMP算法用于在一个主文本字符串中查找一个模式字符串的出现,它的主要优势在于在匹配失败时避免不必要的回溯。
KMP算法通过构建部分匹配表(Partial Match Table),也称为最长前缀后缀匹配表(Longest Prefix Suffix Table),来避免这种不必要的比较。
性能分析
KMP算法的时间复杂度为O(m + n),其中m是主文本字符串的长度,n是模式字符串的长度。
参考
算法学习笔记(13): KMP算法
模板
1234567891011121314151617181920212223242526// 利用匹配获取pmt数组public static int[] getPmt(char[] pattern) { int pmt[] = new int[pattern.length]; // pmt[0] = 0; // 计算p ...
algorithm-dynamic-programming
dp深似海
“系统过去的历史只能通过现阶段的状态去影响系统的未来”——研究生算法课程老师对动态规划的描述,感觉挺不错的
分类参考了灵神的dp题单
记忆化搜索和递推是dp的两种实现方式
网格图dp
背包dp
线性dp
状态机dp
划分型dp
区间dp
状压dp
数位dp
树形dp
dp回溯
其它待分类dp
注意事项
如果动态转移方程不是按顺序的,那么需要注意不能直接赋值f[i+1][j] = f[i][j];,因为这样可能会覆盖之前动态转移的结果(注释的是按顺序的动态转移写法)
相关题解:3276. 选择矩阵中单元格的最大得分
1234567f[i+1][j] = Math.max(f[i+1][j], f[i][j]);// f[i+1][j] = f[i][j]; // 这里是错的,不能赋值for (int s = map.get(nums.get(i)), t = 0; s > 0; s -= t) { t = s & -s; if ((j & t) > 0) continue; f[i+1][j|t] = ...
algorithm-math-combinatorial-count
组合计数
计数基本原理
∣A∣=∑a∈A1|A| = \sum\limits_{a \in A} 1∣A∣=a∈A∑1
加法定理
|A U B| = |A| + |B|
乘法定理
|A * B| = |A| * |B|
举例
n-bit二进制串一共有多少个: 2^n(乘法原理)
如果把0看作(,把1看作),配对的括号序列有多少个?
0011->(())
101010->)()()(
对于长度为6的序列:
序列={()‾(()),k=2()‾()(),k=2(‾())‾(),k=4(‾(()))‾,k=6(‾()())‾,k=6序列 = \begin{cases}
\underline{()}(()), & k = 2 \\
\underline{()}()(), & k = 2 \\
\underline{(}()\underline{)}(), & k = 4 \\
\underline{(}(())\underline{)}, & k = 6 \\
\underline{(}()()\underline{)}, & ...
algorithm-build-graph
建图是一个机械劳作
邻接矩阵
邻接矩阵是一个二维数组,其行和列都对应图中的顶点。如果顶点i和顶点j之间存在边,则矩阵中的i,j 位置的元素为1(对于无权图),或为边的权重(对于有权图)。如果i=j,则通常为0,表示顶点不会与自己相连
一般来说,题目给出的都是邻接矩阵的形式。
例如743. 网络延迟时间
这个题目就是给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。
本篇主要讨论如何将邻接矩阵转换成其它的存图方式
邻接表
邻接表是表示图中顶点之间相邻关系的一种方式。对于图中的每一个顶点,邻接表包含了与该顶点直接相连的所有顶点的列表。
12345678public int networkDelayTime(int[][] times, int n, int k) { List<int[]> g[] = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayL ...
algorithm-SPFA
SPFA算法
概念
SPFA算法是一种基于Bellman-Ford算法的改进版本,它用于计算图中各节点到源节点的最短路径。与Bellman-Ford算法不同的是,SPFA算法使用了队列来优化计算,从而在某些情况下加速了计算过程。
SPFA算法的基本思想是从源节点开始,将源节点放入队列中,然后不断从队列中取出节点,考察它的邻接节点,以更新到这些邻接节点的最短距离。如果某个节点的最短距离被更新,且该节点不在队列中,那么将该节点加入队列中,以便后续继续考察。
复杂度是O(V*E)
步骤
初始化:将源节点的最短距离设置为0,其他节点的最短距离设置为无穷大(或一个足够大的值),并将源节点加入队列中。
迭代处理队列中的节点:
从队列中取出一个节点。
考察该节点的所有邻接节点,如果通过当前节点到达邻接节点的路径比已知的最短路径更短,则更新邻接节点的最短路径。
如果邻接节点的最短路径被更新,且邻接节点不在队列中,将它加入队列中。
重复步骤2,直到队列为空。
最短路径计算完成后,可以从源节点到任意目标节点的最短路径已知。
原则
只让当前点能到达的点入队
如果一个点已经在队列里, ...
algorithm-design-data-structure
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
1234567891011121314151617输入["LRUCache", "put", "put", "get", "put", "get", "put", "get& ...
algorithm-network-flow
网络流
概念
网络流是一种抽象模型,它通常表示为一个有向图,其中节点代表各种资源的位置,边表示资源在节点之间的流动。每条边上都有一个容量,表示资源可以通过该边的最大数量。网络流问题的目标通常是找到从一个节点到另一个节点的流量分布,以最大化或最小化某种性能度量,例如最大流问题和最小割问题。
流(Flow):表示资源在网络中的分配和传输。流量可以通过图中的边流动,但不能超过每条边的容量限制。
容量(Capacity):每条边上的容量表示该边允许的最大流量。流量不得超过容量。
源点和汇点(Source and Sink):源点是网络中资源的起始位置,汇点是资源的目标位置。网络流问题的目标通常是从源点到汇点传输最大量的资源。
最大流问题(Maximum Flow Problem):在给定网络中寻找从源点到汇点的最大流量,同时满足容量限制。
最小割问题(Minimum Cut Problem):在给定网络中找到一组边,通过删除这些边可以分离源点和汇点,同时最小化被切割的容量总和。
Ford-Fulkerson算法
Ford-Fulkerson算法是一种在网络流中寻找最大流的贪心算法。该算法通 ...
algorithm-floyd
Floyd算法
概念
Floyd算法,也称为Floyd-Warshall算法,是一种用于求解图中所有顶点对之间最短路径的算法。
它是一种动态规划算法,适用于有向图或带权图,可以处理负权边(但不能包含负权回路,负权回路会导致无限小路径)。
伪代码
12345for(k : V) for(i : V) for(j : V) if(d(i, k) + d(k, j) < d(i, j)) d(i, j) = d(i, k) + d(k, j)
算法过程
该算法的本质是动态规划,以状态转移方程的形式描述如下,其中 dp[k][i][j] 表示 经过前 k 个顶点的松弛,得到的顶点 i 到顶点 j 的最短路径长度 。注意第一维的 k 表示 k 个顶点,第二维和第三维表示具体的顶点。
定义: dp[k][i][j] 表示经过前 k 个顶点的松弛,得到的顶点 i 到顶点 j 的最短路径长度。
边界: dp[0][i][j] = i == j ? 0 : (g[i][j] == 0 ? Inf : g[i][j])
递推: dp[k][i][j] = min& ...
algorithm-greedy
贪心
贪心算法(英语:greedy algorithm),又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。
45. 跳跃游戏 II
300. 最长递增子序列
3292. 形成目标字符串需要的最少字符串数 II:其中用到的贪心就是跳跃游戏
反悔贪心
概念
反悔贪心算法是一种优化算法,通常用于解决组合优化问题。与传统的贪心算法不同,反悔贪心算法在每一步决策之后考虑可能的反悔,以确保最终的决策是最佳的。它的目标是最小化决策的后悔或损失。
流程
初始决策: 算法开始时会做出初始决策,通常基于某种贪心策略来选择一个方案。
模拟反悔: 在每个决策步骤之后,算法会模拟所有可能的替代决策,计算每个替代决策的后悔值或损失。后悔值是当前决策相对于其他可能决策的性能差距。
选择最小后悔: 算法会选择具有最小后悔值的替代决策作为最终决策。这意味着算法会选择对整体性能改进最大的替代决策。
迭代: 反悔贪心算法会重复执行步骤 2 和步骤 3,每次迭代都会尝试改进当前的决策,直到后悔值不再减小或达到某个停止条件。
应用
反悔贪心算法的应用 ...