AcWing算法基础

AcWing的算法相关课程可以用来打牢基础，把所有的经典算法手敲一遍后可以加深理解和记忆。这里总结了所有相关的内容和打卡记录。

一、基础算法

• 排序
  • AcWing 785. 快速排序
  • AcWing 786. 第k个数
  • AcWing 787. 归并排序
  • AcWing 788. 逆序的数量
• 二分
  • AcWing 789. 数的范围
  • AcWing 790. 数的三次方根
• 高精度
  • AcWing 791. 高精度加法
  • AcWing 792. 高精度减法
  • AcWing 793. 高精度乘法
  • AcWing 794. 高精度除法
• 前缀和与差分
  • AcWing 795. 前缀和
  • AcWing 796. 子矩阵的和
  • AcWing 797. 差分
  • AcWing 798. 差分矩阵
• 双指针算法
  • AcWing 799. 最长连续不重复子序列
  • AcWing 800. 数组元素的目标和
• 位运算
• 离散化
• 区间合并

二、数据结构

• 链表与邻接表：树与图的存储
• 栈与队列：单调队列、单调栈
• kmp
• Trie
• 并查集
• 堆
• Hash表

三、搜索与图论

• DFS与BFS
• 树与图的遍历：拓扑排序
• 最短路
• 最小生成树
• 二分图：染色法、匈牙利算法

四、数学知识

• 质数
• 约数
• 欧拉函数
• 快速幂
• 扩展欧几里得算法
• 中国剩余定理
• 高斯消元
• 组合计数
• 容斥原理
• 简单博弈论

五、动态规划

• 背包问题
• 线性DP
• 区间DP
• 计数类DP
• 数位统计DP
• 状态压缩DP
• 树形DP
• 记忆化搜索

六、贪心

七、时空复杂度分析