Caesar-Victory/ACWing

ACWing

第一章 基础知识

1. 快速排序
   • 912. 排序数组 - 力扣（LeetCode）
2. 归并排序
   • 912. 排序数组 - 力扣（LeetCode）
3. 二分
   1. 整数二分；
      • 69. x 的平方根 - 力扣（LeetCode）
   2. 浮点数二分；
4. 高精度
   1. 高精度加法
   2. 高精度减法
   3. 高精度乘法
   4. 高精度除法
5. 前缀与差分
   1. 一维前缀和
      • 2485. 找出中枢整数 - 力扣（LeetCode）
   2. 二维前缀和
   3. 前缀和
      • 862. 和至少为 K 的最短子数组 - 力扣（Leetcode）
      • https://leetcode.cn/problems/subarray-sum-equals-k/description/
   4. 差分
      • 370. 区间加法 - 力扣（LeetCode）
      • 1094. 拼车 - 力扣（LeetCode）
      • 基础算法：差分讲解_八百标兵奔北坡666的博客-CSDN博客_差分计算公式
   5. 差分矩阵
6. 离散化
   • 493. 翻转对 - 力扣（LeetCode）
   • 1036. 逃离大迷宫 - 力扣（LeetCode）
   • 1854. 人口最多的年份 - 力扣（LeetCode）
7. xxx

第二章 数据结构

1. 单链表

2. 双链表

3. 栈

4. 队列

5. 单调栈

6. 单调队列

7. KMP

   • 28. 找出字符串中第一个匹配项的下标 - 力扣（Leetcode）

8. Trie

9. 并查集

10. 堆

    • 1046. 最后一块石头的重量 - 力扣（Leetcode）

11. 哈希表

    1. 拉链法
    2. 开放寻址法
    3. 字符串前缀哈希法[polymonial rolling hash]
       • 1044. 最长重复子串 - 力扣（Leetcode）
       • 1392. 最长快乐前缀 - 力扣（Leetcode）
       • 备注：同时兼容KMP
       • 2223. 构造字符串的总得分和 - 力扣（Leetcode）

第三章 搜索与图论

DFS

BFS

• 1254. 统计封闭岛屿的数目 - 力扣（Leetcode）
• 1020. 飞地的数量 - 力扣（Leetcode）
• 1905. 统计子岛屿 - 力扣（Leetcode）

树与图的优先遍历

树与图的广度优先遍历

拓扑排序

Dijkstra

• 847. 访问所有节点的最短路径 - 力扣（Leetcode）
• 743. 网络延迟时间 - 力扣（Leetcode）

Bellman-Ford算法

SPFA算法

Floyd[2022.11.28]

Prim

Kruskal

染色法判定二分图

匈牙利算法

第四章 数论

筛质数

• P3912 素数个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 204. 计数质数 - 力扣（Leetcode）

• 核心模式注意数组和变量初始化，全局变量放置在 class Solution里面；

• Python 不方便直接处理除法的取余问题，可以直接转化为乘法；

• Python 不便于使用指针的同时嵌套数组的值作为for循环的判断条件，指针声明+while语句即可解决；

分解质因数 快速幂 约数个数 欧拉函数 同余 矩阵乘法 组合计数 高斯消元 容斥原理 概率与数学期望 博弈论

最后一部分：调试技巧

1. 边界判断，输出的值，其数量超过预期，有可能是边界问题，应当考虑数值为0的情况；
2. 涉及到多个函数，可以注释大多数保留一个，逐个子函数调试，并且在对应位置查看输出；
3. 高频出错点：for循环的上界和下界；变量名；自增减运算符前后位置；