Leetcode热题100中的：矩阵专题
矩阵框架
1.坐标变换型
- 旋转，翻转，变换
2.按圈遍历型
- 螺旋，顺时针，按层遍历
3.原地标记型
- 整行整列修改，传播，标记
4.单调矩阵搜索型
- 行递增，列递增，搜索
5.矩阵DP / 面积型
73.矩阵置零(原地标记型)
关键信息一句话总结：
将第一行和第一列作为标志数组，标记置零，最后自己也变成0
- 方法1：利用标记数组
classSolution{publicvoidsetZeroes(int[][]matrix){// 双数组标记法intn=matrix.length;intm=matrix[0].length;boolean[]row=newboolean[n];boolean[]col=newboolean[m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(matrix[i][j]==0){row[i]=true;col[j]=true;}}}for(inti=0;i<n;i++){for(intj=0;j<m;j++){// 只要第j列或者第i行需要清零 该位置才是0if(row[i]||col[j]){matrix[i][j]=0;}}}}}- 方法2：优化第一行和第一列作为标志数组
classSolution{publicvoidsetZeroes(int[][]matrix){// 优化思路:将标志数组放进第一行和第一列intn=matrix.length;intm=matrix[0].length;booleanfirstRow=false;booleanfirstCol=false;// 1.先检测第一行是否有0 我们后面再处理for(intj=0;j<m;j++){if(matrix[0][j]==0){firstRow=true;break;}}// 2.再检测第一列是否有0 我们后面再处理for(inti=0;i<n;i++){if(matrix[i][0]==0){firstCol=true;break;}}// 3.开始标记for(inti=1;i<n;i++){for(intj=1;j<m;j++){if(matrix[i][j]==0){matrix[0][j]=0;matrix[i][0]=0;}}}// 4.开始填0for(inti=1;i<n;i++){for(intj=1;j<m;j++){if(matrix[0][j]==0||matrix[i][0]==0){matrix[i][j]=0;}}}// 5.第一行和第一列清零if(firstRow){for(intj=0;j<m;j++){matrix[0][j]=0;}}if(firstCol){for(inti=0;i<n;i++){matrix[i][0]=0;}}}}- 反思：我没有想到矩阵的第一列和第一行能够作为标志数组进行优化
54.螺旋矩阵(按圈遍历型)
关键信息一句话总结：
利用四边界，将边界进行收缩
- 方法1：利用%进行方向判断，用isVisited标志数组判断访问
classSolution{publicList<Integer>spiralOrder(int[][]matrix){List<Integer>result=newArrayList<>();intn=matrix.length;intm=matrix[0].length;boolean[][]isVisited=newboolean[n][m];// dx: 右0 下+1 左0 上-1int[]dx=newint[]{0,1,0,-1};// dy: 右+1 下0 左-1 上0int[]dy=newint[]{1,0,-1,0};intx=0;inty=0;// 当前方向 0表示右intdir=0;for(inti=0;i<n*m;i++){result.add(matrix[x][y]);isVisited[x][y]=true;intnx=x+dx[dir];intny=y+dy[dir];if(nx<0||nx>=n||ny<0||ny>=m||isVisited[nx][ny]){// 转换方向dir=(dir+1)%4;}// 移动坐标x+=dx[dir];y+=dy[dir];}returnresult;}}- 方法2：优化思路：利用边界收缩来替换方向判断
classSolution{publicList<Integer>spiralOrder(int[][]matrix){// 四边界法: 优化思路：判断下一个元素是否访问过用 + 方向如何判断// 用四个边界来进行按要求访问 通过收缩边界来进行访问元素List<Integer>result=newArrayList<>();inttop=0;intbottom=matrix.length-1;intleft=0;intright=matrix[0].length-1;while(top<=bottom&&left<=right){// ->rightfor(intj=left;j<=right;j++){result.add(matrix[top][j]);}top++;// ->downfor(inti=top;i<=bottom;i++){result.add(matrix[i][right]);}right--;// ->leftif(top<=bottom){for(intj=right;j>=left;j--){result.add(matrix[bottom][j]);}bottom--;}// ->upif(left<=right){for(inti=bottom;i>=top;i--){result.add(matrix[i][left]);}left++;}}returnresult;}}- 反思：我没有想到四边界收缩法，可以利用边界收缩来对应优化方向判断和访问记录
48.旋转图像(坐标变换型)
关键信息一句话总结：
转置 + 每一行逆序 模拟 顺时针90°旋转
classSolution{publicvoidrotate(int[][]matrix){intn=matrix.length;// (i , j) → (j , n-1-i)// 1.对角线转置for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){inttemp=matrix[i][j];matrix[i][j]=matrix[j][i];matrix[j][i]=temp;}}// 2.每一行倒置for(inti=0;i<n;i++){// 3.双指针倒置intleft=0;intright=n-1;while(left<right){inttemp=matrix[i][left];matrix[i][left]=matrix[i][right];matrix[i][right]=temp;left++;right--;}}}}- 反思：我没有观察出来坐标的变化
240.搜索二维矩阵II(单调矩阵搜索型)
关键信息一句话总结：
右上角开始搜索，右上角的特征是左小下大，收缩搜索范围
classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 从右上角开始 因为左边都小 下边都大intn=matrix.length;intm=matrix[0].length;intx=0;inty=m-1;while(x<n&&y>=0){if(target==matrix[x][y]){returntrue;}if(matrix[x][y]>target){y--;}else{x++;}}returnfalse;}}- 反思：我没有观察出来右上角的特征