通州网站建设电话优化课程体系

48. 旋转图像 - 力扣（LeetCode）

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

思路:

这道题的思路我们可以总结为两个步骤,可以手写一个看看

• 将矩阵绕着对角线交换元素
• 按照中间的那条线交换

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

49. 字母异位词分组 - 力扣（LeetCode）

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

输入: strs = [""]
输出: [[""]]

输入: strs = ["a"]
输出: [["a"]]

思路:

这道题就是用先排序,然后用哈希表记录对应下标即可

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {map<string, vector<int>> pos;for(int i = 0; i < strs.size(); i ++){string s = strs[i];sort(s.begin(), s.end());pos[s].push_back(i);}vector<vector<string>> ans;for(auto&[k, v] : pos){vector<string> temp;for(auto&c : v)temp.push_back(strs[c]);ans.push_back(temp);}return ans;}
};

53. 最大子数组和 - 力扣（LeetCode）

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

思路:

这道题可以用动态规划思路来实现,我们假设$f[i]$表示下标为i的最大值,所以$f[i]$可以由$max(f[i-1]+nums[i],nums[i])$转移得到

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1, 0);f[0] = nums[0];int res = nums[0];for(int i = 1; i < n; i ++){f[i] = max(f[i - 1] + nums[i], nums[i]);res = max(res, f[i]);}return res;}
};

55. 跳跃游戏 - 力扣（LeetCode）

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路:

我们能够跳到的肯定是连续的一段,所以我们只需要统计每一个点跳到最远的位置即可

class Solution {
public:bool canJump(vector<int>& nums) {for (int i = 0, j = 0; i < nums.size(); i ++ ) {if (j < i) return false;j = max(j, i + nums[i]);//}return true;}
};

56. 合并区间 - 力扣（LeetCode）

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路:

将所有区间按照左端点进行排序,然后遍历所有区间,如果新加入的区间左端点比当前区间的右端点还要大,即没有交集,我们就记录一个答案,并且更新新的左端点和右端点,最后不要忘记统计最后一个左端点和右端点

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

62. 不同路径 - 力扣（LeetCode）

输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

输入：m = 7, n = 3
输出：28

输入：m = 3, n = 3
输出：6

思路:

这道题也是经典的动态规划题目,每个点只能够从左边和上边转移过来,也是可以用记忆化搜索实现的

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for(int i = 0; i < m; i ++){dp[i][0] = 1;}for(int i = 0; i < n; i ++){dp[0][i] = 1;}for(int i = 1; i < m; i ++){for(int j = 1; j < n; j ++){dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}// return 0;return dp[m - 1][n - 1];}
};

class Solution {
public:vector<vector<int>> memo;int dfs(int x, int y){if(x == 0 || y == 0)return memo[x][y] = 1;if(memo[x][y] != 0)return memo[x][y];return memo[x][y] = dfs(x - 1, y) + dfs(x, y - 1);}int uniquePaths(int m, int n) {if(m <= 0 || n <= 0)return 0;memo = vector<vector<int>>(m, vector<int>(n, 0));return dfs(m - 1, n - 1);}
};