LeetCode热题HOT100第五天

21. 旋转图像

思路

一次性旋转不行&＃xff0c;先对角线翻转&＃xff0c;再选择上下翻转

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n &＃61; matrix.size();for (int i &＃61; 0; i < n; i &＃43;&＃43; ) {for (int j &＃61; 0; j < i; j &＃43;&＃43; )swap(matrix[i][j], matrix[j][i]);}for (int i &＃61; 0; i < n; i &＃43;&＃43; ) {for (int j &＃61; 0, k &＃61; n - 1; j < k; j &＃43;&＃43; , k -- )swap(matrix[i][j], matrix[i][k]);}}
};


22. 字母异位词分组

思路

对每一个单词排序&＃xff0c;使用哈希映射到每一个分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for (auto& str : strs) {string s &＃61; str;sort(s.begin(), s.end());hash[s].push_back(str);}vector<vector<string>> res;for (auto& t : hash) res.push_back(t.second);return res;}
};


23. 最大子序和

思路&＃xff1a;动态规划

集合&＃xff1a;以$nums[i]$结尾的子序列最大值
转移&＃xff1a;不包含和包含前面的字符取最大值&＃xff0c;空间压缩

class Solution {
public:int maxSubArray(vector<int>& nums) {int maxn &＃61; nums[0], n &＃61; nums.size(), pre &＃61; nums[0];for (int i &＃61; 1; i < nums.size(); i &＃43;&＃43; ){int cur &＃61; max(pre &＃43; nums[i], nums[i]);maxn &＃61; max(cur, maxn);pre &＃61; cur;}return maxn;}
};


24. 跳跃游戏

思路

维护最大跳跃的位置

class Solution {
public:bool canJump(vector<int>& nums) {int n &＃61; nums.size();int res &＃61; 0;for (int i &＃61; 0; i < n; i &＃43;&＃43; ){if (i <&＃61; res)res &＃61; max(res, i &＃43; nums[i]);if (res >&＃61; n - 1) return true;}return false;}
};


25. 合并区间

思路

左端点排序&＃xff0c;$vector$按照第一关键词升序排序&＃xff0c;归并区间

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(), intervals.end());int l &＃61; intervals[0][0], r &＃61; intervals[0][1];for (int i &＃61; 1; i < intervals.size(); i &＃43;&＃43; ) {if (intervals[i][0] <&＃61; r) {r &＃61; max(r, intervals[i][1]);}else {res.push_back({l, r});l &＃61; intervals[i][0], r &＃61; intervals[i][1];}}res.push_back({l, r});return res;}
};