# 常见算法

# 基础算法

  • 时间复杂度分析
  • 算法思想
  • 贪心算法
  • 分治
  • 动态规划
  • 回溯法
  • 枚举法
  • 排序算法

# 常考

  1. 数字题
  2. 二分
  3. 深度优化
  4. 图论
  5. DP 动态规划

# 算法范式

  • BF 算法 - 查找/搜索 所有可能性并选择最佳解决方案
    • 线性搜索
    • 雨水收集 诱导雨水问题
    • 递归楼梯 计算有共有多少种方法可以到达顶层 (4 种解题方案)
    • 最大子数列
    • 旅行推销员问题 尽可能以最短的路线访问每个城市并返回原始城市
    • 离散傅里叶变换 把时间信号解析成构成它的频率
  • 贪心法 - 在当前选择最佳选项,不考虑以后情况
    • 跳跃游戏
    • 背包问题
    • 戴克斯特拉算法- 找到所有图顶点的最短路径
    • 普里姆算法- 寻找加权无向图的最小生成树 (MST)
    • 克鲁斯卡尔算法- 寻找加权无向图的最小生成树 (MST)
  • 分治法 - 将问题分成较小的部分,然后解决这些部分
    • 二分查找
    • 汉诺塔
    • 杨辉三角形
    • 欧几里得算法- 计算最大公约数 (GCD)
    • 归并排序
    • 快速排序
    • 树深度优先搜索(DFS)
    • 图深度优先搜索(DFS)
    • 跳跃游戏
    • 快速算次方
    • 排列(有/无重复)
    • 组合(有/无重复)
  • 动态编程 - 使用以前找到的子解决方案构建解决方案
    • 斐波那契数
    • 跳跃游戏
    • 独特路径
    • 雨水收集 疏导雨水问题
    • 递归楼梯 计算有共有多少种方法可以到达顶层 (4 种解题方案)
    • 莱温斯坦距离 两个序列之间的最小编辑距离
    • 最长公共子序列 (LCS)
    • 最长公共子串
    • 最长递增子序列
    • 最短公共子序列
    • 0-1 背包问题
    • 整数拆分
    • 最大子数列
    • 贝尔曼-福特算法 找到所有图顶点的最短路径
    • 弗洛伊德算法 找到所有顶点对之间的最短路径
    • 正则表达式匹配
  • 回溯法 - 类似于 BF 算法 试图产生所有可能的解决方案,但每次生成解决方案测试如果它满足所有条件,那么只有继续生成后续解决方案。否则回溯并继续寻找不同路径的解决方案。
    • 跳跃游戏
    • 独特路径
    • 幂集 该集合的所有子集
    • 哈密顿图 恰好访问每个顶点一次
    • 八皇后问题
    • 骑士巡逻
    • 组合求和 从规定的总和中找出所有的组合
  • Branch & Bound - 记住在回溯搜索的每个阶段找到的成本最低的解决方案,并使用到目前为止找到的成本最小值作为下限。以便丢弃成本大于最小值的解决方案。通常,使用 BFS 遍历以及状态空间树的 DFS 遍历。