1
#include <vector>
2
using namespace std;
3

4
// 这个函数会返回一个前缀和数组，之后用这个数组可以快速算出任何区间的和
5
vector<int> buildPrefixSum(const vector<int>& arr) {
6
    // 先拿到原数组有多少个数字
7
    int n = arr.size();
8
    // 新建一个数组，长度比原数组多 1，所有元素初始为 0
9
    // 我们把这个数组叫 prefix（前缀和数组）
10
    vector<int> prefix(n + 1, 0);
11

12
    // 开始循环，i 从 0 走到 n-1，代表原数组的每一个位置
13
    for (int i = 0; i < n; i++) {
14
        // prefix[i+1] 要存储“原数组从开头到第 i 个数字的和”
15
        // 这个和等于“前 i 个数字的和”加上“第 i 个数字”
16
        // 前 i 个数字的和正好就是 prefix[i]
17
        // 第 i 个数字就是 arr[i]
18
        // 所以公式就是 prefix[i+1] = prefix[i] + arr[i]
19
        prefix[i + 1] = prefix[i] + arr[i];
20
    }
21
    // 循环结束后，prefix 数组就准备好了，把它返回给调用者
22
    return prefix;
23
}
24

25
// 这个函数用前缀和数组快速求出原数组中从 l 到 r 的区间和
26
int rangeSum(const vector<int>& prefix, int l, int r) {
27
    // 根据数学推导：arr[l] + ... + arr[r] = prefix[r+1] - prefix[l]
28
    // 因为 prefix[r+1] 包含了从 0 到 r 的所有数字和
29
    // 减去 prefix[l]（包含从 0 到 l-1 的所有数字和）
30
    // 剩下的就是从 l 到 r 的和
31
    return prefix[r + 1] - prefix[l];
32
}

1
vector<int> arr = {3, 1, 4, 1, 5};          // 原数组
2
vector<int> pre = buildPrefixSum(arr);       // 调用函数，得到前缀和数组
3
cout << rangeSum(pre, 1, 3) << endl;         // 输出 1+4+1 = 6

1
vector<int> buildSuffixSum(const vector<int>& arr) {
2
    int n = arr.size();
3
    // 后缀和数组长度也是 n+1，最后一个位置 suffix[n] 设为 0
4
    vector<int> suffix(n + 1, 0);
5
    // 从最后一个元素开始往前推
6
    for (int i = n - 1; i >= 0; i--) {
7
        // suffix[i] = 当前元素 arr[i] + 它后面所有元素的和（即 suffix[i+1]）
8
        suffix[i] = suffix[i + 1] + arr[i];
9
    }
10
    return suffix;
11
}
12
// 查询从下标 l 到末尾的和
13
int suffixSum(const vector<int>& suffix, int l) {
14
    return suffix[l];
15
}

1
// 在数组 arr 的闭区间 [l, r] 中查找 x，返回下标，找不到返回 -1
2
int binarySearch(const vector<int>& arr, int x, int l, int r) {
3
    // 只要左指针没有超过右指针，就说明还有元素没检查
4
    while (l <= r) {
5
        // 计算中间位置的下标。用 l + (r-l)/2 可以避免 (l+r) 可能太大而溢出
6
        int mid = l + (r - l) / 2;
7

8
        // 情况1：中间的元素正好等于我们要找的 x
9
        if (arr[mid] == x) {
10
            return mid;   // 找到了，直接返回下标
11
        }
12
        // 情况2：中间的元素比 x 小，说明 x 一定在右半部分
13
        else if (arr[mid] < x) {
14
            l = mid + 1;   // 把左边界移到 mid 的右边，继续在右半部分找
15
        }
16
        // 情况3：中间的元素比 x 大，说明 x 一定在左半部分
17
        else {
18
            r = mid - 1;   // 把右边界移到 mid 的左边，继续在左半部分找
19
        }
20
    }
21
    // 循环结束还没找到，说明 x 不在数组中
22
    return -1;
23
}

