字符串匹配 问题描述 给定文本串  和模式串 ，要求找出  中所有与  相同的子串的起始位置。 KMP算法 算法思想  利用已匹配的信息，避免不必要的比较 构建next数组（失配函数），记录最长相等前后缀 失配时根据next数组回退模式串  时间复杂度  预处理时间： 匹配时间： 空间复杂度：  代码实现   c++   java   python   class Solution { private: vector<int> buildNext(string& pattern) { int m = pattern.length(); vector<int> n...

字符串 字符串匹配 字符串匹配是在文本串中查找模式串出现位置的过程。 特点  预处理时间： 或 ，其中  是模式串长度， 是字符集大小 匹配时间：从  到  不等 适用于文本搜索、生物序列比对等场景  分类    算法 时间复杂度 空间复杂度 特点     朴素匹配   简单直观   KMP   线性时间   Sunday   实际效率高   Boyer-Moore   从右向左匹配   AC自动机   多模式匹配    字符串哈希 字符串哈希是将字符串映射为整数的技术。 特点  预处理时间： 查询时间： 适用于快速字符串比较和子串查询  分类    算法 问题描述 特点     单哈希 使用...

分组背包 问题描述 有  组物品，每组物品有若干个，每组物品中最多只能选择一个。每个物品有重量  和价值 ，其中  表示组号， 表示组内编号。现在有一个容量为  的背包，求解在不超过背包容量的情况下，能够装入物品的最大价值。 与其他背包的区别  01背包：每个物品最多选择1次 完全背包：每个物品可以选择无限次 多重背包：每个物品可以选择有限次 分组背包：物品分组，每组最多选择1个  动态规划解法 状态定义   表示考虑前  组物品，背包容量为  时能获得的最大价值  状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i][k]] + v[i][k]) ...

多重背包 问题描述 有  个物品，每个物品有重量 、价值  和数量限制 。现在有一个容量为  的背包，每个物品最多选择  次，求解在不超过背包容量的情况下，能够装入物品的最大价值。 与其他背包的区别  01背包：每个物品最多选择1次 完全背包：每个物品可以选择无限次 多重背包：每个物品可以选择  次  基本解法 状态定义   表示考虑前  个物品，背包容量为  时能获得的最大价值  状态转移方程 dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]) 其中 k∈[0,s[i]] 且 k*w[i] ≤ j  二进制优化 将每个物品的数量  进行二进制拆分，转化为01...

完全背包 问题描述 有  个物品，每个物品有重量  和价值 。现在有一个容量为  的背包，每个物品可以选择任意次（无限次），求解在不超过背包容量的情况下，能够装入物品的最大价值。 与01背包的区别  01背包：每个物品最多选择一次 完全背包：每个物品可以选择无限次  动态规划解法 状态定义   表示考虑前  个物品，背包容量为  时能获得的最大价值  状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) if j >= w[i] dp[i][j] = dp[i-1][j] if j < w[i]  注意：与01背包的区别是 ...

01背包 问题描述 有  个物品，每个物品有重量  和价值 。现在有一个容量为  的背包，每个物品要么选要么不选（0-1），求解在不超过背包容量的情况下，能够装入物品的最大价值。 动态规划解法 状态定义   表示考虑前  个物品，背包容量为  时能获得的最大价值  状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) if j >= w[i] dp[i][j] = dp[i-1][j] if j < w[i]  初始状态   表示不选任何物品时的价值为0  表示背包容量为0时的价值为0  代码实现 C++ 实现（二维） ...

动态规划 动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的算法思想。 基本概念 核心思想  最优子结构：问题的最优解包含子问题的最优解 重叠子问题：子问题会重复出现，可以保存子问题的解 无后效性：某阶段的状态确定后，后续状态的演变不再受此前各状态及决策的影响  解题步骤  确定状态和选择 明确 dp 数组的定义 找出状态转移方程 确定初始条件和边界情况 确定遍历顺序  常见类型 线性 DP   单序列问题  最长上升子序列 最大子数组和 打家劫舍    双序列问题  最长公共子序列 编辑距离 正则表达式匹配    区间 ...

