术语表 · 187 条 · 中英对照
英文面试时，这些词怎么说。
差分、状压、换根、单调栈的英文怎么说？187 个算法与数据结构术语的中英对照，每条配一句英文面试例句，可以朗读，也能一键做成复习卡。
想把各站模板打印出来，用 打印版模板手册。
共 187 条
基础与复杂度 32
- 时间复杂度time complexity
The time complexity is O(n log n), and the sort is the slowest step.
- 空间复杂度space complexity
The hash map makes the space complexity O(n); with two pointers I could bring it down to O(1).
- 大 O 表示法Big O notation
- 又称：big-O
Big O notation drops constants, so two n plus five is still O(n).
- 均摊复杂度amortized time
- 又称：amortized complexity · amortized O(1)
Appending to a dynamic array is amortized O(1), even though an occasional resize costs O(n).
- 暴力解法brute force
- 又称：naive approach
Let me start with a brute force solution that checks every pair, and then optimize it.
- 边界情况edge case
- 又称：corner case
One edge case is an empty array, so I return zero right away.
- 差一错误off-by-one error
Let me double-check the loop bound so I don't make an off-by-one error.
- 整数溢出integer overflow
The sum can pass two billion, so I use a 64-bit integer to avoid integer overflow.
- 数据范围constraints
- 又称：input size
The constraints say n can be a hundred thousand, so an O(n squared) solution would time out.
- 超时Time Limit Exceeded
- 又称：TLE
My first version got TLE on the large tests, so I replaced the nested loop with a hash set.
- 答案错误Wrong Answer
- 又称：WA
It passes the samples but gets Wrong Answer, which points to an edge case I missed.
- 超内存Memory Limit Exceeded
- 又称：MLE
The full table hit Memory Limit Exceeded, so I compressed it to a single row.
- 模板：网格动规
- 运行错误runtime error
The runtime error came from reading one index past the end of the array.
- 测试用例test case
Let me walk through a small test case to make sure the logic holds.
- 手动模拟（走一遍样例）dry run
- 又称：walk through · trace
Before running it, let me do a dry run with the input one, three, two.
- 伪代码pseudocode
I'll sketch the pseudocode first and then turn it into real code.
- 递归recursion
- 又称：recursive
Recursion fits here because each subtree is the same problem, only smaller.
- 模板：树的遍历
- 调用栈call stack
- 又称：stack overflow
If the tree is one long chain, the call stack could get too deep, so I'll write it iteratively.
- 迭代写法iterative approach
- 又称：iteratively
An iterative approach with an explicit stack avoids deep recursion.
- 循环不变量loop invariant
- 又称：invariant
The loop invariant is that everything left of lo is false and everything from hi on is true.
- 模板：二分查找
- 权衡（取舍）trade-off
- 又称：tradeoff
The trade-off is extra memory for the hash map in exchange for linear time.
- 分治divide and conquer
Merge sort is divide and conquer: split the array, sort each half, then merge them.
- 模拟simulation
- 又称：simulate
There's no trick here; it's a simulation, so I'll follow the rules step by step.
- 预处理preprocessing
- 又称：precompute
With some preprocessing I can precompute prefix sums and answer each query in O(1).
- 稳定排序stable sort
I need a stable sort so that equal keys keep their original order.
- 自定义比较器comparator
- 又称：custom comparator · sort key
I'll pass a custom comparator that sorts by end time, then by start time.
- 计数排序counting sort
The values are between zero and one hundred, so counting sort runs in linear time.
- 升序 / 降序ascending order
- 又称：descending order · non-decreasing
I sort the array in ascending order and scan it from the left.
- 字典序lexicographic order
- 又称：lexicographical order · lexicographically smallest
They want the lexicographically smallest answer, so at each step I pick the smallest valid character.
- 离线查询offline queries
- 又称：offline algorithm
All the queries are known up front, so I can sort them and answer them as offline queries.
- 哨兵sentinel value
- 又称：sentinel
I append a sentinel value of infinity so the last group is closed inside the loop.
数组与字符串 24
- 读写指针（快慢下标）read and write pointers
With read and write pointers, everything to the left of the write pointer is already final.
- 模板：原地数组
- 原地修改in-place
- 又称：in place
I'll do it in place by overwriting the array, so the extra space is O(1).
- 模板：原地数组
- 荷兰国旗问题（三路划分）Dutch national flag
- 又称：three-way partition
This is the Dutch national flag problem: one pass with three pointers sorts the zeros, ones and twos.
- 模板：原地数组
- 滑动窗口sliding window
I keep a sliding window and shrink it from the left whenever it contains a repeated character.
- 模板：双指针滑窗
- 定长滑窗fixed-size window
For a fixed-size window of k, I add the new element and drop the one that falls out.
- 模板：双指针滑窗
- 前缀和prefix sum
- 又称：cumulative sum · running sum
With a prefix sum array, any range sum is the difference of two entries.
- 模板：前缀和区间
- 差分difference array
For many range updates, a difference array adds v at l and subtracts v at r plus one; one prefix sum then rebuilds the values.
- 模板：前缀和区间
- 二维前缀和2D prefix sum
- 又称：summed-area table
A 2D prefix sum gives any rectangle's sum in O(1) with inclusion-exclusion.
- 模板：前缀和区间
- 区间合并merge intervals
- 又称：overlapping intervals
To merge intervals, I sort them by start and extend the last one while the next one starts no later than it ends.
- 模板：前缀和区间
- 扫描线sweep line
- 又称：line sweep
A sweep line over the sorted start and end events tells me how many meetings overlap at once.
- 模板：前缀和区间
- 子序列subsequence
A subsequence keeps the relative order, but its elements don't have to be next to each other.
- 模板：子序列
- 字母异位词anagram
Two words are anagrams when their letter counts match, so I compare the count arrays.
- 模板：哈希计数
- 频次统计frequency map
- 又称：frequency count · counter
I build a frequency map of the characters in one pass.
- 模板：哈希计数
- KMP 算法KMP algorithm
- 又称：Knuth-Morris-Pratt · prefix function
KMP never moves the text pointer back; on a mismatch it falls back using the prefix function.
- 模板：字符串
- 字符串哈希（滚动哈希）rolling hash
- 又称：Rabin-Karp · string hashing
A rolling hash lets me compare two substrings in O(1) after linear preprocessing.
- 模板：字符串
- 字符串拼接string builder
- 又称：immutable string
Strings are immutable in Java, so I use a string builder instead of concatenating in a loop.
- 模板：字符串
- 数组越界out of bounds
- 又称：index out of range
I check that r plus one is less than n first, so the access never goes out of bounds.
- 螺旋遍历spiral order
I peel the matrix layer by layer to read it in spiral order.
- 快速选择quickselect
Quickselect finds the k-th largest element in average O(n) time without sorting everything.
- 模板：单调栈与堆
- 离散化coordinate compression
- 又称：discretization
The values go up to a billion, so I use coordinate compression to map them to their ranks.
数据结构 28
- 哈希表hash map
- 又称：hash table · dictionary
A hash map from value to index gives me O(1) average lookups.
- 模板：哈希计数
- 栈stack
- 又称：last in, first out · LIFO
A stack fits here because the most recent open bracket has to close first.
- 模板：单调栈与堆
- 队列queue
- 又称：first in, first out · FIFO
BFS uses a queue, so nodes are processed in the order they were found.
- 模板：树的遍历
- 双端队列deque
- 又称：double-ended queue
A deque, pronounced like deck, lets me push and pop at both ends in O(1).
- 模板：单调栈与堆
- 单调栈monotonic stack
A monotonic stack finds the next greater element for every index in one pass.
- 模板：单调栈与堆
- 单调队列monotonic queue
- 又称：monotonic deque
A monotonic queue gives the maximum of every window in O(n) total.
- 模板：单调栈与堆
- 堆（优先队列）heap
- 又称：priority queue · min-heap · max-heap
I keep a min-heap of size k, so its top is always the k-th largest so far.
- 模板：单调栈与堆
- 懒删除lazy deletion
Instead of decrease-key, I use lazy deletion: push the new distance and skip stale entries when they pop.
- 模板：最短路
- 虚拟头节点（哑节点）dummy node
- 又称：dummy head · sentinel node
A dummy node before the head means removing the head is not a special case.
- 模板：链表
- 快慢指针fast and slow pointers
- 又称：tortoise and hare · Floyd's cycle detection
With fast and slow pointers, the fast one takes two steps at a time, so they meet if there's a cycle.
- 模板：链表
- 双向链表doubly linked list
The cache pairs a hash map with a doubly linked list, so moving a node to the front is O(1).
- 模板：缓存索引
- LRU 缓存LRU cache
- 又称：least recently used
When it's full, an LRU cache evicts the least recently used key.
- 模板：缓存索引
- 字典树（前缀树）trie
- 又称：prefix tree
A trie, usually pronounced like try, stores words by prefix, so a lookup costs only the word's length.
- 模板：字典树序列化
- 序列化serialization
- 又称：serialize · deserialize
For serialization, I write the tree in preorder with a marker for each null child.
- 模板：字典树序列化
- 迭代器iterator
- 又称：lazy iterator
The iterator does its work in hasNext, so next only returns the value it found.
- 模板：迭代器设计
- 并查集union-find
- 又称：disjoint set union · DSU · disjoint-set
With union-find, I join the two ends of each edge, and an edge whose ends are already connected closes a cycle.
- 模板：并查集
- 路径压缩path compression
Path compression flattens the tree during find, so later finds are almost constant time.
- 模板：并查集
- 按秩合并（按大小合并）union by size
- 又称：union by rank
Union by size hangs the smaller tree under the larger one, which keeps the trees shallow.
- 模板：并查集
- 线段树segment tree
A segment tree supports range sum queries and point updates in O(log n).
- 懒标记（延迟传播）lazy propagation
- 又称：lazy tag
With lazy propagation, a range update stops at fully covered nodes and pushes the change down later.
- 树状数组Fenwick tree
- 又称：binary indexed tree · BIT
A Fenwick tree, also called a binary indexed tree, handles prefix sums with updates in O(log n).
- ST 表（稀疏表）sparse table
A sparse table answers range minimum queries in O(1) after O(n log n) preprocessing.
- 有序集合ordered set
- 又称：TreeMap · sorted container · balanced BST
In Java I'd use a TreeMap to find the floor and ceiling keys in O(log n).
- 模板：二叉搜索树
- 动态数组dynamic array
- 又称：ArrayList · vector
A dynamic array doubles its capacity when it fills up.
- 环形数组（循环队列）circular buffer
- 又称：ring buffer
A circular buffer reuses a fixed array and wraps the index around with modulo.
树与图 36
- 树的高度（深度）height
- 又称：depth · max depth
The height of a node is one plus the larger height of its two children.
- 模板：树的遍历
- 平衡二叉树balanced binary tree
- 又称：height-balanced
A balanced binary tree keeps its height at O(log n), so searches stay fast.
- 模板：二叉搜索树
- 二叉搜索树binary search tree
- 又称：BST
In a binary search tree, every value in the left subtree is smaller than the node.
- 模板：二叉搜索树
- 前序遍历preorder traversal
- 又称：pre-order
In a preorder traversal the root comes first, so the first value is the root.
- 模板：树的构造
- 中序遍历inorder traversal
- 又称：in-order
I'll do an iterative inorder traversal with a stack and stop at the k-th node.
- 模板：二叉搜索树
- 后序遍历postorder traversal
- 又称：post-order
A postorder traversal fits, because each node needs its children's results first.
- 模板：树上路径
- 层序遍历level-order traversal
- 又称：level order
For a level-order traversal, I record the queue size at the start of each level.
- 模板：树的遍历
- 最近公共祖先lowest common ancestor
- 又称：LCA
The lowest common ancestor is the deepest node that has both p and q in its subtree.
- 模板：树上路径
- 树的直径diameter of a tree
- 又称：tree diameter
The diameter of a tree is its longest path between two nodes, and it doesn't have to pass through the root.
- 模板：树上路径
- 顶点和边vertices and edges
- 又称：vertex · edge
With V vertices and E edges, BFS runs in O(V plus E).
- 有向图 / 无向图directed graph
- 又称：undirected graph
The prerequisites form a directed graph, with an edge from each course to the courses it unlocks.
- 模板：拓扑排序
- 带权图weighted graph
- 又称：edge weight
In a weighted graph, the path with the fewest edges isn't always the cheapest.
- 模板：最短路
- 邻接表adjacency list
- 又称：adjacency matrix
The graph is sparse, so I'll build an adjacency list.
- 入度 / 出度in-degree
- 又称：out-degree · indegree
A node with an in-degree of zero has no prerequisites left, so it goes into the queue.
- 模板：拓扑排序
- 广度优先搜索（广搜）breadth-first search
- 又称：BFS
Breadth-first search finds the shortest path when every edge has the same cost.
- 模板：网格搜索
- 深度优先搜索（深搜）depth-first search
- 又称：DFS
I run a depth-first search from each unvisited land cell to count the islands.
- 模板：网格搜索
- 多源 BFSmulti-source BFS
With multi-source BFS, every starting cell goes into the queue at time zero.
- 模板：网格搜索
- 双向 BFSbidirectional BFS
Bidirectional BFS searches from both ends and stops when the two frontiers meet.
- 模板：网格搜索
- 访问标记visited set
- 又称：mark as visited
I add a cell to the visited set when it's enqueued, so it never enters the queue twice.
- 模板：网格搜索
- 洪水填充（泛洪）flood fill
Flood fill spreads from the start cell to every connected cell of the same color.
- 模板：网格搜索
- 连通分量（连通块）connected component
- 又称：connected components
Each DFS from an unvisited node covers exactly one connected component.
- 模板：并查集
- 判环cycle detection
- 又称：detect a cycle
For cycle detection in a directed graph, a DFS that reaches a node still on the current path has found a cycle.
- 模板：拓扑排序
- 拓扑排序topological sort
- 又称：topological order · Kahn's algorithm
A topological sort exists only when the graph has no cycle, which is the whole course schedule check.
- 模板：拓扑排序
- 二分图bipartite graph
- 又称：two-coloring
A bipartite graph can be two-colored so that no edge joins two nodes of the same color.
- 最短路shortest path
With equal edge costs BFS gives the shortest path; with non-negative weights I need Dijkstra.
- 模板：最短路
- Dijkstra 算法Dijkstra's algorithm
- 又称：Dijkstra
Dijkstra's algorithm, said DIKE-struh, only works when every edge weight is non-negative.
- 模板：最短路
- Bellman-Ford 算法Bellman-Ford
- 又称：negative cycle
Bellman-Ford handles negative edge weights and can detect a negative cycle.
- 模板：最短路
- Floyd 算法（多源最短路）Floyd-Warshall
- 又称：all-pairs shortest paths
Floyd-Warshall computes all-pairs shortest paths in O(n cubed), which is fine for a hundred nodes.
- 模板：最短路
- 0-1 BFS（双端队列广搜）0-1 BFS
- 又称：deque BFS
With weights of only zero and one, 0-1 BFS pushes a node reached by a zero-weight edge to the front of a deque.
- 模板：最短路
- 最小生成树minimum spanning tree
- 又称：MST
A minimum spanning tree connects all n nodes with n minus one edges of the least total weight.
- 模板：生成树
- Kruskal 算法Kruskal's algorithm
Kruskal's algorithm sorts the edges by weight and keeps each one that joins two components.
- 模板：生成树
- Prim 算法Prim's algorithm
On a dense graph, Prim's algorithm with a plain array runs in O(n squared).
- 模板：生成树
动态规划 27
- 动态规划dynamic programming
- 又称：DP
Dynamic programming works here because the subproblems overlap and the best answer builds on smaller ones.
- 模板：动规入门
- 状态定义state definition
- 又称：DP state
My state definition is: dp of i is the best total using the first i houses.
- 模板：动规入门
- 状态转移方程state transition
- 又称：recurrence · transition
The state transition takes the better of skipping house i or robbing it on top of dp of i minus two.
- 模板：动规入门
- 重叠子问题overlapping subproblems
Plain recursion solves the same calls again and again; these overlapping subproblems are why caching helps.
- 模板：动规入门
- 最优子结构optimal substructure
The problem has optimal substructure: the best path to a cell extends the best path to one of its neighbors.
- 模板：网格动规
- 记忆化搜索memoization
- 又称：memoize · top-down
Memoization, from the word memo, caches each recursive call by its arguments.
- 模板：动规入门
- 递推（自底向上）bottom-up tabulation
- 又称：bottom-up · tabulation
Bottom-up tabulation fills the table from the smallest subproblems, so there's no recursion at all.
- 模板：动规入门
- 滚动数组rolling array
- 又称：rolling variables · space optimization
Each row only needs the one above it, so a rolling array cuts the space to O(n).
- 模板：网格动规
- 方案数number of ways
- 又称：count the ways
The number of ways can be huge, so I return it modulo ten to the ninth plus seven.
- 模板：动规入门
- 网格 DPgrid DP
In this grid DP, each cell depends only on the cell above it and the cell to its left.
- 模板：网格动规
- 0-1 背包0/1 knapsack
- 又称：zero-one knapsack
In the 0/1 knapsack I loop the capacity downward, so each item is used at most once.
- 模板：背包计数
- 完全背包unbounded knapsack
Coin change is an unbounded knapsack, since each coin can be used any number of times.
- 模板：背包计数
- 伪多项式时间pseudo-polynomial time
The knapsack DP runs in pseudo-polynomial time: it depends on the capacity's value, not on its number of digits.
- 模板：背包计数
- 最长递增子序列longest increasing subsequence
- 又称：LIS
The longest increasing subsequence takes O(n log n) with a tails array and binary search.
- 模板：子序列
- 最长公共子序列longest common subsequence
- 又称：LCS
For the longest common subsequence, matching last characters add one to the diagonal cell.
- 模板：字符串动规
- 编辑距离edit distance
- 又称：Levenshtein distance
Edit distance takes the cheapest of insert, delete and replace at each cell.
- 模板：字符串动规
- 区间 DPinterval DP
- 又称：range DP
Interval DP needs the shorter ranges first, so I loop the left end backwards.
- 模板：回文区间
- Kadane 算法（最大子数组和）Kadane's algorithm
- 又称：maximum subarray
Kadane's algorithm either extends the current run or restarts at the current element.
- 模板：状态机
- 状态机 DPstate machine DP
With state machine DP, each day has a holding state and a not-holding state.
- 模板：状态机
- 带权区间调度weighted interval scheduling
Weighted interval scheduling sorts the jobs by end time and binary searches for the last compatible one.
- 模板：分段调度
- 树形 DPtree DP
In tree DP, each node returns two values: the best with it taken and the best without it.
- 模板：树形博弈
- 换根 DPrerooting
- 又称：rerooting DP · re-rooting
With rerooting, I solve for one root, then move the root to each neighbor and update the answer in O(1).
- 模板：树形博弈
- 博弈 DPgame DP
- 又称：minimax · score difference
In this game DP, each range stores the best score difference the player to move can force.
- 模板：树形博弈
- 状压 DP（状态压缩）bitmask DP
- 又称：DP over subsets
With at most sixteen tasks, bitmask DP keeps the set of finished tasks in one integer.
- 模板：位运算
- 数位 DPdigit DP
Digit DP counts the numbers up to n by walking its digits with a flag for whether we're still tight.
搜索、回溯与贪心 20
- 二分答案binary search on the answer
- 又称：binary search the answer
I'll binary search on the answer: guess a speed, then check in O(n) whether it's fast enough.
- 模板：二分查找
- 单调性monotonicity
- 又称：monotonic
The check is monotonic: if one capacity works, every larger capacity works too.
- 模板：二分查找
- 左闭右开区间half-open interval
- 又称：inclusive · exclusive
I use a half-open interval, inclusive at lo and exclusive at hi, so the loop runs while lo is less than hi.
- 模板：二分查找
- 第一个大于等于 x 的位置lower bound
- 又称：bisect_left
Lower bound returns the first index whose value is at least the target.
- 模板：二分查找
- 回溯backtracking
Backtracking builds the answer one choice at a time and undoes each choice after the recursive call.
- 模板：回溯枚举
- 递归树（决策树）recursion tree
- 又称：decision tree
Drawing the recursion tree shows that each level picks one more element.
- 模板：回溯枚举
- 排列permutation
- 又称：permutations
There are n factorial permutations, so this only works for small n.
- 模板：回溯枚举
- 组合combination
- 又称：combinations
For combinations, the next level starts from i plus one, so no set is counted twice.
- 模板：回溯枚举
- 子集subset
- 又称：power set
Each element is either in the subset or not, which gives two to the n subsets.
- 模板：回溯枚举
- 同层去重skip duplicates
- 又称：deduplicate
After sorting, I skip duplicates on the same level when a value equals the one just before it.
- 模板：回溯枚举
- 切分（分割回溯）partitioning
- 又称：cut points
For palindrome partitioning, each level of the search decides where the next piece ends.
- 模板：拆分构造
- 剪枝pruning
- 又称：prune
With the candidates sorted, I can prune the rest of the loop once the sum passes the target.
- 模板：剪枝搜索
- 折半搜索meet in the middle
With forty items, meet in the middle splits them into two halves of twenty and combines the two lists of sums.
- 贪心greedy
- 又称：greedy algorithm · greedy choice
A greedy choice works here: always take the meeting that ends first.
- 模板：贪心调度
- 交换论证exchange argument
An exchange argument proves it: swapping an optimal answer's first pick for the earliest-ending interval never makes it worse.
- 模板：贪心调度
- 区间调度interval scheduling
- 又称：non-overlapping intervals
Interval scheduling sorts by end time and keeps each interval that starts after the last kept one ends.
- 模板：贪心调度
数学与位运算 20
- 位运算bit manipulation
- 又称：bitwise operations
With bit manipulation I can test the k-th bit using a shift and an AND.
- 模板：位运算
- 异或XOR
- 又称：exclusive or
Since a XOR a is zero, XOR-ing every number leaves the one that appears once.
- 模板：位运算
- 最低位的 1（lowbit）lowest set bit
- 又称：x & -x
x AND negative x isolates the lowest set bit, which is how a Fenwick tree jumps.
- 模板：位运算
- 左移 / 右移bit shift
- 又称：left shift · right shift
A left shift by one doubles the number, as long as it doesn't overflow.
- 模板：位运算
- 二进制中 1 的个数popcount
- 又称：Hamming weight · set bits · bit count
Popcount, the number of set bits, is a single built-in call in most languages.
- 模板：位运算
- 快速幂fast exponentiation
- 又称：binary exponentiation · fast power
Fast exponentiation squares the base every round, so it needs only O(log n) multiplications.
- 模板：位运算
- 取模modulo
- 又称：mod · modular arithmetic
I take the result modulo ten to the ninth plus seven after every addition.
- 乘法逆元modular inverse
- 又称：Fermat's little theorem
The modulus is prime, so the modular inverse of a is a to the power of the modulus minus two.
- 最大公约数greatest common divisor
- 又称：GCD · Euclidean algorithm
The Euclidean algorithm finds the GCD in a logarithmic number of steps.
- 最小公倍数least common multiple
- 又称：LCM
The least common multiple is a divided by the GCD, times b; dividing first avoids overflow.
- 埃氏筛（素数筛）sieve of Eratosthenes
- 又称：prime sieve
The sieve of Eratosthenes crosses out the multiples of each prime and finds every prime up to n in O(n log log n).
- 质因数分解prime factorization
Trial division up to the square root of n gives the prime factorization.
- 组合数binomial coefficient
- 又称：n choose k · combinatorics
The binomial coefficient n choose k counts the ways to pick k items out of n.
- 鸽巢原理（抽屉原理）pigeonhole principle
By the pigeonhole principle, n plus one numbers from one to n must contain a duplicate.
- 容斥原理inclusion-exclusion
- 又称：inclusion-exclusion principle
By inclusion-exclusion, the numbers divisible by two or three are the two counts minus the numbers divisible by six.
- 奇偶性parity
- 又称：odd and even
Every move changes the sum by an even number, so its parity never changes and an odd target can't be reached from an even start.
- 向上取整除法ceiling division
- 又称：round up
For ceiling division with integers, I compute a plus b minus one, divided by b.
- 蓄水池抽样reservoir sampling
Reservoir sampling keeps the i-th item with probability one over i, so every item is equally likely to be chosen.