LeetCode 热题-矩阵置零 螺旋矩阵 旋转图像

矩阵置零73. 矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/给定一个mxn的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法。示例 1输入matrix [[1,1,1],[1,0,1],[1,1,1]]输出[[1,0,1],[0,0,0],[1,0,1]]示例 2输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示m matrix.lengthn matrix[0].length1 m, n 200-2^31 matrix[i][j] 2^31 - 1进阶一个直观的解决方案是使用O(mn)的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用O(mn)的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗难点考虑到不能边检查0边置零如何减少空间复杂度首先排除位运算因为m和n的大小超过64达到200无法使用位运算表示解法1空间复杂度O(mn)class Solution { public: void func(bool flag, int x, vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); if (!flag) { for (int i 0; i n; i) { matrix[x][i] 0; } return; } for (int i 0; i m; i) { matrix[i][x] 0; } } void setZeroes(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); vectorint mflag(m,0),nflag(n,0); for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { mflag[i]1; nflag[j]1; } } } for (int i 0; i m; i) { if(mflag[i]1) func(0,i,matrix); } for (int i 0; i n; i) { if(nflag[i]1) func(1,i,matrix); } return; } };解法2常量空间复杂度难绷竟然是标记第一行第一列0的情况然后用第一行第一列记录剩下矩阵的情况class Solution { public: void setZeroes(vectorvectorint matrix) { int flagr1,flagc1; int m matrix.size(), n matrix[0].size(); for(int i0;im;i) { if(!matrix[i][0]) flagc0; } for(int i0;in;i) { if(!matrix[0][i]) flagr0; } for(int i1;im;i) { for(int j1;jn;j) { if(!matrix[i][j]) { matrix[0][j]0; matrix[i][0]0; } } } for(int i1;im;i) { for(int j1;jn;j) { if(!matrix[0][j]||!matrix[i][0]) { matrix[i][j]0; } } } if(!flagc) { for(int i0;im;i) { matrix[i][0]0; } } if(!flagr) { for(int i0;in;i) { matrix[0][i]0; } } return; } };螺旋矩阵54. 螺旋矩阵https://leetcode.cn/problems/spiral-matrix/给你一个m行n列的矩阵matrix请按照顺时针螺旋顺序返回矩阵中的所有元素。示例 1输入matrix [[1,2,3],[4,5,6],[7,8,9]]输出[1,2,3,6,9,8,7,4,5]示例 2输入matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出[1,2,3,4,8,12,11,10,9,5,6,7]提示m matrix.lengthn matrix[i].length1 m, n 10-100 matrix[i][j] 100解法1模拟dfs思想但是碰壁了再改变方向class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { vectorint res; int x0,y0; int lastx0,lasty0; int mmatrix.size(),nmatrix[0].size(); int dx[] {0,1,0,-1}; int dy[] {1,0,-1,0}; res.push_back(matrix[x][y]); int i0;//先右走 matrix[x][y]200; while(res.size()n*m) { int ux xdx[i], uy ydy[i]; if(uxm||ux0||uyn||uy0) { i(i1)%4; continue; } if(matrix[ux][uy]200) { i(i1)%4; continue; } if(uxlastxuylasty) { i(i1)%4; continue; } res.push_back(matrix[ux][uy]); matrix[x][y]200; lastxx,lastyy; xux,yuy; } return res; } };解法2按层模拟可以将矩阵看成若干层首先输出最外层的元素其次输出次外层的元素直到输出最内层的元素。定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如下图矩阵最外层元素都是第 1 层次外层元素都是第 2 层剩下的元素都是第 3 层。[[1, 1, 1, 1, 1, 1, 1],[1, 2, 2, 2, 2, 2, 1],[1, 2, 3, 3, 3, 2, 1],[1, 2, 2, 2, 2, 2, 1],[1, 1, 1, 1, 1, 1, 1]]对于每层从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)右下角位于 (bottom,right)按照如下顺序遍历当前层的元素。从左到右遍历上侧元素依次为 (top,left) 到 (top,right)。从上到下遍历右侧元素依次为 (top1,right) 到 (bottom,right)。如果 leftright 且 topbottom则从右到左遍历下侧元素依次为 (bottom,right−1) 到 (bottom,left1)以及从下到上遍历左侧元素依次为 (bottom,left) 到 (top1,left)。遍历完当前层的元素之后将 left 和 top 分别增加 1将 right 和 bottom 分别减少 1进入下一层继续遍历直到遍历完所有元素为止。class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { if (matrix.size() 0 || matrix[0].size() 0) { return {}; } int rows matrix.size(), columns matrix[0].size(); vectorint order; int left 0, right columns - 1, top 0, bottom rows - 1; while (left right top bottom) { for (int column left; column right; column) { order.push_back(matrix[top][column]); } for (int row top 1; row bottom; row) { order.push_back(matrix[row][right]); } if (left right top bottom) { for (int column right - 1; column left; column--) { order.push_back(matrix[bottom][column]); } for (int row bottom; row top; row--) { order.push_back(matrix[row][left]); } } left; right--; top; bottom--; } return order; } };复杂度分析时间复杂度O(mn)其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。空间复杂度O(1)。除了输出数组以外空间复杂度是常数。作者力扣官方题解链接https://leetcode.cn/problems/spiral-matrix/solutions/275393/luo-xuan-ju-zhen-by-leetcode-solution/旋转图像48. 旋转图像https://leetcode.cn/problems/rotate-image/给定一个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解法1同上一题class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { vectorint res; int x0,y0; int lastx0,lasty0; int mmatrix.size(),nmatrix[0].size(); int dx[] {0,1,0,-1}; int dy[] {1,0,-1,0}; res.push_back(matrix[x][y]); int i0;//先右走 matrix[x][y]1001; while(res.size()n*m) { int ux xdx[i], uy ydy[i]; if(uxm||ux0||uyn||uy0) { i(i1)%4; continue; } if(matrix[ux][uy]1001) { i(i1)%4; continue; } if(uxlastxuylasty) { i(i1)%4; continue; } res.push_back(matrix[ux][uy]); matrix[x][y]1001; lastxx,lastyy; xux,yuy; } return res; } void rotate(vectorvectorint matrix) { int indx0; int lastx0,lasty0; int mmatrix.size(),nmatrix[0].size(); int lx 0,rx n-1,ly0,ryn-1; int x0,yn-1; vectorint res(n*n,0) ; res spiralOrder(matrix); int dx[] {1,0,-1,0}; int dy[] {0,-1,0,1}; int i0,sx0,syn-1; matrix[x][y]res[indx]; indx; while(indxn*n) { int ux xdx[i], uy ydy[i]; if(uxrx||uxlx||uyry||uyly) { i(i1)%4; continue; } if(uxsxuysy) //走到头了 { i(i1)%4; sx; sy--; xsx,ysy; matrix[x][y]res[indx]; lx,ly,rx--,ry--; indx; continue; } if(uxlastxuylasty) { i(i1)%4; continue; } lastxx,lastyy; xux,yuy; matrix[x][y]res[indx]; indx; } } };典型错误class Solution { public: void rotate(vectorvectorint matrix) { int n matrix.size(); vectorpairint,int loc;//顺时针的顺序 vectorint nums;//顺时针的结果 int left0,rightn-1; while(leftright) { for(int ileft;iright;i) { loc.push_back({left,i}); nums.push_back(matrix[left][i]); } for(int ileft1;iright;i) { loc.push_back({i,right}); nums.push_back(matrix[i][right]); } for(int iright-1;ileft;i--) { loc.push_back({right,i}); nums.push_back(matrix[right][i]); } for(int iright-1;ileft1;i--) { loc.push_back({i,left}); nums.push_back(matrix[i][left]); } left,right--; } for(int i0,jn-1;in*n;i,j) { if(jnums.size()) j-nums.size(); int val nums[i]; pairint,int xyloc[j]; matrix[xy.first][xy.second]val; } } };解法2公式顺时针旋转90°的公式为[ x , y ] ------- [ y , n-1-x ]解法3翻转替代旋转