哈希

题目特征

  1. 快速查找需求
    • 如判断元素是否存在（重复、交集等），或需要快速查询互补值（如两数之和）。
  2. 统计频率/次数
    • 统计字符、数字等的出现次数，例如变位词、多数元素问题。
  3. 唯一性/去重问题
    • 如找第一个不重复字符、去重后保留特定顺序等。
  4. 映射关系维护
    • 需建立元素间映射（如字符串同构），或记录元素的位置信息（如子数组问题）。
  5. 前缀和优化
    • 结合哈希表快速计算子数组和、差值等（如和为K的子数组）

常见解题思路

  1. 哈希集合（HashSet）
    • 存储唯一元素，用于去重或存在性判断。
      示例题：环形链表、快乐数、数组交集。
  2. 哈希映射（HashMap）
    • 记录键值对，存储元素及其索引、频率或其他关联信息。
      示例题：两数之和、变位词分组、克隆图的深拷贝。
  3. 前缀和 + 哈希表
    • 计算前缀和，用哈希表记录和的出现次数或最早出现位置。
      示例题：和为K的子数组、连续数组（0和1数量相等的最长子数组）。
  4. 滑动窗口 + 哈希表
    • 维护窗口内元素的哈希统计，用于子串/子数组问题。
      示例题：无重复字符的最长子串、最小覆盖子串。
  5. 频率统计与比较
    • 用哈希表统计频率后比较（如变位词），或用数组替代哈希优化空间（如仅小写字母的场景）。

优化技巧

  • 数组替代哈希表：若元素范围有限（如字母、固定范围的数字），使用数组更高效。
  • 双向映射：处理同构问题时，需双向检查两个哈希表的映射关系。
  • 延迟更新：在滑动窗口中，可延迟删除哈希表中的元素以简化逻辑（如某些子串问题）。

典型例题

  1. 两数之和（HashMap记录值与索引）
  2. 无重复字符的最长子串（滑动窗口 + HashMap记录字符最新位置）
  3. 字母异位词分组（HashMap以排序后的字符串为Key）
  4. 和为K的子数组（前缀和 + HashMap统计和出现次数）
  5. 最长连续序列（HashSet快速查找连续元素）

动态规划（DP）

题目特征

  1. 最优化问题
    • 如求最大值、最小值、最长/最短路径等。
  2. 重叠子问题
    • 问题可以分解为多个子问题，且子问题之间存在重叠（重复计算）。
  3. 无后效性
    • 当前状态只与之前的状态有关，而与之后的状态无关。
  4. 状态转移
    • 问题可以通过状态转移方程描述，即当前状态由之前的状态推导而来。

常见解题思路

  1. 定义状态
    • 明确问题的状态表示，通常用 dp[i] 或 dp[i][j] 表示某种条件下的最优解。
      示例：
    • dp[i]：以第 i 个元素结尾的子问题的解（如最长递增子序列）。
    • dp[i][j]：从位置 (0,0) 到 (i,j) 的解（如网格路径问题）。
  2. 状态转移方程
    • 根据问题的逻辑，推导出状态之间的关系。
      示例：
    • 斐波那契数列：dp[i] = dp[i-1] + dp[i-2]
    • 最长递增子序列：dp[i] = max(dp[i], dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]
    • 背包问题：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
  3. 初始化
    • 确定初始状态的值，通常为边界条件。
      示例：
    • dp[0] = 0 或 dp[0] = 1（根据问题需求）。
    • 二维 DP 问题中，通常需要初始化第一行和第一列。
  4. 计算顺序
    • 按照状态转移方程的逻辑，确定计算顺序（如从左到右、从下到上等）。
  5. 返回结果
    • 根据问题需求，返回 dp 数组中的某个值或最大值/最小值。

常见动态规划问题类型

  1. 线性 DP
    • 状态定义为一维数组，如斐波那契数列、最长递增子序列、最大子数组和。
  2. 二维 DP
    • 状态定义为二维数组，如网格路径问题、编辑距离、最长公共子序列。
  3. 背包问题
    • 0-1 背包、完全背包、多重背包等，状态转移涉及容量和物品选择。
  4. 区间 DP
    • 状态定义为区间，如石子合并、最长回文子串。
  5. 树形 DP
    • 在树结构上进行状态转移，如二叉树中的最大路径和。
  6. 状态压缩 DP
    • 通过位运算等技巧压缩状态，减少空间复杂度（如旅行商问题）。