1
int lowerBound(const vector<int>& arr, int x) {
2
    int l = 0, r = arr.size();          // 区间是 [l, r)，一开始包含所有元素
3
    while (l < r) {
4
        int mid = l + (r - l) / 2;
5
        // 如果中间元素 >= x，那么第一个 >= x 的位置不可能在 mid 右边
6
        // 它可能是 mid 本身，也可能在左边，所以把右边界缩小到 mid
7
        if (arr[mid] >= x) {
8
            r = mid;
9
        } else {
10
            // 中间元素 < x，那么第一个 >= x 的位置一定在 mid 右边
11
            l = mid + 1;
12
        }
13
    }
14
    // 循环结束时 l 和 r 相等，就是我们要的位置
15
    return l;
16
}

1
int upperBound(const vector<int>& arr, int x) {
2
    int l = 0, r = arr.size();
3
    while (l < r) {
4
        int mid = l + (r - l) / 2;
5
        // 如果中间元素 > x，那么第一个 > x 的位置可能在 mid 或左边
6
        if (arr[mid] > x) {
7
            r = mid;
8
        } else {
9
            // 中间元素 <= x，那么第一个 > x 的位置一定在 mid 右边
10
            l = mid + 1;
11
        }
12
    }
13
    return l;
14
}

1
#include <iostream>
2
#include <string>
3
using namespace std;
4

5
// 定义一个结构体，名字叫 Student
6
struct Student {
7
    // 下面是成员变量，它们会出现在每个 Student 对象中
8
    string name;      // 学生的名字，是一个字符串
9
    int age;          // 学生的年龄，是一个整数
10
    double score;     // 学生的成绩，是一个小数（浮点数）
11

12
    // 这是构造函数，专门用来创建 Student 对象的
13
    // 它接收三个参数：n, a, s，分别对应名字、年龄、成绩
14
    // 后面的 : name(n), age(a), score(s) 叫做初始化列表
15
    // 意思是把参数 n 赋值给 name，a 赋值给 age，s 赋值给 score
16
    Student(string n, int a, double s) : name(n), age(a), score(s) {}
17

18
    // 这是一个成员函数，用来显示学生的信息
19
    // 末尾的 const 表示这个函数不会修改任何成员变量
20
    // 这样即使一个对象是 const 的，也可以调用这个函数
21
    void display() const {
22
        // 输出学生信息，用空格隔开
23
        cout << name << " " << age << " " << score << endl;
24
    }
25
};

1
int main() {
2
    // 创建一个 Student 对象，名字叫 stu1，调用构造函数给它赋值
3
    Student stu1("张三", 20, 95.5);
4
    // 调用 stu1 的 display 函数，它会输出 "张三 20 95.5"
5
    stu1.display();
6

7
    // 结构体的成员默认是公开的，所以可以直接修改
8
    // 把 stu1 的成绩改成 98.0
9
    stu1.score = 98.0;
10
    // 再次显示，现在成绩变了
11
    stu1.display();
12

13
    // 也可以直接用花括号创建对象，这是 C++11 的列表初始化
14
    Student stu2 = {"李四", 22, 88.0};
15
    stu2.display();
16

17
    return 0;
18
}

1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int n = 3;  // 假设集合包含数字 {0, 1, 2}
6
    // 总共有 2 的 n 次方个子集，这里 n=3，所以 2³=8 个子集
7
    // mask 从 0 到 7（二进制 000 到 111）
8
    for (int mask = 0; mask < (1 << n); mask++) {
9
        cout << "{ ";
10
        // 检查 mask 的每一位，i 从 0 到 n-1
11
        for (int i = 0; i < n; i++) {
12
            // 如果 mask 的第 i 位是 1，说明这个子集包含元素 i
13
            // mask >> i 把 mask 右移 i 位，然后 & 1 取出最低位
14
            if ((mask >> i) & 1) {
15
                cout << i << " ";   // 输出这个元素
16
            }
17
        }
18
        cout << "}\n";
19
    }
