差分数组 1234a[0] a[1] a[2] a[3] a[4] (0)差分数组: a[0] a[1]-a[0] a[2]-a[1] a[3]-a[2] a[4]-a[3] (-a[4])对差分数组求前缀和: a[0] a[1] a[2] a[3] a[4] (0)// 考虑末尾0(-a[4])，那么差分数组之和sum=0 前缀和就是离散版本的“求积分”，差分数组就是离散版本的“求微分” 形成目标数组的子数组最少增加次数 给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。 答案保证在 32 位有符号整数以内。 示例 1： 1234567输入：target = [1,2,3,2,1]输出：3解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。[0,0,0,0,0] 将下标为 0 到 4 的元素（包 ...

前缀和 前缀和是一种数组变换方法，通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样，计算任意区间的和变得非常高效，只需一次前缀和计算即可，而不需要多次重复计算。 123int[] nums;int n = nums.length, sum[] = new int[n+1];sum[i+1] = sum[i] + nums[i]; 需要用sum[0]表示空数组的和 l到r的区间和表示为 sum[r+1] - sum[l] 例如，nums[0]到nums[5]的区间和表示为 sum[6] - sum[0] 二维前缀和 定义sum[i+1][j+1]表示左上角grid[0][0]，右下角grid[i][j]的子矩阵元素和 123456int[][] sum = new int[m + 1][n + 1];for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] ...

单调栈 单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，从栈顶添加和删除元素，其次栈中的所有元素单调递增或者单调递减 在一个队列Deque中，我们offer右边，poll左边，这样左边就是队首，右边是队尾 如果这个Deque作为栈，我们push和pop左边，并且把左边作为栈顶 单调性的判断是从栈顶到栈底（Deque中从左往右看） 单增栈：栈顶到栈底的元素是单调递增的，即栈顶的元素最小 单减栈：栈顶到栈底的元素是单调递减的，即栈顶的元素最大 后上界：对于数组中的某个元素 a[i]，它的后上界是指在它之后的第一个比它大的元素 后下界：对于数组中的某个元素 a[i]，它的后下界是指在它之后的第一个比它小的元素 单调栈在算法中的应用在于它能够在一次扫描(从左到右)即O(n)的复杂度之内找到数组中每一个元素的后上界(单增栈)或者后下界(单减栈) 496. 下一个更大元素 II: 递增栈获得每个元素的后上界 2866. 美丽塔 II(2072) 1944. 队列中可以看到的人数(2105) 2454. 下一个更大元素 IV(2175)：双单调栈 ...

二维偏序 概念 偏序关系满足： 反自反性（Reflexivity）： 对于集合中的每个元素，关系都与自身存在。 反对称性（Antisymmetry）： 如果存在a<=b && b<=a，则必须是a==b 传递性（Transitivity）： 如果存在a<=b && b<=c，则必须是a<=c 二维偏序问题涉及对一个二维数据集中元素的排序，其中排序不仅仅依赖于元素自身的大小关系，还可能依赖于元素在不同维度上的关系。 二维偏序是这样一类问题：已知点对的序列(a1,b1), (a2,b2), (a3,b3)...， 并在其上定义某种偏序关系<，现有点(ai,bi)，求满足(aj,bj) < (ai,bi)的的数量。 二维偏序问题一般是要使其中的一个维度有序，再通过树状数组的方式处理另一个维度 翻转对 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 示例 1: 12输入: ...

树状数组 概念 树状数组（Fenwick Tree）是一种数组实现的树状结构，常用于解决前缀和问题。它能够在O(log n)的时间内进行单点更新与区间查询操作，特别适用于在动态变化的数组中进行频繁的前缀和查询和更新。 通常需要对输入数据进行离散化，因为数据通常是不连续，而数组要求索引连续 操作 单点修改：更改数组中一个元素的值 区间查询：查询一个区间内所有元素的和 范围：[1, n]; 例如：7（111） 单点修改：111 -> 1000 区间查询：111 -> 110 -> 100 前缀和模板 注意不能add(0, val)，无法跳出循环，因为lowbit(0) = 0 1234567891011121314151617181920212223242526class FenwickTree { int[] tr; // [1, n] public FenwickTree(int[] nums) { // [0, n-1] this.tr = new int[nums.length+1]; f ...

基环树 (pseudotree) 在基环树中，除了环上的节点之外，其他节点都只属于一条路径，从根节点到其他节点都是唯一的。 每一个内向基环树（连通块）都由一个基环和其余指向基环的树枝组成 相关题解 2127. 参加会议的最多员工数

字典树 概念 字典树，也称为前缀树（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 ...

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

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] = ...

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