C++力扣hot100

### C++ 实现 LeetCode Hot 100 问题解决方案 以下是针对部分 LeetCode Hot 100 中的经典问题提供基于 C++ 的解决方案： #### 1. **移除元素** 该问题是关于如何从数组中删除指定值并返回新的长度。可以通过双指针方法来优化性能。 ```cpp class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0, fast = 0; while (fast < nums.size()) { if (nums[fast] != val) { nums[slow++] = nums[fast]; } fast++; } return slow; } }; ``` 上述代码实现了时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\) 的算法[^1]。 --- #### 2. **寻找多数元素** 给定一个大小为 \(n\) 的数组，其中有一个数字出现超过 \(\lfloor n/2 \rfloor\) 次。可以利用哈希表统计频率或者采用摩尔投票法进一步降低空间复杂度。 ##### 基于哈希表的方法： ```cpp class Solution { public: int majorityElement(vector<int>& nums) { map<int, int> m; int threshold = nums.size() / 2; for(auto& val : nums){ if(m.find(val) == m.end()){ m[val] = 1; } else{ m[val]++; } if(m[val] > threshold){ return val; } } return -1; } }; ``` 这种方法的时间复杂度为 \(O(n)\)，但由于使用了额外的空间存储键值对，因此其空间复杂度也为 \(O(n)\)[^2]。 ##### 使用摩尔投票法改进： ```cpp class Solution { public: int majorityElement(vector<int>& nums) { int count = 0, candidate = 0; for(int num : nums){ if(count == 0){ candidate = num; } count += (num == candidate ? 1 : -1); } return candidate; } }; ``` 通过这种方式，我们能够将空间复杂度降至 \(O(1)\)。 --- #### 3. **单词接龙 II** 这是一个典型的广度优先搜索（BFS）问题，目标是从 `beginWord` 转化到 `endWord` 所需的最少转换次数。 ```cpp unordered_map<string, vector<string>> graph; bool bfs(string beginWord, string endWord, unordered_set<string>& wordList) { queue<pair<string, int>> q; q.push({beginWord, 0}); unordered_set<string> visited; visited.insert(beginWord); while(!q.empty()) { auto current = q.front(); q.pop(); string word = current.first; int steps = current.second; if(word == endWord) { return true; } for(char c='a';c<='z';c++) { for(int i=0;i<word.length();i++) { char originalChar = word[i]; word[i] = c; if(wordList.count(word) && !visited.count(word)) { visited.insert(word); q.push({word, steps + 1}); // 构建图结构用于后续回溯 graph[word].push_back(current.first); } word[i] = originalChar; } } } return false; } ``` 这段代码展示了如何构建 BFS 图形以及记录每一步的状态变化过程[^3]。 --- #### 总结 以上提供了三个经典 LeetCode HOT 100 问题及其对应的 C++ 解决方案。这些例子涵盖了不同的数据结构和算法技巧，包括但不限于双指针、哈希映射、摩尔投票法以及广度优先搜索等技术。