20
    return 0;
21
}

1
int fib(int n) {
2
    if (n <= 1) return n;
3
    return fib(n-1) + fib(n-2);
4
}

1
int fib(int n) {
2
    // 如果 n 是 0 或 1，直接返回 n 本身
3
    if (n <= 1) return n;
4

5
    // 创建一个数组 dp，大小是 n+1，用来存放每个位置的斐波那契数
6
    vector<int> dp(n + 1);
7

8
    // 初始条件：第 0 个斐波那契数是 0，第 1 个是 1
9
    dp[0] = 0;
10
    dp[1] = 1;
11

12
    // 从 i=2 开始，一直计算到 i=n
13
    for (int i = 2; i <= n; i++) {
14
        // 斐波那契数的定义：当前数等于前两个数之和
15
        dp[i] = dp[i-1] + dp[i-2];
16
    }
17

18
    // 最后 dp[n] 就是我们要的答案
19
    return dp[n];
20
}

1
int knapsack(int W, const vector<int>& wt, const vector<int>& val) {
2
    int n = wt.size();  // 一共有多少个物品
3
    // dp 数组，长度是 W+1，下标表示容量，值表示该容量下的最大价值
4
    // 一开始什么物品都没放，价值都是 0
5
    vector<int> dp(W + 1, 0);
6

7
    // 外层循环：依次考虑每个物品
8
    for (int i = 0; i < n; i++) {
9
        // 内层循环：从最大容量 W 往下遍历到当前物品的重量 wt[i]
10
        // 为什么要从大到小？因为如果从小到大，同一个物品| 方法 | 作用 | 说明 |
11
|------|------|------|
12
| `stack<T> st;` | 创建一个空的栈，元素类型为 `T` | 例如 `stack<int> st;` |
13
| `st.push(x);` | 将元素 `x` 压入栈顶 | 无返回值 |
14
| `st.pop();` | 弹出栈顶元素（删除） | 无返回值；**必须先确保栈非空**，否则未定义行为 |
15
| `st.top();` | 返回栈顶元素的引用 | 不删除元素；**必须先确保栈非空** |
16
| `st.empty();` | 判断栈是否为空 | 返回 `bool`，空为 `true` |
17
| `st.size();` | 返回栈中元素的个数 | 返回 `size_t` 类型 |
18
可能会被多次使用（完全背包）
19
        // 这里每个物品只能用一次，所以必须从大到小，保证更新时用到的 dp[w - wt[i]] 是没放过当前物品的状态
20
        for (int w = W; w >= wt[i]; w--) {
21
            // 对于当前容量 w，有两种选择：
22
            // 1. 不装这个物品，价值保持原来的 dp[w]
23
            // 2. 装这个物品，价值 = dp[w - wt[i]] + val[i]（腾出 wt[i] 空间，加上物品价值）
24
            // 我们取两者中较大的一个
25
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
26
        }
27
    }
28
    // 最终 dp[W] 就是容量为 W 时能获得的最大价值
29
    return dp[W];
30
}

1
#include <stack>
2
#include <iostream>
3
using namespace std;
4

5
int main() {
6
    // 创建一个存放 int 类型数据的栈
7
    stack<int> st;
8

9
    // 入栈：把 10 放到栈顶
10
    st.push(10);
11
    // 入栈：把 20 放到栈顶，现在栈顶是 20
12
    st.push(20);
13

14
    // 获取栈顶元素：top() 返回栈顶的值，但不删除它
15
    int topVal = st.top();   // 现在 topVal = 20
16
    cout << "栈顶元素是：" << topVal << endl;
17

18
    // 弹出栈顶：删除栈顶元素，没有返回值
19
    st.pop();                // 现在栈顶变成了 10
20

21
    // 判断栈是否为空：empty() 返回 true 表示空，false 表示非空
22
    if (st.empty()) {
23
        cout << "栈为空" << endl;
24
    } else {
25
        cout << "栈不为空" << endl;
26
    }
27

28
    // 获取栈中元素个数：size() 返回当前栈里的元素数量
29
    int sz = st.size();      // 此时只有一个元素 10，所以 sz = 1
30
    cout << "栈的大小是：" << sz << endl;
31

32
    return 0;
33
}

