主要面向做题复健，偏 Data Structure 与常用算法模板速查。

语法和STL

std

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>

reverse(nums.begin(), nums.end()); // 反转数组
string s = to_string(num);         // 数字转字符串

sort(nums.begin(), nums.end(),
     [捕获列表](参数1, 参数2) { return 比较逻辑; }); // 排序

upper_bound(v.begin(), v.end(), target);
min_element(v.begin(), v.end(),
            [](int a, int b) { return a < b; });
max_element(v.begin(), v.begin() + k,
            [](int a, int b) { return a < b; });

补充：

  • 区间通常写成左闭右开：[begin, end)
  • end - begin 为元素个数
  • 以 nums.size() 为值的下标，指向最后一个元素的下一个位置
  • v.begin(), v.begin() + k 表示前 k 个元素
  • upper_bound(v.begin(), v.end(), target) 的含义是“应插入的位置”
  • 若数组中有 target，其范围为 [lower_bound, upper_bound)
  • 若数组中没有 target，则 up = low，指向第一个比 target 大的位置

struct

1
2
3
4
5
6
7
struct Student {
    string name;
    int age;
    float score;
} a, b; // 定义了两个 Student 类型的变量 a, b

Student c; // 定义了一个 Student 类型的变量 c

string 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
string s;
getline(cin, s); // 输入一行字符串，包括空格
s = "hello";
s += str;       // 字符串拼接

s.length(); // 字符串长度
s.substr(start, length); // 子串
s.find(str, [pos]); // 从第 pos 个字符开始查找子串
s.c_str(); // 返回字符串所在字符数组的起始地址

// 字符操作
isalnum(c); // 判断是否为字母或数字
isupper(c); // 判断是否为大写字母
islower(c); // 判断是否为小写字母
toupper(c); // 将小写字母转换为大写字母

动态数组vector

特点：

  • 尾部 O(1) 插入删除
  • 中间 O(n) 插入删除
  • 支持随机访问，核心是连续内存空间
  • 扩缩容和搬移数据成本较高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> v;
vector<int> nums(n, 2); // 初始化大小为 n，值全为 2

vector<int> v2(10); // 初始化大小为 10
v2[0] = 1;          // 初始化大小后再随机访问
vector<int> v3(10, 1);                  // 大小为 10，值为 1
vector<int> v4(v2);                     // 拷贝 v2
vector<int> v5(v2.begin(), v2.begin() + 3); // 拷贝前三个元素
vector<int> v6(a, a + 3);               // 拷贝数组 a 的前三个元素

// 二维 int 数组
vector<vector<int>> dp;

// 大小为 m * n 的布尔数组，初值全为 true
vector<vector<bool>> dp(m, vector<bool>(n, true));

push_back(value);
pop_back();
insert(pos, value); // pos 为迭代器，如 ans.begin() + 2
erase(pos);

// 遍历
for (int i = 0; i < v.size(); i++)
    cout << v[i] << endl;

//两个迭代器 v.begin() 和 v.end() 
// begin() 指向第一个有效元素
// end() 指向最后一个有效元素的下一个位置

环形数组

适合 O(1) 增删头部元素。

当 start, end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果。

栈队列stack,queue

实际上可以用 vector 代替 stack。

1
2
3
push(1), pop();
stk.top();
queue.front();

双向链表list

特点：

  • O(1) 插入删除
  • 不支持随机访问，只能高效获取头尾元素
  • 增删查改指定索引元素是 O(n)

可选优化：

  • 哈希链表
  • 跳表

跳表相当于在原链表基础上增加多层索引。每向上一层，索引节点数量减少一半，索引间隔变为 2 倍，索引高度是 logN，所以查询时间复杂度是 O(logN)。

1
2
3
4
5
6
7
8
9
10
11
12
13
list<int> l;
front(), back();
push_back(1), pop_back();
push_front(2), pop_front();

auto it = l.begin();

// 删除元素
lst.erase(it);

// 遍历
for (auto it = l.begin(); it != l.end(); it++)
    cout << *it << endl;