邮局选址 问题描述 在一个以XY轴表达的城市里， 个居民点散乱分布，居民点位置可以用坐标  表示。任意两点  和  间距离可以用  度量（曼哈顿距离）。居民希望在城市中选择建立邮局的最佳位置，使得  个居民点到邮局的距离总和最小。 贪心策略 这个问题可以将横纵坐标分开考虑，对答案没影响。问题可以转换为在一维坐标轴上选择一个点，使得所有点到它的距离和最小。 贪心策略：选择居民点的中位数位置建立邮局可以使总距离最小。 原因：  假设有两个点 、，需要放置点  如果  放在  之间，距离和为  如果  放在  外部，距离和为  所以最优解一定在中位数位置  算法实现   c++   java   p...

排队等待 问题描述 有 n 个顾客需要服务，每个顾客有一个服务时间  和等待成本系数 。顾客的等待成本为：等待时间 × 等待成本系数。求一个服务顺序，使得所有顾客的总等待成本最小。 贪心策略  按照服务时间和等待成本系数的比值  升序排序 按照排序后的顺序依次服务顾客  正确性证明 假设最优解中存在相邻的两个顾客 i 和 j，且 。 交换这两个顾客的位置：  i 的等待成本减少： j 的等待成本增加：  总成本变化： 由于 ，所以  因此交换后总成本增加，与最优解假设矛盾。 算法实现   c++   java   python   class Solution { public: vector...

区间最少点覆盖 问题描述 给定 n 个闭区间 ，求最少需要多少个点，使得每个区间内至少包含一个点。 贪心策略  将所有区间按左端点升序排序 维护当前所有未覆盖区间的最小右端点 当遇到左端点大于当前最小右端点时，需要新增一个点  算法实现   c++   java   python   class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { if (points.empty()) return 0; // 按左端点升序排序 sort(points.begin(), ...

排序 C++ 排序 sort 函数 // 头文件 #include <algorithm> // 升序排序（默认） sort(arr, arr + n); // 数组 sort(vec.begin(), vec.end()); // vector // 降序排序 sort(arr, arr + n, greater<int>()); // 数组 sort(vec.begin(), vec.end(), greater<int>()); // vector // 自定义比较函数 bool cmp(int a, int b) { return a > b;...

贪心 贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法策略。 贪心算法的特点  局部最优选择：每一步都做出在当前看来最好的选择 不可回退：一旦做出选择，就不能返回重新选择 简单高效：实现相对简单，执行效率通常较高  贪心算法的应用场景  找零钱问题 活动选择问题 区间调度问题 最小生成树（Prim算法、Kruskal算法） 哈夫曼编码  贪心算法的解题步骤  将问题分解为若干个子问题 找出适合的贪心策略 求解每个子问题的最优解 将局部最优解堆叠成全局最优解  贪心算法的优缺点 优点  简单直观 解题速度快 适用...

二维动态差分（区修单查） 二维动态差分是二维差分的动态实现，通过二维树状数组维护差分数组，可以在  的时间复杂度内完成子矩阵修改和单点查询操作。 基本概念 二维动态差分的核心思想是：  使用二维树状数组维护差分数组 子矩阵修改转化为四个点的修改 单点查询通过二维前缀和实现 适用于子矩阵修改和单点查询交替的场景  实现方式 二维动态差分的关键操作：  update：修改差分数组某个位置的值 query：查询差分数组的二维前缀和 rangeAdd：子矩阵增加操作 pointQuery：单点查询  基本实现   c++   java   python   class DynamicDifferenc...

二维静态差分 二维差分是一维差分在二维平面上的扩展，用于处理矩阵的子矩阵修改问题。 通过二维差分数组，可以将子矩阵修改的时间复杂度从  优化到 。 基本概念 二维差分的核心思想是：  构建二维差分数组 ，其中  表示相邻格子的差值 子矩阵修改转化为差分数组的四个点的修改 原矩阵可以通过二维前缀和还原 适用于频繁进行子矩阵修改的场景  实现方式 二维差分的实现步骤：  构建二维差分数组 通过四点修改实现子矩阵增加 通过二维前缀和还原原矩阵 处理查询操作  基本实现   c++   java   python   class Difference2D { private: vector<ve...