1
bool isValid(string s) {
2
    // 创建一个字符栈，用来存放左括号
3
    stack<char> st;
4

5
    // 遍历字符串中的每一个字符
6
    for (char c : s) {
7
        // 如果当前字符是左括号之一，就把它压入栈中
8
        if (c == '(' || c == '[' || c == '{') {
9
            st.push(c);
10
        } else {
11
            // 否则，当前字符是右括号
12
            // 首先检查栈是否为空：如果栈空，说明没有左括号来匹配，直接返回 false
13
            if (st.empty()) return false;
14

15
            // 取出栈顶的左括号（但不删除，先看看）
16
            char top = st.top();
17
            // 然后把这个左括号弹出（因为已经匹配上了）
18
            st.pop();
19

20
            // 检查当前右括号是否和弹出的左括号匹配
21
            // 如果匹配，继续循环；如果不匹配，返回 false
22
            if ((c == ')' && top != '(') ||
23
                (c == ']' && top != '[') ||
24
                (c == '}' && top != '{')) {
25
                return false;
26
            }
27
        }
28
    }
29
    // 所有字符处理完后，如果栈为空，说明所有括号都匹配了；否则有未匹配的左括号
30
    return st.empty();
31
}

1
// 计算 n! 的递归函数
2
int factorial(int n) {
3
    // 终止条件：如果 n 是 0 或 1，阶乘就是 1
4
    // 此时不再调用自己，直接返回 1
5
    if (n <= 1) return 1;
6

7
    // 递归调用：n! = n * (n-1)!
8
    // 这里调用自己，传入 n-1，让问题规模缩小
9
    return n * factorial(n - 1);
10
}

1
#include <vector>
2
#include <iostream>
3
using namespace std;
4

5
int main() {
6
    // 创建一个空的 vector，里面存放 int 类型的数据
7
    vector<int> v1;
8

9
    // 创建一个有 5 个元素的 vector，每个元素默认是 0
10
    vector<int> v2(5);
11

12
    // 创建一个有 5 个元素的 vector，每个元素初始化为 10
13
    vector<int> v3(5, 10);
14

15
    // 直接用花括号初始化，里面放 1,2,3,4
16
    vector<int> v4 = {1, 2, 3, 4};
17

18
    // 在 v1 的尾部添加一个元素 100
19
    v1.push_back(100);
20
    // 再添加一个元素 200
21
    v1.push_back(200);
22

23
    // 删除尾部元素（删除 200）
24
    v1.pop_back();
25

26
    // 通过下标访问元素（不检查边界，如果下标越界会导致未定义行为）
27
    int a = v1[0];            // a = 100
28
    // 通过 at() 访问元素（会检查边界，如果越界会抛出异常）
29
    int b = v1.at(0);         // b = 100
30
    // 获取第一个元素
31
    int first = v1.front();   // first = 100
32
    // 获取最后一个元素
33
    int last = v1.back();     // last = 100（因为只有一个元素）
34

35
    // 获取当前 vector 中元素的个数
36
    int size = v1.size();     // size = 1
37
    // 获取当前 vector 的容量（已经分配的内存能容纳多少个元素，可能大于 size）
38
    int cap = v1.capacity();  // 可能大于 1
39
    // 判断 vector 是否为空
40
    bool empty = v1.empty();  // false，因为有一个元素
41

42
    // 清空 vector 中的所有元素（size 变为 0，但容量可能不变）
43
    v1.clear();
44

45
    // 预分配空间：确保至少能容纳 100 个元素，避免多次扩容
46
    v1.reserve(100);
47

48
    // 遍历 vector 的两种方式
49
    // 方式1：用下标
50
    for (int i = 0; i < v1.size(); i++) {
51
        cout << v1[i] << " ";
52
    }
53
    // 方式2：范围 for 循环（C++11）
54
    for (int x : v1) {
55
        cout << x << " ";
56
    }
57

58
    return 0;
59
}