哈希表 unordered_map<K,V>

Map 键值对是 Java 的接口。根据底层实现不同：

  • HashMap 基于哈希表，O(1) 增删改查
  • TreeMap 基于红黑树，O(logn) 增删改查
  1. 哈希表O(1)增删改查，因为底层实现就是table数组，只是通过哈希函数把key映射到table数组的索引位置，然后在这个位置上存储value。使用拉链法、开放寻址法解决哈希冲突（冲突时同位置存多个、向下个位置存）。
  2. 哈希表底层就是操作一个数组，其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)，且合理解决哈希冲突的问题，那么增删查改的复杂度就都是 O(1)。
  3. 哈希表中键的遍历顺序是不确定的，不能依赖哈希表的遍历顺序来编写程序。
    • key 在底层 table 数组中的分布是随机的，不像数组/链表结构那样有明确的元素顺序。
    • 哈希表会自动扩缩容，扩容时会重新计算哈希值，导致键值对的顺序发生变化。
  4. C++哈希表中，访问一个不存在的键会自动创建，值为默认。这一点和其他语言不同，需要格外注意。记住访问值之前要先判断键是否存在
1
2
3
4
5
6
7
8
9
10
11
12
// 初始化一个空的哈希表
unordered_map<int, string> hashmap;

// 直接用Key操作
hashmap[4] = "four";
hashmap.erase(4);

// c++20 判断键是否存在
if (hashmap.contains(4)) {
    cout << hashmap[4] << endl;
}

哈希集合 unordered_set

本质上还是哈希表，只存 key，不关心 value，主要用于元素去重和 O(1) 判断是否存在。

用链表加强哈希表LinkedHashMap

有序哈希表底层是“哈希表 + 双向链表”，既有哈希表 O(1) 的增删查改效率，又能像链表一样保持插入顺序。

抽象来看：

  • 哈希表存 <key, Node>
  • 链表存 Node
  • Node 再存 key 和 value

这样就可以从 key 在 O(1) 时间内找到 Node，同时在链表中增删也是 O(1)。

1
private final HashMap<K, Node<K, V>> map = new HashMap<>();

用数组加强哈希表

如果想基于标准哈希表增加一个新的 randomKey() API，并要求在 O(1) 时间返回随机键，可以这样设计：

  • 用数组存储哈希表中的键
  • 用哈希表存储键值对

问题在于 remove() 的时间复杂度可能是 O(n)，因为需要遍历数组找到要删除的键。

解决办法：

  • 哈希表记录每个 Key 在数组中的位置，即 <Key, 数组下标>
  • 数组存 pair<Key, Value>

这样就可以在 O(1) 时间内找到要删除键的位置，然后交换并删除。

1
2
3
4
5
// 存储 key 和 key 在 arr 中的索引
private final HashMap<K, Integer> map = new HashMap<>();

// 真正存储 key-value 的数组
private final ArrayList<Node<K, V>> arr = new ArrayList<>();

二叉树

链式直接表示 val left right

1
2
3
4
5
6
7
8
9
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

邻接表实现

1
2
3
4
unordered_map<int, vector<int>> tree;
tree[1] = {2, 3};
tree[2] = {4};
tree[3] = {5, 6};

对应的树结构可以理解为：

1
2
3
4
5
    1
   / \
  2   3
 /   / \
4   5   6

递归遍历DFS

1
2
3
4
5
6
7
8
9
10
11
12
// 二叉树的遍历框架
// 在前序、中序、后序遍历的位置加代码
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

注：二叉搜索树 BST 的中序遍历结果是有序的。

层序遍历BFS

每次把队头元素拿出来，然后把它的左右子节点加入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);
    // 每轮while循环对应处理一层节点
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // 访问 cur 节点
        std::cout << cur->val << std::endl;
        
        // 把 cur 的左右子节点加入队列
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

