算法基础

基础算法

  • 排序：快速排序、归并排序、计数排序
  • 二分：整数二分、浮点数二分
  • 高精度：加、减、乘、除、取模
  • 前缀和与差分：一维、二维
  • 双指针算法：快慢指针、左右指针
  • 位运算：与、或、异或、左移、右移
  • 离散化：数值映射
  • 区间合并

数据结构

  • 链表与邻接表：图的存储
  • 栈与队列：单调队列、单调栈
  • KMP：字符串匹配
  • Trie：字典树
  • 并查集：集合合并与查询
  • 堆：优先队列
  • Hash表：哈希表

搜索与图论

  • DFS与BFS：图的遍历
  • 树与图的遍历：先序、中序、后序、层序遍历
  • 拓扑排序：有向无环图的排序
  • 最短路：Dijkstra、Bellman-Ford、Floyd-Warshall
  • 最小生成树：Prim、Kruskal
  • 二分图：染色法、匈牙利算法

数学知识

  • 质数：判断质数、筛选质数
  • 约数：求约数个数、求约数之和
  • 欧拉函数：求欧拉函数值
  • 快速幂：快速计算幂次
  • 扩展欧几里得算法：求解不定方程
  • 中国剩余定理：求解模线性方程组
  • 高斯消元：求解线性方程组
  • 组合计数：排列组合、卡特兰数
  • 容斥原理：计数问题
  • 简单博弈论：Nim游戏
  • 动态规划：背包问题、线性DP、区间DP、计数类DP、数位统计DP、状态压缩DP、树形DP、记忆化搜索
  • 贪心