leetcode hot100有哪些

### LeetCode Hot 100 Problems C++ Solutions 以下是针对LeetCode热门题目的一些常见问题及其C++解决方案的概述。这些解答基于常见的算法思想，如滑动窗口、哈希表以及字符串操作等。 #### 反转字符串 对于反转字符串的问题，可以采用双指针的方法来交换数组中的字符位置[^1]。这种方法的时间复杂度为O(n)，其中n是字符串长度，而空间复杂度为O(1)。 ```cpp class Solution { public: void reverseString(std::vector<char>& s) { int n = s.size(); int left = 0, right = n - 1; while (left < right) { std::swap(s[left++], s[right--]); } } }; ``` #### 不重复最长子串 不重复最长子串可以通过滑动窗口的思想实现[^2]。通过维护一个动态变化的窗口并记录当前无重复字符的最大长度，可以在一次遍历中完成计算。 ```cpp class Solution { public: int lengthOfLongestSubstring(const std::string& s) { std::unordered_set<char> window; int maxLength = 0, start = 0; for(int i = 0;i<s.length();i++) { char currentChar = s[i]; while(window.find(currentChar)!=window.end()) { window.erase(s[start]); ++start; } window.insert(currentChar); maxLength = std::max(maxLength,i-start+1); } return maxLength; } }; ``` #### 多数元素查找 多数元素查找问题是另一个经典案例，通常可以用摩尔投票法或者哈希映射方法解决[^3]。这里展示的是利用哈希表的方式，其时间复杂度为O(n)，空间复杂度同样为O(n)。 ```cpp class Solution { public: int majorityElement(std::vector<int>& nums) { std::map<int,int> countMap; int threshold = nums.size() / 2; for(auto num : nums){ if(countMap.find(num)==countMap.end()){ countMap[num]=1; }else{ countMap[num]++; } if(countMap[num]>threshold){ return num; } } return -1; } }; ``` #### 广度优先搜索(BFS) 广度优先搜索是一种用于图结构探索的技术，在某些场景下也可以应用于语义关联网络等问题[^4]。下面是一个简单的BFS模板例子： ```cpp #include <queue> #include <vector> void bfs(int root,std::vector<std::vector<int>> adjList){ std::queue<int> q; std::vector<bool> visited(adjList.size(),false); q.push(root); visited[root]=true; while(!q.empty()){ int node=q.front();q.pop(); // Process the node here... for(auto neighbor:adjList[node]){ if(!visited[neighbor]){ q.push(neighbor); visited[neighbor]=true; } } } } ```

### 关于 LeetCode Hot100 的题目解析与代码实现 以下是针对部分经典 LeetCode Hot100 题目的详细解析和代码实现： --- #### **可被三整除的最大和** 此题的核心在于动态规划的应用。通过构建状态转移方程来解决子序列求和问题。 ```python from functools import lru_cache def maxSumDivThree(nums): @lru_cache(None) def dp(index, remainder): if index == len(nums): return 0 if remainder == 0 else float('-inf') take = nums[index] + dp(index + 1, (remainder + nums[index]) % 3) not_take = dp(index + 1, remainder) return max(take, not_take) return dp(0, 0) ``` 上述方法利用记忆化递归来优化时间复杂度，确保每种可能的状态仅计算一次[^1]。 --- #### **玩筹码** 该问题可以通过贪心算法高效解决。核心思路是统计奇偶位置上的筹码数量并选择代价较小的操作方式。 ```python def minCostToMoveChips(position): even_count = sum(p % 2 == 0 for p in position) odd_count = len(position) - even_count return min(even_count, odd_count) ``` 这里的时间复杂度为 O(n)，其中 n 是 `position` 数组的长度。 --- #### **买卖股票的最佳时机** 这是一道经典的单次交易最大利润问题，可以采用线性扫描的方式完成。 ```python def maxProfit(prices): min_price = float('inf') max_profit = 0 for price in prices: if price < min_price: min_price = price elif price - min_price > max_profit: max_profit = price - min_price return max_profit ``` 这段代码的关键在于维护当前最低价格以及潜在的最大收益。 --- #### **跳跃游戏 I 和 II** 这两道题分别涉及布尔判断和最小步数计算。前者可通过记录可达范围快速判定，后者则需借助动态规划思想逐步推进最优路径。 ##### 跳跃游戏 I ```python def canJump(nums): farthest = 0 for i, jump in enumerate(nums): if i > farthest: return False farthest = max(farthest, i + jump) return True ``` ##### 跳跃游戏 II ```python def jump(nums): jumps = current_end = farthest = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == current_end and i != len(nums) - 1: jumps += 1 current_end = farthest return jumps ``` 两者的共同特点是基于局部最优解推导全局最佳策略。 --- #### **划分字母区间** 本题要求找到字符串中的不重叠分区数目，适合用双指针配合哈希表处理。 ```python def partitionLabels(s): last_occurrence = {c: i for i, c in enumerate(s)} partitions = [] start = end = 0 for i, char in enumerate(s): end = max(end, last_occurrence[char]) if i == end: partitions.append(end - start + 1) start = i + 1 return partitions ``` 这种方法能够在线性时间内解决问题，并且保持空间开销较低。 --- #### **移动零** 对于数组操作类问题，“头部”扩展技巧非常实用。具体做法如下所示： ```python def moveZeroes(nums): head = 0 for i in range(len(nums)): if nums[i] != 0: nums[head], nums[i] = nums[i], nums[head] head += 1 ``` 此处逻辑清晰明了，只需两次遍历即可达成目标[^2]。 --- ### 总结 以上展示了若干热门 LeetCode 题目及其解决方案。这些例子涵盖了多种常见算法模式，包括但不限于动态规划、贪心算法、滑动窗口等技术手段。