如果还想同时维护节点所在层数，可以写成下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;
    // 每轮while循环对应处理一层节点
    while (!q.empty()) {
       
        // 通过 sz = q.size() 固定当前层的节点数量，确保只处理当前层的所有节点。
        int sz = q.size();       
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // 把 cur 的左右子节点加入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

多叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Node {
public:
    int val;
    vector<Node*> children;
};

// 二叉树的遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

// N 叉树的遍历框架
void traverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    for (Node* child : root->children) {
        traverse(child);
    }
    // 后序位置
}

二叉搜索树 BST —— TreeMap / TreeSet

左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。

HashMap 底层把键值对存储在一个 table 数组里，而 TreeMap 底层把键值对存储在一棵二叉搜索树的节点里。

常见能力：

  • 增删改查：O(logn)
  • 最大最小元素：O(logn)
  • 返回全部元素：利用 BST 中序遍历有序
  • rank：O(logn)，返回排名第 k 的元素，但需要额外维护每个节点为根的子树节点个数

注意，BST 的增删改查操作虽然理想情况下是 O(logn)，但在极端情况下会退化成链表，时间复杂度变成 O(n)。因此才会进一步引出 AVL 树和红黑树。

Trie树

主要解决字符串相关问题。相同前缀的字符串不会重复存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 基本的多叉树节点
class TreeNode {
public:
    int val;
    vector<TreeNode*> children;
};

// Trie 树节点实现
template<typename V>
struct TrieNode {
    V val = NULL;
    TrieNode<V>* children[256] = { NULL };  
    // val 存储键对应的值，children 数组存储指向子节点的指针。
    // children 数组的索引本身有意义，代表键中的一个字符。
    // 例如 children[97] 如果非空，说明这里存储了字符 'a'。
};

堆 ——一种能动态排序的数据结构

能动态排序的常用数据结构其实只有两个：

  • 优先级队列，底层一般用二叉堆实现
  • 二叉搜索树

二叉搜索树的用途更广，但优先级队列的 API 和代码实现更简单，所以一般能用优先级队列解决的问题，就没必要再上二叉搜索树。

  • BST：左子树的值都小于当前节点，右子树的值都大于当前节点。
  • 二叉堆：某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。一般用于优先队列和堆排序。

主要操作就两个：sink（下沉）和 swim（上浮），用来维护二叉堆性质。

  • 二叉堆插入：O(logn)
  • 二叉堆删除：O(logn)

堆排序相当于把一个乱序数组都 push 到一个二叉堆里，然后再一个个 pop 出来。不过标准堆排序并不依赖优先级队列，而是直接在数组上原地建堆，所以空间复杂度可以做到 O(1)。

C++ STL 的优先队列默认是最大堆，也就是堆顶为最大元素，可以通过自定义比较函数实现最小堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::priority_queue<TypeName> q;             // 数据类型为 TypeName
std::priority_queue<TypeName, Container> q;  // 使用 Container 作为底层容器
std::priority_queue<TypeName, Container, Compare> q;
// 使用 Container 作为底层容器，使用 Compare 作为比较类型

// 默认使用底层容器 vector
// 比较类型 less<TypeName>（此时为它的 top() 返回为最大值）
// 若希望 top() 返回最小值，可令比较类型为 greater<TypeName>
// 注意：不可跳过 Container 直接传入 Compare

// 从 C++11 开始，如果使用 lambda 函数自定义 Compare
// 则需要将其作为构造函数的参数代入，如：
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) {
  return l.second < r.second;
};
std::priority_queue<std::pair<int, int>, 
                    std::vector<std::pair<int, int>>,
                    decltype(cmp)> 
                                    pq(cmp);

线段树

线段树是二叉树结构的衍生，用于高效解决区间查询和动态修改问题：

  • 区间查询：O(logN)
  • 单点修改：O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13

class SegmentTree {
    // 构造函数，给定一个数组，初始化线段树，时间复杂度 O(N)
    // merge 是一个函数，用于定义 query 方法的行为
    // 通过修改这个函数，可以让 query 函数返回区间的元素和、最大值、最小值等
    public SegmentTree(int[] nums, Function<Integer, Integer> merge) {}
    
