力扣C++

### LeetCode C++ 解题方案与示例代码 #### LRU缓存问题的C++实现 LRU（Least Recently Used）缓存是一种常见的数据结构设计问题，在LeetCode上也经常作为面试考察的重点之一。该问题的核心在于维护一个固定容量的数据存储空间，当达到容量上限时自动淘汰最久未使用的项。 下面展示了一个基于双向链表和哈希映射的高效C++实现方法： ```cpp #include <unordered_map> #include <list> class LRUCache { public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { auto it = cache.find(key); if (it == cache.end()) return -1; // 将访问过的节点移到前面 lru.splice(lru.begin(), lru, it->second); return it->second->second; } void put(int key, int value) { auto it = cache.find(key); if (it != cache.end()) { // 更新已有键值对的位置到队首 lru.splice(lru.begin(), lru, it->second); it->second->second = value; return; } if (lru.size() >= cap) { // 移除最近最少使用的元素 int lastKey = lru.back().first; cache.erase(lastKey); lru.pop_back(); } lru.emplace_front(std::make_pair(key, value)); cache[key] = lru.begin(); } private: std::list<std::pair<int, int>> lru; // 双向链表用于记录顺序 std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache; // 哈希表快速查找 int cap; // 容量大小 }; ``` 上述代码实现了LRU缓存的功能[^3]，其中`get`函数负责获取指定key对应的value，并将其移动至最近使用位置；而`put`函数则在更新或新增键值对的同时处理超出容量的情况。 --- #### 全排列问题的C++回溯算法实现 全排列问题是另一个经典算法题目，可以通过回溯法来解决。给定一组不重复的数字，返回其所有的可能排列组合。 下面是完整的C++代码实现： ```cpp #include <vector> using namespace std; void backtrack(vector<vector<int>>& res, vector<int>& path, vector<bool>& used, const vector<int>& nums) { if (path.size() == nums.size()) { res.push_back(path); // 当路径长度等于数组长度时保存结果 return; } for (int i = 0; i < nums.size(); ++i) { if (!used[i]) { // 如果当前数尚未被使用 used[i] = true; // 标记已使用状态 path.push_back(nums[i]); // 加入路径 backtrack(res, path, used, nums); // 进一步递归探索 path.pop_back(); // 回退操作 used[i] = false; // 恢复标记 } } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; vector<int> currentPath; vector<bool> visited(nums.size(), false); backtrack(result, currentPath, visited, nums); return result; } ``` 此代码片段定义了`permute`函数，它接收输入数组并返回所有可能的排列列表[^2]。核心逻辑由辅助函数`backtrack`完成，采用深度优先搜索的方式逐步构建每一种可能性。 --- #### 并行计算中的多线程优化 除了以上两个具体问题外，C++还擅长于高性能计算领域内的任务分配与资源管理。例如，可以借助标准库 `<thread>` 实现简单的并发执行模式以提升效率。以下是一段演示如何利用多线程加速矩阵乘法运算的例子： ```cpp #include <iostream> #include <vector> #include <thread> using namespace std; const int N = 100; // 矩阵维度 // 单一线程版本 void multiply(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int rowStart, int rowEnd) { for (int i = rowStart; i < rowEnd; ++i) { for (int j = 0; j < N; ++j) { for (int k = 0; k < N; ++k) { C[i][j] += A[i][k] * B[k][j]; } } } } int main() { vector<thread> threads; vector<vector<int>> A(N, vector<int>(N)), B(N, vector<int>(N)), C(N, vector<int>(N, 0)); // 初始化A和B... int numThreads = thread::hardware_concurrency(); // 获取CPU支持的最大线程数量 for (int t = 0; t < numThreads; ++t) { int startRow = (N / numThreads) * t; int endRow = ((t == numThreads - 1) ? N : (N / numThreads) * (t + 1)); threads.emplace_back(multiply, ref(A), ref(B), ref(C), startRow, endRow); } for(auto& th : threads){ th.join(); } cout << "Matrix multiplication completed." << endl; return 0; } ``` 这段程序展示了如何将大尺寸矩阵分解成若干子区域分别交给不同线程独立计算[^1]，从而显著缩短整体耗时。 ---