解题步骤总结

  1. 分析问题是否满足动态规划的特征（最优化、重叠子问题、无后效性）。
  2. 定义状态，明确 dp 数组的含义。
  3. 推导状态转移方程，确定如何从子问题推导出当前问题。
  4. 初始化 dp 数组，处理边界条件。
  5. 按顺序计算 dp 数组，并返回最终结果。
  6. 考虑空间优化（如滚动数组）。

优化技巧

  1. 空间优化
    • 如果状态转移只依赖于前几个状态，可以用滚动数组或变量代替整个 dp 数组。
      示例：斐波那契数列中，只需两个变量 prev 和 curr。
  2. 记忆化搜索
    • 在递归中缓存子问题的解，避免重复计算（如自顶向下的 DP）。
  3. 预处理
    • 对输入数据进行预处理（如排序），简化状态转移逻辑。
  4. 边界条件处理
    • 注意处理边界条件，避免数组越界或逻辑错误。

典型例题

  1. 斐波那契数列（线性 DP）
  2. 最长递增子序列（线性 DP）
  3. 最大子数组和（线性 DP）
  4. 编辑距离（二维 DP）
  5. 0-1 背包问题（背包 DP）
  6. 最长回文子串（区间 DP）
  7. 打家劫舍（线性 DP + 空间优化）
  8. 三角形最小路径和（二维 DP + 空间优化）

贪心算法

题目特征

1. 明显的局部最优可推导全局最优

  • 问题可以通过每一步选择当前最优解，最终得到全局最优解。
  • 典型场景：最少操作次数、最大收益、最短时间等最优化问题。

2. 无后效性

  • 当前选择不会影响后续子问题的结构，后续状态仅依赖当前状态。

3. 常见问题类型

  • 区间调度：如最多不重叠活动、合并区间。
  • 分配问题：分糖果、任务调度。
  • 跳跃覆盖：能否到达终点、最少跳跃次数。
  • 数学规律：找零钱（特定面值）、加油站问题。
  • 压缩编码：哈夫曼编码、字符串重构。

常见解题思路

1. 排序 + 贪心遍历

  • 核心：通过排序预处理，使数据满足贪心选择的顺序。
  • 典型例题：
    • 合并区间：按左端点排序，合并右端点连续的区间。
    • 最多不重叠活动：按结束时间排序，选择最早结束的活动。

2. 优先队列（堆）维护当前最优

  • 核心：动态选择当前最优解（如最大值、最小值）。
  • 典型例题：
    • 合并K个有序链表：用小根堆每次取最小节点。
    • 任务调度器：优先处理剩余次数最多的任务，避免冷却时间。

3. 数学性质推导

  • 核心：利用问题中隐藏的数学规律直接决策。
  • 典型例题：
    • 跳跃游戏：维护当前能到达的最远距离，不回溯。
    • 加油站问题：总油量≥0时，必存在解；遍历找到剩余油量最低点的下一个站点。

4. 双向贪心或多次遍历

  • 核心：通过左右两次遍历或前后双指针满足不同条件。
  • 典型例题：
    • 分发糖果：左遍历保证右分高者多，右遍历保证左分高者多。
    • 接雨水：双指针从两端向中间逼近，计算局部凹陷。

优化技巧

1. 排序优化

  • 若问题只需局部有序，可用计数排序或桶排序降低时间复杂度。
    • 示例：任务调度器中按任务频率排序。

2. 空间压缩

  • 用变量替代数组，减少空间复杂度。
    • 示例：跳跃游戏中用 max_reach 替代DP数组。

3. 剪枝策略

  • 提前终止无效遍历。
    • 示例：加油站问题中，若当前油量不足则直接跳到下一个起点。

4. 数学替换

  • 将问题转化为数学公式，避免复杂逻辑。
    • 示例：柠檬水找零问题中，优先用10元找零，减少5元消耗。

易错点与注意事项

  1. 贪心策略的证明：必须验证局部最优能推导全局最优（可通过反证法或数学归纳）。
  2. 边界条件：如空输入、全零、单元素等情况需特殊处理。
  3. 排序规则：区间问题按左端点还是右端点排序，影响贪心逻辑。