    // 查询闭区间 [i, j] 的元素和（也可能是最大最小值，取决于 merge 函数），时间复杂度 O(logN)
    public int query(int i, int j) {}
    
    // 更新 nums[i] = val，时间复杂度 O(logN)
    public void update(int i, int val) {}
}

因为不断把线段二分，所以线段树高度是 O(logN)。

  • query：遍历节点总数是 logN 的常数倍，所以时间复杂度是 O(logN)
  • update：找到叶子节点并更新路径上的值，所以时间复杂度也是 O(logN)

图

图是节点 Vertex 和边 Edge 的集合，可以用邻接矩阵或邻接表表示。

图的存储

1
2
3
4
5
6
7
// 邻接表
// graph[x] 存储 x 的所有邻居节点
vector<vector<int>> graph;

// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
vector<vector<bool>> matrix;

图的遍历

图的遍历就是多叉树遍历的延伸，仍然是 DFS 和 BFS。区别在于图中可能存在环，所以需要标记避免死循环。
遍历图的「节点」和「路径」略有不同:

  • 遍历「节点」时，需要 visited 数组在前序位置标记节点
  • 遍历图的所有「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 多叉树节点
class Node {
public:
    int val;
    std::vector<Node*> children;
};

// 多叉树的遍历框架
void traverse(Node* root) {
    // base case
    if (root == nullptr) {
        return;
    }
    // 前序位置
    std::cout << "visit " << root->val << std::endl;
    for (auto child : root->children) {
        traverse(child);
    }
    // 后序位置
}

// 图节点
class Vertex {
public:
    int id;
    std::vector<Vertex*> neighbors;
};

// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
void traverse(Vertex* s, std::vector<bool>& visited) {
    // base case
    if (s == nullptr) {
        return;
    }
    if (visited[s->id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s->id] = true;
    std::cout << "visit " << s->id << std::endl;
    for (auto neighbor : s->neighbors) {
        traverse(neighbor, visited);
    }
    // 后序位置
}

对于树结构，遍历所有「路径」和遍历所有「节点」差别不大；而对于图结构，这两者是有区别的。

因为对于树结构来说，只能由父节点指向子节点，所以从根节点 root 出发，到任意一个节点 targetNode 的路径都是唯一的。换句话说，遍历一遍树结构的所有节点之后，必然可以找到 root 到 targetNode 的唯一路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 多叉树的遍历框架，寻找从根节点到目标节点的路径
std::list<Node*> path;

void traverse(Node* root, Node* targetNode) {
    // base case
    if (root == nullptr) {
        return;
    }
    if (root->val == targetNode->val) {
        // 找到目标节点
        std::cout << "find path: ";
        for (auto node : path) {
            std::cout << node->val << "->";
        }
        std::cout << targetNode->val << std::endl;
        return;
    }
    // 前序位置
    path.push_back(root);
    for (Node* child : root->children) {
        traverse(child, targetNode);
    }
    // 后序位置
    path.pop_back();
}

而对于图结构来说，由起点 src 到目标节点 dest 的路径可能不止一条。我们需要一个 onPath 数组，在进入节点时（前序位置）标记为正在访问，退出节点时（后序位置）撤销标记，这样才能遍历图中的所有路径，从而找到 src 到 dest 的所有路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 下面的算法代码可以遍历图的所有路径，寻找从 src 到 dest 的所有路径

// onPath 和 path 记录当前递归路径上的节点
vector<bool> onPath(graph.size());
list<int> path;

void traverse(Graph& graph, int src, int dest) {
    // base case
    if (src < 0 || src >= graph.size()) {
        return;
    }
    if (onPath[src]) {
        // 防止死循环（成环）
        return;
    }
    if (src == dest) {
        // 找到目标节点
        cout << "find path: ";
        for (auto it = path.begin(); it != path.end(); it++) {
            cout << *it << "->";
        }
        cout << dest << endl;
        return;
    }

    // 前序位置
    onPath[src] = true;
    path.push_back(src);
    for (const Edge& e : graph.neighbors(src)) {
        traverse(graph, e.to, dest);
    }
    // 后序位置
    path.pop_back();
    onPath[src] = false;
}

遍历所有路径的算法复杂度通常较高。

快速排序、快速选择、sort

1
2
3
4
bool cmp(int a, int b) {
    return a > b; // 从大到小排序
}
sort(nums.begin(), nums.end(), cmp);

算法框架

链表双指针

  • 双指针：合并两个或 k 个有序链表
  • 快慢指针：slow 走一步，fast 走两步，可以判断链表是否有环、找到链表中点、找到倒数第 k 个元素
1
2
3
4
5
6
7
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow) break;
}

