网站制作公司知道万维科技,电子商务网站建设 教学ppt,洛阳建设网站制作,85度c蛋糕房网站系统建设48. 旋转图像 - 力扣#xff08;LeetCode#xff09;
给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1#xff1…48. 旋转图像 - 力扣LeetCode
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1
输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[[7,4,1],[8,5,2],[9,6,3]]示例 2
输入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]]提示
n matrix.length matrix[i].length1 n 20-1000 matrix[i][j] 1000
思路:
这道题的思路我们可以总结为两个步骤,可以手写一个看看
将矩阵绕着对角线交换元素按照中间的那条线交换
class Solution {
public:void rotate(vectorvectorint 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
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]]提示
1 strs.length 1040 strs[i].length 100strs[i] 仅包含小写字母
思路:
这道题就是用先排序,然后用哈希表记录对应下标即可
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {mapstring, vectorint pos;for(int i 0; i strs.size(); i ){string s strs[i];sort(s.begin(), s.end());pos[s].push_back(i);}vectorvectorstring ans;for(auto[k, v] : pos){vectorstring temp;for(autoc : v)temp.push_back(strs[c]);ans.push_back(temp);}return ans;}
};53. 最大子数组和 - 力扣LeetCode
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2
输入nums [1]
输出1示例 3
输入nums [5,4,-1,7,8]
输出23提示
1 nums.length 105-104 nums[i] 104
**进阶**如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
思路:
这道题可以用动态规划思路来实现,我们假设 f [ i ] f[i] f[i]表示下标为i的最大值,所以 f [ i ] f[i] f[i]可以由 m a x ( f [ i − 1 ] n u m s [ i ] , n u m s [ i ] ) max(f[i - 1] nums[i], nums[i]) max(f[i−1]nums[i],nums[i])转移得到
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();vectorint 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 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示
1 nums.length 1040 nums[i] 105
思路:
我们能够跳到的肯定是连续的一段,所以我们只需要统计每一个点跳到最远的位置即可
class Solution {
public:bool canJump(vectorint 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 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。提示
1 intervals.length 104intervals[i].length 20 starti endi 104
思路:
将所有区间按照左端点进行排序,然后遍历所有区间,如果新加入的区间左端点比当前区间的右端点还要大,即没有交集,我们就记录一个答案,并且更新新的左端点和右端点,最后不要忘记统计最后一个左端点和右端点
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint 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 x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1
输入m 3, n 7
输出28示例 2
输入m 3, n 2
输出3
解释
从左上角开始总共有 3 条路径可以到达右下角。
1. 向右 - 向下 - 向下
2. 向下 - 向下 - 向右
3. 向下 - 向右 - 向下示例 3
输入m 7, n 3
输出28示例 4
输入m 3, n 3
输出6提示
1 m, n 100题目数据保证答案小于等于 2 * 109
思路:
这道题也是经典的动态规划题目,每个点只能够从左边和上边转移过来,也是可以用记忆化搜索实现的
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(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:vectorvectorint 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 vectorvectorint(m, vectorint(n, 0));return dfs(m - 1, n - 1);}
};