1
#include <algorithm>
2
vector<int> v = {5, 2, 8, 1, 9};
3

4
// 排序：将 v 中所有元素从小到大排列
5
sort(v.begin(), v.end());   // 现在 v 变成 {1, 2, 5, 8, 9}
6

7
// 反转：将 v 中所有元素的顺序颠倒
8
reverse(v.begin(), v.end()); // 现在 v 变成 {9, 8, 5, 2, 1}
9

10
// 二分查找：返回第一个 >= 5 的位置（下标）
11
int pos = lower_bound(v.begin(), v.end(), 5) - v.begin(); // pos = 2（因为 v[2]=5）

1
int n = 5;  // 顶点数 0~4
2
vector<vector<int>> graph(n);
3
// 添加无向边 0-1
4
graph[0].push_back(1);
5
graph[1].push_back(0);

1
// 创建一个布尔数组 visited，大小等于顶点数，初始全为 false
2
// visited[u] 表示顶点 u 是否已经被访问过
3
vector<bool> visited(n, false);
4

5
// DFS 函数，参数 u 是当前正在访问的顶点
6
void dfs(int u) {
7
    // 标记当前顶点 u 为已访问
8
    visited[u] = true;
9
    // 这里可以执行对 u 的操作，比如输出它
10
    cout << u << " ";
11

12
    // 遍历所有与 u 相邻的顶点
13
    for (int v : graph[u]) {
14
        // 如果邻居 v 还没有被访问过，就递归访问它
15
        if (!visited[v]) {
16
            dfs(v);
17
        }
18
    }
19
    // 当所有邻居都处理完后，函数返回，回溯到上一层
20
}

1
void dfsIter(int start) {
2
    // visited 数组记录是否访问过
3
    vector<bool> visited(n, false);
4
    // 创建一个栈，存放待访问的顶点
5
    stack<int> st;
6
    st.push(start);
7

8
    while (!st.empty()) {
9
        int u = st.top(); st.pop();   // 取出栈顶元素
10
        if (visited[u]) continue;     // 如果已经访问过，跳过
11
        visited[u] = true;            // 标记已访问
12
        cout << u << " ";             // 处理当前顶点
13

14
        // 将所有未访问的邻居压入栈
15
        for (int v : graph[u]) {
16
            if (!visited[v]) st.push(v);
17
        }
18
    }
19
}

1
#include <queue>
2
void bfs(int start) {
3
    // visited 数组记录是否已访问
4
    vector<bool> visited(n, false);
5
    // 队列，用来存储待访问的顶点，先进先出
6
    queue<int> q;
7
    // 把起点放入队列
8
    q.push(start);
9
    // 标记起点已访问
10
    visited[start] = true;
11

12
    while (!q.empty()) {
13
        // 取出队首元素
14
        int u = q.front(); q.pop();
15
        // 处理当前顶点 u（比如输出）
16
        cout << u << " ";
17

18
        // 遍历 u 的所有邻居
19
        for (int v : graph[u]) {
20
            // 如果邻居还没访问过
21
            if (!visited[v]) {
22
                // 标记为已访问，并加入队列尾部
23
                visited[v] = true;
24
                q.push(v);
25
            }
26
        }
27
    }
28
}

1
vector<int> dist(n, -1);   // dist[u] 表示从起点到 u 的最短距离，-1 表示未访问
2
queue<int> q;
3
dist[start] = 0;           // 起点到自己的距离是 0
4
q.push(start);
5

6
while (!q.empty()) {
7
    int u = q.front(); q.pop();
8
    for (int v : graph[u]) {
9
        if (dist[v] == -1) {           // 如果 v 还没被访问过
10
            dist[v] = dist[u] + 1;     // 距离 = 父节点距离 + 1
11
            q.push(v);
12
        }
13
    }
14
}