技巧：

  • 当需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况处理。
1
ListNode dummy(0), *p = &dummy;
  • 创建新链表时，要正确终结链表。如果是复用原链表节点创建新链表，要把最后一个节点的 next 设为空指针。

反转链表

反转单链表

迭代法：每次修改一个节点，需要维护 pre、cur、next 三个指针。

注意技巧：

  1. 一旦出现类似 nxt.next 这种操作，就要条件反射地先判断 nxt 是否为 null，否则容易出现空指针异常。
  2. 注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。

递归法：递归函数的定义是，输入一个节点 head，将“以 head 为起点”的链表反转，并返回反转之后的头结点。

随后，当前节点会接到“后面链表反转后的尾部”，所以要把这个尾节点的 next 指向当前节点，同时把当前节点的 next 设为空，最后返回头节点。

数组双指针

  • 快慢指针：原地修改元素，fast 指针在前面探查元素
  • 左右指针：如二分。只要数组有序，就应该想到左右指针

滑动窗口

初始化 left = right = 0，把左闭右开区间 [left, right) 称为一个“窗口”。

滑动窗口通过扩大和缩小窗口来解决某些问题，主要用来处理子数组或子串问题，比如寻找符合条件的最长/最短子数组。

注意：

  • 滑动窗口并不能穷举出所有子串
  • 判断哈希表中元素是否存在，应使用 if (map.count(c))，而不是 if (map[c])，因为 map[c] 可能会创建新的键值对

遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：

  1. 什么时候应该扩大窗口？
  2. 什么时候应该缩小窗口？
  3. 什么时候应该更新答案？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 滑动窗口算法伪码框架
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    auto window = ...

    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c);
        // 增大窗口
        right++;

        // 进行窗口内数据的一系列更新
        ...

        // *** debug 输出的位置 ***
        printf("window: [%d, %d)\n", left, right);
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d);
            // 缩小窗口
            left++;

            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

二叉树与递归

递归算法常见思考顺序：

  1. 首先，这个问题是否可以抽象成一棵树结构？如果可以，那么就要用递归算法了。
  2. 如果要用递归算法，那么就思考「遍历」和「分解问题」这两种思维模式，看看哪种更适合这个问题。
  3. 如果用「分解问题」的思维模式，那么一定要写清楚这个递归函数的定义是什么，然后利用这个定义来分解问题，利用子问题的答案推导原问题的答案；
  4. 如果用「遍历」的思维模式，那么要用一个无返回值的递归函数，单纯起到遍历递归树，收集目标结果的作用。

其实，“分解问题”的思维模式就对应着后面的动态规划和分治算法，而“遍历”的思维模式则更接近 DFS / 回溯算法。

algorithm

sort

用于数组、vector 等具有随机访问特性的容器。

  • 默认以 less<T> 作为比较函数，即从小到大排序
  • cmp 比较函数的规则是：当返回 true 时，表示 a 排在 b 前面
  • 可以重载 < 运算符，也可以重载 () 运算符
1
2
3
4
bool cmp(node a, node b)
{
    return a.length > b.length; // a 比 b 长时，a 排在 b 前面
}

next_permutation

1
2
next_permutation(start, end); // 在 [start, end) 区间内求下一个排列
next_permutation(a, a + n);   // 求 a 数组的下一个排列，长度为 n