发表更新7 分钟读完 (大约1004个字)0次访问

c++ stl对应代码

下面是每个题目对应的 C++ 代码，使用了 std 命名空间：

1. 基础题目：

题目1：使用 std::vector 实现动态数组

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> nums;
    int n, input;

    cout << "Enter the number of elements: ";
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cout << "Enter a number: ";
        cin >> input;
        nums.push_back(input);
    }

    sort(nums.begin(), nums.end());

    cout << "Sorted numbers: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

题目2：使用 std::list 实现链表

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
#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> numbers;
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_front(5);

    auto it = numbers.begin();
    advance(it, 1); // 指向第二个元素
    numbers.insert(it, 15);

    cout << "List elements: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    numbers.erase(it); // 删除刚才插入的15

    cout << "List after erasing an element: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

题目3：使用 std::set 实现唯一元素集合

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
#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> unique_numbers;
    int n, input;

    cout << "Enter the number of elements: ";
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cout << "Enter a number: ";
        cin >> input;
        unique_numbers.insert(input); // 自动去重
    }

    cout << "Unique sorted numbers: ";
    for (int num : unique_numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

题目4：使用 std::map 实现简单的词频统计

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
#include <iostream>
#include <map>
#include <sstream>

using namespace std;

int main() {
    map<string, int> word_count;
    string input, word;

    cout << "Enter a sentence: ";
    getline(cin, input);

    stringstream ss(input);

    while (ss >> word) {
        word_count[word]++;
    }

    cout << "Word frequencies:" << endl;
    for (auto pair : word_count) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

2. 进阶题目：

题目5：使用 std::priority_queue 实现任务调度

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
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Task {
    string name;
    int priority;

    bool operator<(const Task& other) const {
        return priority < other.priority; // 优先级高的任务排在队列前
    }
};

int main() {
    priority_queue<Task> tasks;

    tasks.push({"Task 1", 1});
    tasks.push({"Task 2", 5});
    tasks.push({"Task 3", 3});

    while (!tasks.empty()) {
        Task t = tasks.top();
        tasks.pop();
        cout << "Executing " << t.name << " with priority " << t.priority << endl;
    }

    return 0;
}

题目6：用 std::stack 实现括号匹配

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
#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == '}' && st.top() != '{') return false;
            if (c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string s;
    cout << "Enter a string of brackets: ";
    cin >> s;

    if (isValid(s)) {
        cout << "Valid" << endl;
    } else {
        cout << "Invalid" << endl;
    }

    return 0;
}

题目7：实现 LRU 缓存机制

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
49
50
51
52
53
54
55
#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cacheList;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) return -1;

        auto it = cacheMap[key];
        int value = it->second;
        cacheList.erase(it);
        cacheList.push_front({key, value});
        cacheMap[key] = cacheList.begin();
        return value;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            cacheList.erase(cacheMap[key]);
        } else if (cacheList.size() == capacity) {
            int oldKey = cacheList.back().first;
            cacheList.pop_back();
            cacheMap.erase(oldKey);
        }

        cacheList.push_front({key, value});
        cacheMap[key] = cacheList.begin();
    }
};

int main() {
    LRUCache cache(2); // 缓存容量为2

    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 返回1
    cache.put(3, 3);              // 移除键2
    cout << cache.get(2) << endl; // 返回-1
    cache.put(4, 4);              // 移除键1
    cout << cache.get(1) << endl; // 返回-1
    cout << cache.get(3) << endl; // 返回3
    cout << cache.get(4) << endl; // 返回4

    return 0;
}

3. 高级题目：

题目8：使用 std::unordered_map 实现字典树（Trie）

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
49
50
51
52
53
54
55
56
#include <iostream>
#include <unordered_map>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }

    bool search(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    
    cout << trie.search("app") << endl;   // 返回 true
    cout << trie.search("apple") << endl; // 返回 true
    cout << trie.search("appl") << endl;  // 返回 false

    return 0;
}

题目9：基于 std::multimap 实现的多重映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <map>

using namespace std;

int main() {
    multimap<int, string> students;
    students.insert({90, "Alice"});
    students.insert({85, "Bob"});
    students.insert({90, "Charlie"});

    cout << "Students and their scores: " << endl;
    for (auto& [score, name] : students) {
        cout << name << " - " << score << endl;
    }

    return 0;
}

题目10：用 std::deque 实现滑动窗口最大值

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
#include <iostream>
#include <deque>
#include <vector>

using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }

        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back

();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    vector<int> result = maxSlidingWindow(nums, k);
    cout << "Sliding window maximums: ";
    for (int maxVal : result) {
        cout << maxVal << " ";
    }
    cout << endl;

    return 0;
}

这些代码覆盖了容器相关的基础和进阶问题，能帮助你更好地理解和运用 C++ 的标准模板库 (STL)。如果需要进一步解释某个题目或代码细节，可以随时讨论！

c++ stl对应代码

https://mr-xiongyq.github.io/2024/09/20/c-stl对应代码/

作者

Xiongyuqi

发布于

2024-09-20

更新于

2024-10-29

许可协议

评论

关注我

链接

分类

最新文章

归档

标签

C++8
Computer1
C语言3
linux1
rag1
transformer3
代码1
代码实现1
堆栈3
多模态1
字符串3
字符串处理1
字符处理1
排序1
数学函数1
数据结构4
日常1
算法19
算法设计3
算法设计、动态规划1
算法设计概念1
编程3
证明题3
输入方法1
面经1
面经1-swimtransformer1
面经2-attention(注意力机制)1
面试真题1
面试经验1
×