本文完整同步自个人求职工作区,更新于 2026-08-31。源文件及后续更新托管在 GitHub 仓库 llm-algo-job-notes。
面向:能做简单题 → 冲国内大厂笔试。这里收录的是 Hot100 覆盖不到、但字节/美团/华为/拼多多笔试高频的考点。 大厂笔试 = ACM 模式(自读 stdin)+ 3~5 题难度递增 + 部分分制。前 2 题靠 Hot100 Medium,第 3~4 题就靠本篇。 每篇仍是 9 件套。所有 ACM 模板都可
python x.py < in.txt直接跑。
本篇总览
| # | 考点 | 一句话触发条件 | 优先级 |
|---|---|---|---|
| 28 | 二分答案 | 「最大值最小 / 最小值最大 / 能否在 x 下完成」 | ⭐⭐⭐ 必背 |
| 29 | 差分数组 | 「区间批量加减」「多次区间修改后查最终值」 | ⭐⭐⭐ 必背 |
| 30 | 最短路 Dijkstra / 0-1 BFS | 「带权图求最短距离 / 最小代价」 | ⭐⭐⭐ 必背 |
| 31 | 快速幂 + 取模 | 「结果对 1e9+7 取模」「求 a^b」 | ⭐⭐⭐ 必背 |
| 32 | 数论基础 | GCD/LCM、判质数、质数筛、质因数分解 | ⭐⭐ 高频 |
| 33 | 区间调度贪心 | 「最多不重叠区间 / 最少箭 / 会议室」 | ⭐⭐ 高频 |
| 34 | 单调队列 | 「定长滑动窗口的最大/最小值」 | ⭐⭐ 高频 |
| 35 | 模拟题套路 | 「读懂一大段规则,按步骤实现」 | ⭐⭐ 高频(华为/美团) |
一周时间分配建议:28–31 必须吃透(占笔试难题的一大半);32–35 有时间就过。文末列了「一周不建议碰」的考点,别浪费时间。
28. 二分答案(在答案空间上二分)
识别信号
- 「最大值最小化 / 最小值最大化」「求满足条件的最小/最大的那个值」。
- 「能否在容量/时间/速度 = x 的条件下完成?」且这个「能否」随 x 单调(x 越大越容易/越难)。
- 关键词:最小速度、最大间距、最少天数、最小的最大负载、分割数组。
为什么
虽然数组本身无序,但「答案」有单调性:如果 x 可行,那 x+1 也可行(或反之)。于是在答案的取值范围 [lo, hi] 上二分,用一个 check(x) 判定可行性,把「求最优值」变成「找可行/不可行的分界点」。
解题步骤
- 确定答案范围
lo, hi(最小可能值、最大可能值)。 - 写
check(x):在「限制 = x」下能否满足要求(通常 O(n) 扫一遍)。 - 二分找第一个可行(最小化)或最后一个可行(最大化)的 x。
Python 模板
# 通法:最小化「最大值」——找第一个可行的 x
def min_feasible(lo, hi, check):
# 契约:整数闭区间 [lo, hi] 内存在答案,check 单调 False -> True
# 循环不变量:第一个可行值始终在 [lo, hi]
if lo > hi or not check(hi):
raise ValueError("[lo, hi] must contain a feasible value")
while lo < hi:
mid = (lo + hi) // 2
if check(mid): # mid 可行 → 尝试更小
hi = mid
else:
lo = mid + 1
return lo
# 例:爱吃香蕉的珂珂——h 小时吃完的最小速度
def min_eating_speed(piles, h):
def check(k):
return sum((p + k - 1) // k for p in piles) <= h # 向上取整求小时数
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if check(mid): hi = mid
else: lo = mid + 1
return lo
# 例:分割数组的最大值最小(把数组分成 m 段,最小化各段和的最大值)
def split_array(nums, m):
def check(cap): # 每段和不超过 cap,能否分成 <= m 段
cnt, cur = 1, 0
for x in nums:
if cur + x > cap:
cnt += 1; cur = 0
cur += x
return cnt <= m
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if check(mid): hi = mid
else: lo = mid + 1
return lo
ACM 模板
import sys
def main():
data = sys.stdin.read().split()
n, h = int(data[0]), int(data[1])
piles = list(map(int, data[2:2 + n]))
def check(k):
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if check(mid): hi = mid
else: lo = mid + 1
print(lo)
main()
复杂度:O(n · log(值域))。check 一般 O(n),二分 log(hi-lo) 次。
典型题:爱吃香蕉的珂珂、在 D 天内送达包裹的最低运力、分割数组的最大值、最小化最大距离、制作 m 束花所需最少天数。
常见坑
- 先想清是「找第一个可行」还是「最后一个可行」,模板的
hi=mid/lo=mid+1别写反。 - 上面模板的明确不变量是:答案始终在闭区间
[lo, hi],且check为False -> True;初始hi必须可行。否则别直接返回hi制造一个“看起来合理”的错答案。 check里向上取整用(p+k-1)//k,别用浮点。
口诀:最大最小求分界,答案空间上二分。
29. 差分数组(区间批量修改的逆前缀和)
识别信号
- 「对区间
[l, r]整体加 val」这类操作做很多次,最后才查询数组的最终形态。 - 「多个航班/时间段叠加」「区间覆盖计数」「n 个操作后求每个位置的值」。
为什么
朴素做法每次区间修改 O(n),m 次就 O(nm)。差分数组把「区间修改」变成两个端点的单点修改:d[l]+=val, d[r+1]-=val,最后对 d 求一次前缀和就还原出结果,总复杂度 O(n+m)。差分是前缀和的逆运算。
解题步骤
- 建差分数组
d(长度 n+1,防越界)。 - 每个区间操作
[l,r]+val:d[l]+=val; d[r+1]-=val。 - 对
d求前缀和,得到每个位置的最终值。
Python 模板
def apply_range_updates(n, ops):
# ops: [(l, r, val), ...] 对闭区间 [l,r] 都加 val
d = [0] * (n + 1)
for l, r, val in ops:
d[l] += val
d[r + 1] -= val # r+1 处抵消,所以开 n+1
res, cur = [], 0
for i in range(n):
cur += d[i] # 前缀和还原
res.append(cur)
return res
# 二维差分(矩阵区间加)——大厂偶尔考
def diff_2d(rows, cols, ops):
d = [[0]*(cols+1) for _ in range(rows+1)]
for r1, c1, r2, c2, val in ops: # 左上(r1,c1)到右下(r2,c2)
d[r1][c1] += val
d[r1][c2+1] -= val
d[r2+1][c1] -= val
d[r2+1][c2+1] += val
# 二维前缀和还原
for i in range(rows):
for j in range(cols):
up = d[i-1][j] if i else 0
left = d[i][j-1] if j else 0
ul = d[i-1][j-1] if i and j else 0
d[i][j] += up + left - ul
return [row[:cols] for row in d[:rows]]
ACM 模板
import sys
def main():
data = sys.stdin.read().split()
idx = 0
n, m = int(data[idx]), int(data[idx+1]); idx += 2
d = [0]*(n+1)
for _ in range(m):
l, r, val = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
d[l] += val; d[r+1] -= val
out, cur = [], 0
for i in range(n):
cur += d[i]; out.append(str(cur))
print(' '.join(out))
main()
复杂度:m 次区间修改 + 一次还原 = O(n + m)。
典型题:航班预订统计、拼车(判断能否完成)、区间加法后求最大值、一维/二维区间覆盖。
常见坑
d要开n+1长度,d[r+1]才不越界。- 差分只适合「先批量改、最后统一查」;如果「边改边查任意区间」要用树状数组/线段树。
- 下标从 0 还是 1 开始,
r+1的位置要对应好。
口诀:区间加变两端点,差分还原前缀和。
30. 最短路:Dijkstra / 0-1 BFS
识别信号
- 「带权图求两点间最短距离 / 最小花费 / 最小时间」,边权非负。
- 「网格里每步代价不同,求到终点最小代价」。
- 边权只有 0 和 1 → 用 0-1 BFS(双端队列),比 Dijkstra 更快。
为什么 无权图用普通 BFS 就够;一旦边有不同权重,BFS 的「层 = 距离」不成立,要用 Dijkstra:每次从「已知最短的未确定点」向外扩,用小顶堆快速取最小。边权只有 0/1 时,0 权边放队头、1 权边放队尾,普通双端队列即可替代堆。
解题步骤(Dijkstra)
dist[]初始化 INF,dist[src]=0,起点入小顶堆(0, src)。- 弹出堆顶(当前最短);若是过期记录(
d > dist[u])跳过。 - 松弛所有邻边:
dist[u]+w < dist[v]就更新并入堆。
Python 模板
import heapq
# Dijkstra 堆优化(邻接表 graph[u] = [(v, w), ...])
def dijkstra(n, graph, src):
INF = float('inf')
dist = [INF] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 过期记录,跳过
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
# 0-1 BFS(边权只有 0/1):双端队列,0 权头进、1 权尾进
from collections import deque
def zero_one_bfs(n, graph, src):
INF = float('inf')
dist = [INF] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in graph[u]: # w ∈ {0, 1}
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
ACM 模板
import sys, heapq
def main():
data = sys.stdin.read().split()
idx = 0
n, m = int(data[idx]), int(data[idx+1]); idx += 2
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, w = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
graph[u].append((v, w))
graph[v].append((u, w)) # 无向图再加反向;有向图删掉这行
INF = float('inf'); dist = [INF]*n; dist[0] = 0
pq = [(0, 0)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w; heapq.heappush(pq, (dist[v], v))
print(' '.join(str(x) if x != INF else '-1' for x in dist))
main()
复杂度:Dijkstra 堆优化 O((n+m) log n);0-1 BFS O(n+m)。
典型题:网络延迟时间、到达目标的最小花费、最小体力消耗路径(网格)、概率最大路径。K 站中转内最便宜航班必须把「已用边数」加入状态,不能直接套本节的一维 dist 模板。
常见坑
- Dijkstra 只适用非负权;有负权要用 Bellman-Ford / SPFA。
- 有「最多 K 步/站」约束时,最短路状态至少要包含
(节点,已用步数),或改用分层 Bellman-Ford。 - 一定要判「过期记录」
if d > dist[u]: continue,否则堆里旧值会拖慢甚至出错。 - 无向图建边要双向都加。
口诀:带权最短用堆扩,松弛跳过过期值。
31. 快速幂 + 取模(大数幂与模运算)
识别信号
- 题目要求「结果对
1e9+7(或998244353)取模」。 - 求
a^b,其中 b 极大(如 1e9),普通循环会超时。 - 关键词:方案数取模、大指数、矩阵快速幂(进阶)。
为什么
a^b 直接乘要 O(b) 次;快速幂利用 a^b = (a^(b/2))^2 把指数每次砍半,O(log b) 搞定。取模是因为计数类答案会爆 long,题目让你全程 % MOD 保持数值可控(Python 虽不溢出但会变超大整数拖慢,取模同样必要)。
解题步骤
res=1,把b看成二进制。- 从低位到高位:当前位是 1 就
res = res*a % mod;每步a = a*a % mod,b >>= 1。 - 循环到
b==0,res即答案。
Python 模板
MOD = 10**9 + 7
# 快速幂:a^b % mod
def qpow(a, b, mod=MOD):
if b < 0:
raise ValueError("exponent must be non-negative")
if mod <= 0:
raise ValueError("mod must be positive")
res = 1 % mod
a %= mod
while b:
if b & 1:
res = res * a % mod
a = a * a % mod
b >>= 1
return res
# 逆元(费马小定理):调用方必须保证 mod 为质数
def inv(a, mod=MOD):
if mod <= 1:
raise ValueError("mod must be greater than 1")
if a % mod == 0:
raise ValueError("a has no modular inverse")
return qpow(a, mod - 2, mod)
# 组合数取模 C(n, k) % mod:调用方须保证 mod 为质数,且要求 0 <= n < mod
def comb_mod(n, k, mod=MOD):
if mod <= 1:
raise ValueError("mod must be greater than 1")
if n < 0:
raise ValueError("n must be non-negative")
if k < 0 or k > n:
return 0
if n >= mod:
raise ValueError("n must be smaller than mod; use Lucas when n >= mod")
fac = [1] * (n + 1)
for i in range(1, n + 1):
fac[i] = fac[i - 1] * i % mod
return fac[n] * inv(fac[k], mod) % mod * inv(fac[n - k], mod) % mod
ACM 模板
import sys
def main():
a, b = map(int, sys.stdin.read().split())
MOD = 10**9 + 7
if b < 0:
raise ValueError("exponent must be non-negative")
res, a = 1 % MOD, a % MOD
while b:
if b & 1: res = res * a % MOD
a = a * a % MOD; b >>= 1
print(res)
main()
复杂度:qpow 是 O(log b);费马逆元是 O(log mod);单次 comb_mod 是 O(n + log mod) 时间、O(n) 空间。
典型题:Pow(x,n)(LeetCode 50)、超级次方、各类「方案数 mod 1e9+7」的计数 DP、组合数取模。
常见坑
- Python 内置
pow(a, b, mod)就是快速幂,笔试可直接用pow(2, 100000, MOD)!但要会手写原理以防被要求。 qpow这里仅接收非负指数和正模数;负指数需要先求逆元,而逆元只在gcd(a, mod)=1时存在。- 质数模数是调用前提,模板不做昂贵的试除判质数;费马逆元还要求
a % mod != 0。阶乘组合数模板要求n < mod;当n >= mod时阶乘含 0,应改用 Lucas 定理(或按题目模数选别的方法)。 - 全程
% mod,别只在最后取一次(中间会爆成大整数拖慢)。
口诀:指数砍半平方乘,取模逆元费马幂。
32. 数论基础(GCD / 质数筛 / 质因数)
识别信号
- 出现「最大公约数、最小公倍数、互质、约数个数」。
- 「判断质数、找 ≤ n 的所有质数、质因数分解」。
- 送分题或中档题里的数学小工具。
为什么 这些是数论的「乐高积木」,笔试里常作为大题的一个子步骤。背熟模板能 30 秒解决,现推容易翻车(尤其筛法的复杂度)。
解题步骤:直接套模板,记住「欧几里得求 gcd」「埃氏筛 O(n log log n)」。
Python 模板
from math import gcd # Python 自带 gcd,直接用
def lcm(a, b):
if a == 0 or b == 0:
return 0
return abs(a // gcd(a, b) * b) # 先除再乘,结果约定非负
# 判质数 O(√n)
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
# 埃氏筛:求 [2, n] 所有质数
def sieve(n):
if n < 2:
return []
is_p = [True] * (n + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_p[i]:
for j in range(i * i, n + 1, i): # 从 i*i 开始
is_p[j] = False
return [i for i in range(2, n + 1) if is_p[i]]
# 质因数分解
def factorize(n):
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n > 1:
factors[n] = factors.get(n, 0) + 1 # 剩下的大质数
return factors
ACM 模板
import sys
def main():
n = int(sys.stdin.readline())
if n < 2:
print()
return
is_p = [True]*(n+1)
is_p[0] = is_p[1] = False
for i in range(2, int(n**0.5)+1):
if is_p[i]:
for j in range(i*i, n+1, i): is_p[j] = False
print(*[i for i in range(2, n+1) if is_p[i]])
main()
复杂度:gcd O(log)、判质数 O(√n)、埃氏筛 O(n log log n)、分解 O(√n)。
常见坑
- 埃氏筛内层从
i*i开始(小于 i*i 的已被更小质数筛过)。 lcm(0, b)=0,且通常约定最小公倍数非负;先除后乘防溢出。- 质因数分解最后
if n>1别忘(剩下的是个大质数)。
口诀:辗转相除求 gcd,埃氏筛法标合数。
33. 区间调度贪心(排序 + 扫描)
识别信号
- 「最多能选多少个互不重叠的区间」「最少用几支箭引爆气球」「会议室能否全排下 / 需要几个会议室」。
- 「按某个维度排序后,贪心地选/合并」。
为什么 区间问题的贪心核心:按右端点排序,每次选「结束最早」的,给后面留最多空间——这样能选的区间最多。这是可证明的经典贪心。
解题步骤(最多不重叠区间)
- 按右端点升序排序。
- 维护上一个选中区间的右端
end。 - 当前区间左端
≥ end就选它,更新end。
Python 模板
# 最多不重叠区间数(等价:最少删除数 = n - 该值)
def max_non_overlap(intervals):
ordered = sorted(intervals, key=lambda x: x[1]) # 不改调用方输入
cnt, end = 0, float('-inf')
for s, e in ordered:
if s >= end: # 不重叠,选它
cnt += 1
end = e
return cnt
# 合并区间(56,按左端点排)
def merge(intervals):
ordered = sorted(intervals, key=lambda x: x[0])
res = []
for s, e in ordered:
if res and s <= res[-1][1]:
res[-1][1] = max(res[-1][1], e) # 有重叠,合并
else:
res.append([s, e])
return res
# 需要多少个会议室(最大重叠数):差分/扫描线思想
def min_meeting_rooms(intervals):
events = []
for s, e in intervals:
events.append((s, 1)) # 开始 +1
events.append((e, -1)) # 结束 -1
events.sort() # 同时刻:结束(-1)排在开始(+1)前
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
ACM 模板
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
intervals = [(int(data[1+2*i]), int(data[2+2*i])) for i in range(n)]
intervals.sort(key=lambda x: x[1])
cnt, end = 0, float('-inf')
for s, e in intervals:
if s >= end: cnt += 1; end = e
print(cnt)
main()
复杂度:排序 O(n log n) + 扫描 O(n)。
典型题:无重叠区间、用最少数量的箭引爆气球、合并区间、会议室 I/II、划分字母区间。
常见坑
- 「最多不重叠」按右端点排;「合并区间」按左端点排——别搞混。
- 边界「相邻算不算重叠」看题意:
[1,2]和[2,3]有时算重叠有时不算,>=还是>要对应。
口诀:不重叠按右端排,合并区间按左端。
34. 单调队列(定长窗口最值)
识别信号
- 「滑动窗口(定长 k)里的最大值/最小值」,要求 O(n)。
- 「窗口内最值」反复出现在 DP 优化里(单调队列优化 DP)。
为什么 定长窗口求最值,朴素每窗 O(k) 共 O(nk)。单调队列(双端队列存下标)维护一个「单调递减」序列:队头永远是当前窗口最大值,新元素把比它小的队尾全弹掉,每个元素进出各一次 → O(n)。
解题步骤(求最大值)
- 队列存下标,对应值单调递减。
- 新元素入队前,把队尾比它小的都弹掉(它们不可能再当最大)。
- 队头下标若滑出窗口(
≤ i-k)就弹掉;窗口成形后队头即答案。
Python 模板
from collections import deque
# 239 滑动窗口最大值
def max_sliding_window(nums, k):
if not 1 <= k <= len(nums):
raise ValueError("k must be in [1, len(nums)]")
dq = deque() # 存下标,nums[下标] 单调递减
res = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # 弹掉队尾更小的
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # 队头滑出窗口
if i >= k - 1:
res.append(nums[dq[0]]) # 窗口成形,队头是最大
return res
ACM 模板
import sys
from collections import deque
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
nums = list(map(int, data[2:2 + n]))
if not 1 <= k <= n:
raise ValueError("k must be in [1, n]")
dq, res = deque(), []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x: dq.pop()
dq.append(i)
if dq[0] <= i - k: dq.popleft()
if i >= k - 1: res.append(nums[dq[0]])
print(*res)
main()
复杂度:时间 O(n),空间 O(k)。
典型题:滑动窗口最大值(239,也在 Hot100)、绝对差不超过限制的最长子数组、跳跃游戏 VI(单调队列优化 DP)。
常见坑
- 先检查
1 <= k <= len(nums);k=0、负数或大于数组长度都没有有效定长窗口。 - 队列存下标不是值(要靠下标判断是否滑出窗口)。
- 求最大值维护递减队列(弹掉更小的);求最小值反过来。
- 判滑出用
dq[0] <= i-k,收集答案用i >= k-1,两个边界别错。
口诀:定长窗口求最值,单调队列存下标。
35. 模拟题套路(读懂规则,稳扎稳打)
识别信号
- 题目是一大段规则/流程描述,没有明显算法名,让你「按题意实现」。
- 华为机试、美团笔试的第 1~2 题常是这种「劝退式长题面」。
- 关键词:游戏规则、日期处理、字符串格式化、状态机、报数、约瑟夫环。
为什么 简单模拟主要考代码组织能力 + 细心;复杂模拟还会考状态设计、事件优先级、同步/异步更新和周期快进。双陆棋、角色移动等题不能只靠“照题意写”硬堆条件。
解题步骤(方法论,不是算法)
- 列出完整状态,以及每轮
validate → transition → resolve → score的阶段顺序。 - 明确冲突规则、并列规则和更新是读旧状态还是边算边改;需要同步更新时先写入新状态。
- 每个阶段写一个不变量断言,状态尽量可序列化,便于判环、快进和复现失败。
- 用样例手动走阶段快照,再写非法动作、并列、循环状态等边界样例。
Python 模板(通用骨架 + 常用小工具)
# 状态机 / 分步模拟的通用骨架
def simulate(steps):
state = init_state()
for step in steps:
state = apply_rule(state, step) # 每条规则一个函数
return format_output(state)
# —— 笔试常用小工具 ——
# 约瑟夫环(n 人围圈,每数到 m 出局,求最后幸存者,0-indexed)
def josephus(n, m):
ans = 0
for i in range(2, n + 1):
ans = (ans + m) % i
return ans # 要 1-indexed 就 +1
# 日期:两个日期相差天数,直接用标准库最稳
from datetime import date
def days_between(y1, m1, d1, y2, m2, d2):
return abs((date(y2, m2, d2) - date(y1, m1, d1)).days)
# 二维方向模拟(上右下左循环,螺旋/机器人行走常用)
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 顺时针
def turn_right(d):
return (d + 1) % 4
ACM 模板(以「按规则处理 n 条指令」为例)
import sys
def main():
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
x = y = 0 # 例:机器人在网格移动
d = 0 # 朝向
DIRS = [(-1,0),(0,1),(1,0),(0,-1)]
for _ in range(n):
cmd = data[idx]; idx += 1
if cmd == 'L': d = (d + 3) % 4
elif cmd == 'R': d = (d + 1) % 4
else: # 'F' 前进
dx, dy = DIRS[d]; x += dx; y += dy
print(x, y)
main()
复杂度:通常就是 O(步数),关键不在复杂度而在正确性。
典型题:约瑟夫环、螺旋矩阵、机器人行走、日期计算、字符串大数加减、报数游戏、简单状态机。
常见坑
- 题意读错是最大杀手——一定用样例验证再提交。
- 大整数加减、进位、前导零这类细节最容易漏。
- 别怕代码长,模拟题拆清楚函数比追求简短重要。
口诀:长题面别慌张,拆规则分函数,样例走一遍。
📎 附录 A:大厂笔试应试策略(临场提分)
- 先扫全部题,按「好拿分」排序做,不一定从第 1 题开始。前面 AC 的分最稳。
- 部分分制:一道 Hard 全 AC 难,但过 30%~60% 测试点(暴力/小数据解)也有分——别放空。
- 数据范围反推算法(务必形成本能):
- n ≤ 20 → 状压/回溯;n ≤ 2000 → O(n²);n ≤ 1e5 → O(n log n);n ≤ 1e6 → O(n)。
- Python 防 TLE 三件套:
sys.stdin.read()快读、攒out列表'\n'.join快写、pow(a,b,mod)用内置。 - 卡题就跳:一题超过 20~25 分钟没思路,先拿下别的,回头再啃。
- 提交前自测:样例 + 空输入 + 单元素 + 最大规模,至少脑跑一遍边界。
📎 附录 B:一周时间,这些「别碰」(性价比低)
若只剩一周且目标是通用技术卷,以下内容可以暂缓;目标算法岗/算法专场时必须按公司证据调整:
- 线段树 / 树状数组进阶:通用卷可先学 Fenwick;目标阿里/算法专场至少掌握单点更新与区间查询,27 届公开回忆已出现线段树建模。
- 数位 DP / 状压 DP:难且冷门,投入产出比低。
- KMP / 后缀数组 / AC 自动机:字符串高级算法,大厂笔试极少;
str.find/ 字符串哈希够用。 - 网络流 / 二分图匹配:通用卷低频,但算法岗已出现最小权完美匹配;目标阿里时至少会识别并掌握 Hungarian O(n³)。
通用卷一周突击仍优先 Hot100 Medium + 28–31 + 计时模拟;算法岗应再按作战手册和组合题决策树选择公司专项。
🎯 超纲篇 8 口诀速记
- 二分答案:最大最小求分界,答案空间上二分。
- 差分数组:区间加变两端点,差分还原前缀和。
- 最短路:带权最短用堆扩,松弛跳过过期值。
- 快速幂:指数砍半平方乘,取模逆元费马幂。
- 数论:辗转相除求 gcd,埃氏筛法标合数。
- 区间贪心:不重叠按右端排,合并区间按左端。
- 单调队列:定长窗口求最值,单调队列存下标。
- 模拟题:长题面别慌张,拆规则分函数,样例走一遍。
原始文档:GitHub 源文件。