C++ STL 容器学习笔记#

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

5
int main() {
6
    // 1. 定义一维 vector
7
    vector<int> arr;
8

9
    // 2. 初始化 100 个元素（提前分配，避免扩容）
10
    vector<int> arr1(100);
11

12
    // 3. 初始化 100 个元素，初值为 1
13
    vector<int> arr2(100, 1);
14

15
    // 4. 定义二维 vector（100 行，列数不定）
16
    vector<vector<int>> arr3(100, vector<int>());
17

18
    // 5. 定义二维 vector（100 行 666 列，初值 -1）
19
    vector<vector<int>> arr4(100, vector<int>(666, -1));
20

21
    // 6. 固定行数的二维数组（推荐简洁写法）
22
    vector<int> arr5[100];  // 100 行，每行是独立的 vector
23

24
    return 0;
25
}

1
// 示例：构建邻接表
2
vector<int> graph[100];  // 100 个节点的图
3

4
// 添加边：1 -> 2, 1 -> 3
5
graph[1].push_back(2);
6
graph[1].push_back(3);
7

8
// 遍历节点 1 的所有邻居
9
for (int neighbor : graph[1]) {
10
    cout << neighbor << " ";  // 输出: 2 3
11
}
12

13
// 访问第 1 行第 0 列
14
cout << graph[1][0];  // 输出: 2

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

5
int main() {
6
    // 创建并初始化
7
    vector<int> scores(5, 0);
8

9
    // 输入 5 个分数
10
    for (int i = 0; i < 5; i++) {
11
        cin >> scores[i];
12
    }
13

14
    // 计算平均分
15
    int sum = 0;
16
    for (int score : scores) {
17
        sum += score;
18
    }
19
    double avg = sum / (double)scores.size();
20

21
    cout << "平均分: " << avg << endl;
22

23
    return 0;
24
}

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

5
int main() {
6
    // 构造栈
7
    stack<int> stk;
8

9
    // 进栈
10
    stk.push(10);  // [10]
11
    stk.push(20);  // [10, 20]
12
    stk.push(30);  // [10, 20, 30]
13

14
    // 取栈顶元素
15
    cout << stk.top();  // 30
16

17
    // 出栈
18
    stk.pop();  // [10, 20]
19
    cout << stk.top();  // 20
20

21
    // 检查是否为空
22
    if (!stk.empty()) {
23
        cout << "栈非空" << endl;
24
    }
25

26
    // 获取大小
27
    cout << "栈大小: " << stk.size();  // 2
28

29
    return 0;
30
}

1
vector<int> v;
2

3
// 进栈
4
v.push_back(10);
5
v.push_back(20);
6
v.push_back(30);
7

8
// 取栈顶
9
cout << v.back();  // 30
10

11
// 出栈
12
v.pop_back();
13
cout << v.back();  // 20

1
bool isValid(string s) {
2
    stack<char> stk;
3

4
    for (char c : s) {
5
        if (c == '(' || c == '[' || c == '{') {
6
            stk.push(c);
7
        } else {
8
            if (stk.empty()) return false;
9

10
            char top = stk.top();
11
            stk.pop();
12

13
            if ((c == ')' && top != '(') ||
14
                (c == ']' && top != '[') ||
15
                (c == '}' && top != '{')) {
16
                return false;
17
            }
18
        }
19
    }
20

21
    return stk.empty();
22
}
23

24
// 测试
25
cout << isValid("()[]{}");   // true
26
cout << isValid("([)]");     // false
27
cout << isValid("{[()]}");   // true

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

5
int main() {
6
    // 构造队列
7
    queue<int> que;
8

9
    // 进队
10
    que.push(10);  // [10]
11
    que.push(20);  // [10, 20]
12
    que.push(30);  // [10, 20, 30]
13

14
    // 取队首
15
    cout << que.front();  // 10
16

17
    // 取队尾
18
    cout << que.back();   // 30
19

20
    // 出队
21
    que.pop();  // [20, 30]
22
    cout << que.front();  // 20
23

24
    // 大小
25
    cout << que.size();  // 2
26

27
    return 0;
28
}

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

6
// 二维网格的 BFS
7
int bfs(vector<vector<int>>& grid, int startX, int startY) {
8
    int n = grid.size();
9
    int m = grid[0].size();
10

11
    queue<pair<int, int>> que;
12
    que.push({startX, startY});
13

14
    vector<vector<bool>> visited(n, vector<bool>(m, false));
15
    visited[startX][startY] = true;
16

17
    int steps = 0;
18

19
    while (!que.empty()) {
20
        int size = que.size();
21

22
        for (int i = 0; i < size; i++) {
23
            auto [x, y] = que.front();
24
            que.pop();
25

26
            if (grid[x][y] == 9) {  // 找到目标
27
                return steps;
28
            }
29

30
            // 四个方向
31
            int dx[] = {-1, 1, 0, 0};
32
            int dy[] = {0, 0, -1, 1};
33

34
            for (int d = 0; d < 4; d++) {
35
                int nx = x + dx[d];
36
                int ny = y + dy[d];
37

38
                if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
39
                    !visited[nx][ny] && grid[nx][ny] != -1) {
40
                    que.push({nx, ny});
41
                    visited[nx][ny] = true;
42
                }
43
            }
44
        }
45
        steps++;
46
    }
47

48
    return -1;  // 未找到
49
}

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

5
int main() {
6
    // 1. 大顶堆（默认）
7
    priority_queue<int> pque1;
8

9
    // 2. 小顶堆
10
    priority_queue<int, vector<int>, greater<int>> pque2;
11

12
    // 进堆
13
    pque1.push(30);
14
    pque1.push(10);
15
    pque1.push(50);
16
    pque1.push(20);
17

18
    // 取堆顶（最大值）
19
    cout << pque1.top();  // 50
20

21
    // 出堆
22
    pque1.pop();
23
    cout << pque1.top();  // 30
24

25
    return 0;
26
}

1
// 大顶堆：堆顶是最大值
2
priority_queue<int> maxHeap;
3
maxHeap.push(5);
4
maxHeap.push(2);
5
maxHeap.push(8);
6
cout << maxHeap.top();  // 8
7

8
// 小顶堆：堆顶是最小值
9
priority_queue<int, vector<int>, greater<int>> minHeap;
10
minHeap.push(5);
11
minHeap.push(2);
12
minHeap.push(8);
13
cout << minHeap.top();  // 2

1
vector<int> topKFrequent(vector<int>& nums, int k) {
2
    // 小顶堆，保持大小为 k
3
    priority_queue<int, vector<int>, greater<int>> pque;
4

5
    for (int num : nums) {
6
        pque.push(num);
7

8
        if (pque.size() > k) {
9
            pque.pop();  // 弹出最小值
10
        }
11
    }
12

13
    // 堆中剩下的就是前 k 大元素
14
    vector<int> result;
15
    while (!pque.empty()) {
16
        result.push_back(pque.top());
17
        pque.pop();
18
    }
19

20
    return result;
21
}