机试学习

记录算法问题的学习路线，提高机试学习效率，持续提升机试代码能力。

1 知识点概览

Type	Knowledge
基础算法	双指针、差分、滑动窗口、二分、贪心
数据结构	线段树 、单调栈、堆、Trie树
动态规划	动态规划

---

2 数据范围分析

根据数据范围的复杂度和算法内容，ACM或笔试题的时间限制一般为1~2秒。

在这种情况下，C++代码中的操作次数控制在 $10^7~10^8$ 为最佳。下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

Data Range	Time Complexity	Common Algorithm
$n≤30$	指数级别	dfs+剪枝，状态压缩dp
$n≤10^2$	$O(n^3)$	floyd，dp，高斯消元
$n≤10^3$	$O(n^2)$、 $O(n²logn)$	dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n≤10^4$	$O(n∗\sqrt{n})$	块状链表、分块、莫队
$n≤10^5$	$O(nlogn)$	各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
$n≤10^6$	常数较小的 $O(nlogn)$	单调队列、 hash、双指针扫描、BFS、并查集，kmp、AC自动机
$n≤10^7$	$O(n)$	双指针扫描、kmp、AC自动机、线性筛素数
$n≤10^9$	$O(\sqrt{n})$	判断质数
$n≤10^{18}$	$O(logn)$	最大公约数，快速幂，数位DP
$n≤10^{1000}$	$O((logn)²)$	高精度加减乘除
$n≤10^{100000}$	$O(logk×loglogk)$	$k$ 表示位数，高精度加减、FFT/NTT

---

3 刷题记录

ID	平台	题单名称	状态	完成时间
1	Acwing	算法基础课	Ongoing
2	Acwing	蓝桥杯每日一题	Ongoing
3	Acwing	算法竞赛进阶指南	Ongoing
5	Leetcode	Leetcode热题100	Over	2024.07.27
6	Leetcode	动态规划（基础版）	Over	2024.10.08
7	Leetcode	「新」动计划·编程入门	Over	2024.07.23
8	Leetcode	面试经典150题	Ongoing
9	Leetcode	119经典题变种挑战	Ongoing
10	Leetcode	30天Pandas挑战	Over	2024.11.27
11	Nowcoder	笔试必刷TOP101	Ongoing
12	Nowcoder	输入输出练习	Ongoing
13	Leetcode	高频 SQL 50 题（基础版）	Ongoing