leetcode hot100题c++

### LeetCode Hot 100 Problems C++ Solutions 以下是针对 LeetCode 上热门的前 100 题中的部分经典题目提供的一些高效解决方案及其分析。 #### 移除指定元素 移除数组中等于给定值 `val` 的所有元素并返回新的长度。可以采用双指针方法来优化性能，时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)[^1]。 ```cpp class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0; for(int fast = 0; fast < nums.size(); ++fast){ if(nums[fast] != val){ nums[slow++] = nums[fast]; } } return slow; } }; ``` #### 寻找多数元素 在一个大小为 \(n\) 的数组中找到出现次数超过 \(\lfloor n/2 \rfloor\) 的元素。可以通过哈希表统计频率实现，但更优的方法是摩尔投票法（Boyer-Moore Voting Algorithm），其时间复杂度同样为 \(O(n)\)，而空间复杂度降到了 \(O(1)\)[^2]。 ```cpp class Solution { public: int majorityElement(vector<int>& nums) { int count = 0, candidate = 0; for(auto num : nums){ if(count == 0){ candidate = num; } count += (num == candidate ? 1 : -1); } return candidate; } }; ``` #### 单词接龙 II 通过广度优先搜索（BFS）求解单词转换问题。构建邻接字典加速匹配过程，并记录访问状态防止循环依赖。最终返回从起始单词到目标单词所需的最少变换步数[^3]。 ```cpp unordered_map<string, vector<string>> buildGraph(string& startWord, string& endWord, vector<string>& wordList){ unordered_set<string> dict(wordList.begin(), wordList.end()); unordered_map<string, vector<string>> graph; auto addEdge = [&](string s1, string s2)->void{ graph[s1].push_back(s2); graph[s2].push_back(s1); }; queue<pair<string, int>> q; q.push({startWord, 0}); while(!q.empty()){ pair<string, int> current = q.front(); q.pop(); string currStr = current.first; if(currStr == endWord && !graph.count(endWord)){ break; } for(char c='a';c<='z';++c){ for(int i=0;i<currStr.length();++i){ char originalChar = currStr[i]; currStr[i] = c; if(dict.find(currStr)!=dict.end() && !(current.second >0 && find(graph[currStr].begin(), graph[currStr].end(), currStr) != graph[currStr].end())){ addEdge(currStr, currStr); if(current.second >=0 ){ q.push({currStr, current.second+1}); } } currStr[i] = originalChar; } } } return graph; } ```