组合计数 计数基本原理 ∣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{)}, & ...

建图是一个机械劳作 邻接矩阵 邻接矩阵是一个二维数组，其行和列都对应图中的顶点。如果顶点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 ...

SPFA算法 概念 SPFA算法是一种基于Bellman-Ford算法的改进版本，它用于计算图中各节点到源节点的最短路径。与Bellman-Ford算法不同的是，SPFA算法使用了队列来优化计算，从而在某些情况下加速了计算过程。 SPFA算法的基本思想是从源节点开始，将源节点放入队列中，然后不断从队列中取出节点，考察它的邻接节点，以更新到这些邻接节点的最短距离。如果某个节点的最短距离被更新，且该节点不在队列中，那么将该节点加入队列中，以便后续继续考察。 复杂度是O(V*E) 步骤 初始化：将源节点的最短距离设置为0，其他节点的最短距离设置为无穷大（或一个足够大的值），并将源节点加入队列中。 迭代处理队列中的节点： 从队列中取出一个节点。 考察该节点的所有邻接节点，如果通过当前节点到达邻接节点的路径比已知的最短路径更短，则更新邻接节点的最短路径。 如果邻接节点的最短路径被更新，且邻接节点不在队列中，将它加入队列中。 重复步骤2，直到队列为空。 最短路径计算完成后，可以从源节点到任意目标节点的最短路径已知。 原则 只让当前点能到达的点入队 如果一个点已经在队列里， ...

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& ...

网络流 概念 网络流是一种抽象模型，它通常表示为一个有向图，其中节点代表各种资源的位置，边表示资源在节点之间的流动。每条边上都有一个容量，表示资源可以通过该边的最大数量。网络流问题的目标通常是找到从一个节点到另一个节点的流量分布，以最大化或最小化某种性能度量，例如最大流问题和最小割问题。 流（Flow）：表示资源在网络中的分配和传输。流量可以通过图中的边流动，但不能超过每条边的容量限制。 容量（Capacity）：每条边上的容量表示该边允许的最大流量。流量不得超过容量。 源点和汇点（Source and Sink）：源点是网络中资源的起始位置，汇点是资源的目标位置。网络流问题的目标通常是从源点到汇点传输最大量的资源。 最大流问题（Maximum Flow Problem）：在给定网络中寻找从源点到汇点的最大流量，同时满足容量限制。 最小割问题（Minimum Cut Problem）：在给定网络中找到一组边，通过删除这些边可以分离源点和汇点，同时最小化被切割的容量总和。 Ford-Fulkerson算法 Ford-Fulkerson算法是一种在网络流中寻找最大流的贪心算法。该算法通 ...

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& ...

贪心 贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。 45. 跳跃游戏 II 300. 最长递增子序列 3292. 形成目标字符串需要的最少字符串数 II：其中用到的贪心就是跳跃游戏 反悔贪心 概念 反悔贪心算法是一种优化算法，通常用于解决组合优化问题。与传统的贪心算法不同，反悔贪心算法在每一步决策之后考虑可能的反悔，以确保最终的决策是最佳的。它的目标是最小化决策的后悔或损失。 流程 初始决策： 算法开始时会做出初始决策，通常基于某种贪心策略来选择一个方案。 模拟反悔： 在每个决策步骤之后，算法会模拟所有可能的替代决策，计算每个替代决策的后悔值或损失。后悔值是当前决策相对于其他可能决策的性能差距。 选择最小后悔： 算法会选择具有最小后悔值的替代决策作为最终决策。这意味着算法会选择对整体性能改进最大的替代决策。 迭代： 反悔贪心算法会重复执行步骤 2 和步骤 3，每次迭代都会尝试改进当前的决策，直到后悔值不再减小或达到某个停止条件。 应用 反悔贪心算法的应用 ...

一些常见的排序

二分查找 二分查找（Binary Search）是一种高效的搜索算法，适用于有序数组或有序列表。它通过不断地将搜索范围减半来查找目标元素，从而在O(log n)的时间复杂度内找到特定元素的位置。 在有序数组中找到中间位置的元素，与目标元素进行比较。如果中间元素等于目标元素，则搜索成功；如果中间元素大于目标元素，则在数组的左半部分继续进行二分查找；如果中间元素小于目标元素，则在数组的右半部分进行二分查找。通过不断重复这个过程，直到找到目标元素或搜索范围缩小到为空为止。 基本模板 找到大于等于target的第一个数（最左边）（最小化最大值） nums = [1, 2, 4, 5, 5, 6], target = 5 -> res = 3 位置越往左可能性越低（越不符合条件），所以需要符合if条件时r = m来逼近答案 123456int l = 0, r = n;while (l < r) { int m = l + (r-l)/2; if (nums[m] >= target) r = m; else l = m + 1;} 找 ...

并查集（union-find） 介绍 概念 当涉及到处理元素之间的等价关系、集合的合并与查询等问题时，它是一种用于维护不相交集合的有效方法，常被用于解决诸如连通性、网络连接状态、等价关系等问题。 核心思想 并查集通过构建一个森林（或者称为集合），其中每个元素都属于一个集合，每个集合以一个代表元素来标识。这样的数据结构可以高效地进行两个关键操作：查找和合并。 操作 查找（Find）： 查找一个元素所属的集合，通常以代表元素作为标识。这个操作通常用于判断两个元素是否属于同一个集合，即判断它们的代表元素是否相同。 123int find(int x) { return pa[x] == x ? x : (pa[x] = find(pa[x]));} 合并（Union）： 将两个不相交的集合合并为一个集合，即将两个集合的代表元素连接在一起。 1234567void union(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return; if (rank[ ...