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. 数组元素的目标和
• AcWing 2816. 判断子序列

位运算

• AcWing 801. 二进制中1的个数 - 文章链接

离散化

• AcWing 802. 区间和

区间合并

• AcWing 803. 区间合并 - 文章链接

第二讲、数据结构

单链表

• AcWing 826. 单链表

双链表

• AcWing 827. 双链表

栈

• AcWing 828. 模拟栈
• AcWing 3302. 表达式求值

队列

• AcWing 829. 模拟队列

单调栈

• AcWing 830. 单调栈

单调队列

• AcWing 154. 滑动窗口

KMP

• AcWing 831. KMP字符串

Trie

• AcWing 835. Trie字符串统计
• AcWing 143. 最大异或对

并查集

• AcWing 836. 合并集合
• AcWing 837. 连通块中点的数量
• AcWing 240. 食物链

堆

• AcWing 838. 堆排序
• AcWing 839. 模拟堆

哈希表

• AcWing 840. 模拟散列表
• AcWing 841. 字符串哈希

第三讲、搜索与图论

DFS

• AcWing 842. 排列数字
• AcWing 843. n-皇后问题

BFS

• AcWing 844. 走迷宫
• AcWing 845. 八数码

树与图的深度优先遍历

• AcWing 846. 树的重心

树与图的广度优先遍历

• AcWing 847. 图中点的层次

拓扑排序

• AcWing 848. 有向图的拓扑序列

Dijkstra

• AcWing 849. Dijkstra求最短路 I
• AcWing 850. Dijkstra求最短路 II

bellman-ford

• AcWing 853. 有边数限制的最短路

spfa

• AcWing 851. spfa求最短路
• AcWing 852. spfa判断负环

Floyd

• AcWing 854. Floyd求最短路

Prim

• AcWing 858. Prim算法求最小生成树

Kruskal

• AcWing 859. Kruskal算法求最小生成树

染色法判定二分图

• AcWing 860. 染色法判定二分图

匈牙利算法

• AcWing 861. 二分图的最大匹配

第四讲、数学知识

质数

• AcWing 866. 试除法判定质数
• AcWing 867. 分解质因数
• AcWing 868. 筛质数

约数

• AcWing 869. 试除法求约数
• AcWing 870. 约数个数
• AcWing 871. 约数之和
• AcWing 872. 最大公约数

欧拉函数

• AcWing 873. 欧拉函数
• AcWing 874. 筛法求欧拉函数

快速幂

• AcWing 875. 快速幂
• AcWing 876. 快速幂求逆元

扩展欧几里得算法

• AcWing 877. 扩展欧几里得算法
• AcWing 878. 线性同余方程

中国剩余定理

• AcWing 204. 表达整数的奇怪方式

高斯消元

• AcWing 883. 高斯消元解线性方程组
• AcWing 884. 高斯消元解异或线性方程组

求组合数

• AcWing 885. 求组合数 I
• AcWing 886. 求组合数 II
• AcWing 887. 求组合数 III
• AcWing 888. 求组合数 IV
• AcWing 889. 满足条件的01序列

容斥原理

• AcWing 890. 能被整除的数

博弈论

• AcWing 891. Nim游戏
• AcWing 892. 台阶-Nim游戏
• AcWing 893. 集合-Nim游戏
• AcWing 894. 拆分-Nim游戏

第五讲、动态规划

背包问题

• AcWing 2. 01背包问题
• AcWing 3. 完全背包问题
• AcWing 4. 多重背包问题
• AcWing 5. 多重背包问题 II
• AcWing 9. 分组背包问题

线性DP

• AcWing 898. 数字三角形
• AcWing 895. 最长上升子序列
• AcWing 896. 最长上升子序列 II
• AcWing 897. 最长公共子序列
• AcWing 902. 最短编辑距离
• AcWing 899. 编辑距离

区间DP

• AcWing 282. 石子合并

计数类DP

• AcWing 900. 整数划分

数位统计DP

• AcWing 338. 计数问题

状态压缩DP

• AcWing 291. 蒙德里安的梦想
• AcWing 91. 最短Hamilton路径

树形DP

• AcWing 285. 没有上司的舞会

记忆化搜索

• AcWing 901. 滑雪

第六讲、贪心

区间问题

• AcWing 905. 区间选点
• AcWing 908. 最大不相交区间数量
• AcWing 906. 区间分组
• AcWing 907. 区间覆盖

Huffman树

• AcWing 148. 合并果子

排序不等式

• AcWing 913. 排队打水

绝对值不等式

• AcWing 104. 货仓选址

推公式

• AcWing 125. 耍杂技的牛