滑动窗口 问题描述 滑动窗口是一种在数组或字符串上使用双指针维护一个区间的技术。 通常，两个指针同向移动，通过动态更新区间内的信息来解决问题。 定长窗口 算法思想  维护固定大小的窗口 窗口右移时更新区间信息 适用于求解连续子数组的统计问题 时间复杂度   代码实现   c++   java   python   class Solution { public: vector<double> movingAverage(vector<int>& nums, int k) { vector<double> result; int n = nums.si...

对撞指针 问题描述 对撞指针是一种在有序数组中使用两个相向移动的指针来解决问题的技术。 通常，一个指针从左向右移动，另一个指针从右向左移动，直到满足特定条件或指针相遇。 两数之和 算法思想  在有序数组中使用左右指针 如果和大于目标值，右指针左移 如果和小于目标值，左指针右移 如果和等于目标值，找到答案  代码实现   c++   java   python   class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right =...

快慢指针 问题描述 快慢指针是一种在链表中使用两个移动速度不同的指针来解决问题的技术。 通常，快指针每次移动两步，慢指针每次移动一步。 环形检测 算法思想  使用快慢指针在链表上移动 如果存在环，两个指针一定会相遇 相遇后，将一个指针移到起点，两个指针同速前进 再次相遇的点即为环的入口  代码实现   c++   java   python   class Solution { public: ListNode* detectCycle(ListNode* head) { if (!head || !head->next) return nullptr; // 快慢指针找相遇点 List...

双指针 快慢指针 快慢指针是一种在线性数据结构上使用两个不同速度指针的技术。 特点  时间复杂度： 空间复杂度： 适用于环形检测、中点查找等场景  分类    算法 问题描述 特点     环形检测 检测链表是否有环 快指针每次移动2步   中点查找 查找链表中点 快指针每次移动2步   倒数第k个 查找倒数第k个节点 快指针先走k步   链表相交 判断两个链表是否相交 对齐后同速前进    对撞指针 对撞指针是一种在有序数组中使用两个相向移动的指针的技术。 特点  时间复杂度： 空间复杂度： 适用于查找、排序等场景  分类    算法 问题描述 特点     二分查找 有序数组中查找元素 相...

回文串 问题描述 给定一个字符串 ，判断其是否为回文串，或者找出其中的最长回文子串。 回文串是指正着读和倒着读都一样的字符串。 Manacher算法 算法思想  在字符串间插入特殊字符，统一奇偶长度的回文串处理 利用已有回文信息，避免重复计算 维护当前最右回文边界，加速匹配过程  时间复杂度  预处理时间： 查找时间： 空间复杂度：  代码实现   c++   java   python   class Solution { private: string preProcess(string& s) { string t = "#"; for (char c : s...

字典树 问题描述 字典树（Trie）是一种用于高效存储和查找字符串的树形数据结构。 每个节点代表一个字符，从根节点到某一节点的路径上的字符连接起来，表示该节点对应的字符串。 基本操作 算法思想  将字符串集合构建成树形结构 每个节点包含多个子节点（通常为26个小写字母） 使用标记表示某个节点是否为字符串的结尾 利用字符串的公共前缀来节省空间  时间复杂度  插入时间：，其中  是字符串长度 查找时间： 空间复杂度：，其中  是字符串总长度， 是字符集大小  代码实现   c++   java   python   class Trie { private: struct TrieNode { ...

字符串哈希 问题描述 将字符串映射为整数，使得：  相同的字符串映射到相同的整数 不同的字符串尽量映射到不同的整数 能够快速计算子串的哈希值  字符串哈希算法 算法思想  选择一个大质数作为模数  选择一个进制数  (通常为131或13331) 将字符串看作  进制数，对  取模 使用前缀和思想预处理子串哈希值  时间复杂度  预处理时间： 查询时间： 空间复杂度：  代码实现   c++   java   python   class StringHash { private: const int P = 131; const long long M = 1e9 + 7; vector&lt...

字符串匹配 问题描述 给定文本串  和模式串 ，要求找出  中所有与  相同的子串的起始位置。 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   单序列问题  最长上升子序列 最大子数组和 打家劫舍    双序列问题  最长公共子序列 编辑距离 正则表达式匹配    区间 ...