用vs做网站在安装时要勾选,全国代理网,推广网站广告有哪些,郑州建站时间48. 旋转图像
给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 #xff1a; 输入#xff1a;matrix [[5,1,9,11],[2,4,…48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 输入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]]
思路 以i0,j0元素5开始旋转过程中的交替顺序就是5-11-16-15-5
元素位置的行和列变化[0][0]-[0][3]-[3][3]-[3][0]-[0][0]
以元素1为例1-10-12-13-1
元素位置的行和列变化[0][1]-[1][3]-[3][2]-[2][0]-[0][1]
以元素9为例9-7-14-2-9
元素位置的行和列变化[0][2]-[2][3]-[3][1]-[1][0]-[0][2]
抽象成i和j的变化[i][j]-[j][n-1-i]-[n-1-i][n-1-j]-[n-1-j][i]-[i][j]
转换成核心代码注意需要一个临时变量去存储起点的值防止覆盖以后不知道旋转后的位置填入什么当然这个临时变量也可以存储终点的值最后填入起点也是可以的就是代码顺序变一下 int tempmatrix[i][j];matrix[i][j]matrix[n-j-1][i];matrix[n-j-1][i]matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1]matrix[j][n-i-1];matrix[j][n-i-1]temp;
到此最外圈已经处理完成不妨确定一下终止条件三个起点519它们i0j递增j一开始等于i最后小于n-1-i。(可以通过6X6的矩阵验证黄色是每圈的起点红色是每圈的终点) 加上之前的核心代码 for(int ji;jn-i-1;j){int tempmatrix[i][j];matrix[i][j]matrix[n-j-1][i];matrix[n-j-1][i]matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1]matrix[j][n-i-1];matrix[j][n-i-1]temp;}
最后就是处理圈由外向内收缩的过程通过6X6的矩阵可以看到圈数是35X5的矩阵圈数也是3所以圈数n/2,i从0开始递增。
代码
class Solution {
public:void rotate(vectorvectorint matrix) {int nmatrix.size();for(int i0;in/2;i){for(int ji;jn-i-1;j){int tempmatrix[i][j];matrix[i][j]matrix[n-j-1][i];matrix[n-j-1][i]matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1]matrix[j][n-i-1];matrix[j][n-i-1]temp;}} }
};
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 1 输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5
输出true
思路暴力可以直接两层循环解出来这里利用矩阵升序和降序的特点写出解法
我们可以模仿爬虫对于目标数如果当前处在的元素大于目标数我们就向降序的方向移动如果当前处在的元素小于目标数我们就向升序的方向移动。这就是爬虫选择方向的规则。
我们现在确定爬虫的起点左上左下右上右下
左上向右向下都是升序右下向上向左都是升序不作为爬虫的起点。
左下向右升序向上降序右上向左降序向下升序可以作为爬虫起点。
我们以左下为起点开始搜索目标值5185向上爬105向上爬35向右爬65向上爬找到返回true。 代码
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int imatrix.size()-1;int j0;while(i0jmatrix[0].size()){if(matrix[i][j]target) i--;//向上爬else if(matrix[i][j]target) j;//向右爬else return true;}return false;}
};
