LeetCode Hot100 - 矩阵篇

前言

        刷力扣hot100，记录一下每题的思路~

        这次是矩阵相关的题目

（1）73. 矩阵置零

①两个boolean数组记录要置零的行列号，遍历数组置零对应的行列

class Solution {
    public void setZeroes(int[][] matrix) {
        int m=matrix.length, n=matrix[0].length;
        // 记录要置零的行列号
        boolean[] row=new boolean[m], col=new boolean[n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0){
                    row[i]=true;
                    col[j]=true;
                }
            }
        }
        // 将对应行列置零
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(row[i]||col[j])matrix[i][j]=0;
            }
        }
    }
}

②第一行第一列记录对应行列是否要置零。

        [0][0]同时代表行列，不能直接置零，使用两个boolean单独记录。

        先遍历矩阵修改对应第一行第一列，置零除第一行第一列（标志位用于后续判断）的元素，再根据boolean处理第一行第一列

class Solution {
    public void setZeroes(int[][] matrix) {
        int m=matrix.length, n=matrix[0].length;
        // [0][0]同时代表行列，不能直接置零，单独处理
        boolean row0=false, col0=false;
        for(int j=0;j<n;j++)if(matrix[0][j]==0){row0=true;break;}
        for(int i=0;i<m;i++)if(matrix[i][0]==0){col0=true;break;}
        // 要置零的行列号
        for(int i=1;i<m;i++){ 
            for(int j=1;j<n;j++){
                if(matrix[i][j]==0)
                    matrix[i][0]=matrix[0][j]=0;
            }
        }
        // 第一行第一列先不置零
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
            }
        }
        // 处理第一行第一列
        if(row0) for(int j=0;j<n;j++) matrix[0][j]=0; // 第一行
        if(col0) for(int i=0;i<m;i++) matrix[i][0]=0; // 第一列
    }
}

③同上，令[0][0]只标志第一行，单独用col0标志第一列。

        先遍历矩阵，根据第一列元素更改col0，其他元素更改对应第一行第一列；置零除第一行第一列（标志位用于后续判断）的元素，再根据[0][0]和col0处理第一行第一列

④同上，置零逆序处理行，将第一行标志位最后处理，则不用单独判断第一行

class Solution {
    public void setZeroes(int[][] matrix) {
        int m=matrix.length, n=matrix[0].length;
        // 令[0][0]单独标志第一行，用col0标志第一列
        boolean col0=false;
        for(int i=0;i<m;i++){
            if(matrix[i][0]==0) col0=true; // 处理第一列
            for(int j=1;j<n;j++){ // 处理除第一列外的数
                if(matrix[i][j]==0)
                    matrix[i][0]=matrix[0][j]=0;
            }
        }
        // 第一列先不置零
        for(int i=m-1;i>=0;i--){ // 第一行标志位最后处理
            for(int j=1;j<n;j++){
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
            }
        }
        // 处理第一列
        if(col0) for(int i=0;i<m;i++) matrix[i][0]=0; // 第一列
    }
}

（2）54. 螺旋矩阵

①模拟。设定方向数组和下标，并用矩阵记录每个位置是否访问。

        遍历m*n次，计算下一跳不合法就更新方向下标，再进行下一跳

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m=matrix.length, n=matrix[0].length; // 行列
        int[][] dir={{0,1},{1,0},{0,-1},{-1,0}}; // 方向矩阵
        int x=0, y=0, dirIdx=0; // 当前位置、方向下标
        boolean[][] flag = new boolean[m][n]; // 是否已访问
        for(int i=0;i<m*n;i++){ // 每个数
            ans.add(matrix[x][y]); // 添加
            flag[x][y]=true;
            // 下个位置是否合法
            int x1=x+dir[dirIdx][0], y1=y+dir[dirIdx][1];
            if(x1<0||x1>=m || y1<0||y1>=n || flag[x1][y1])
                dirIdx=(dirIdx+1)%4;
            // 更新位置
            x+=dir[dirIdx][0];
            y+=dir[dirIdx][1];
        }
        return ans;
    }
}

②按层模拟。

        lrtb记录每层的上下左右，四个for循环遍历每边，前两个for循环之后修改了t和r，后两个for循环要重新判断是否满足t<=b和l<=r，判断上下或者左右是否已走完

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m=matrix.length, n=matrix[0].length; // 行列
        int l=0, r=n-1, t=0, b=m-1; // 上下左右范围
        while(l<=r&&t<=b){
            for(int j=l; j<=r; j++)ans.add(matrix[t][j]); // 左到右
            t++;
            for(int i=t; i<=b; i++)ans.add(matrix[i][r]); // 上到下
            r--;
            if(t<=b) // 判断是否上下走完了
                for(int j=r; j>=l; j--)ans.add(matrix[b][j]); // 右到左
            b--;
            if(l<=r) // 判断左右是否走完了
                for(int i=b; i>=t; i--)ans.add(matrix[i][l]); // 下到上
            l++;
        }
        return ans;
    }
}

③同上，在每个for循环后判断边界是否合法，不合法就break，便于理解

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m=matrix.length, n=matrix[0].length; // 行列
        int l=0, r=n-1, t=0, b=m-1; // 上下左右范围
        while(l<=r&&t<=b){
            for(int j=l; j<=r; j++)ans.add(matrix[t][j]); // 左到右
            if(++t>b) break;
            for(int i=t; i<=b; i++)ans.add(matrix[i][r]); // 上到下
            if(--r<l) break;
            for(int j=r; j>=l; j--)ans.add(matrix[b][j]); // 右到左
            if(--b<t) break;
            for(int i=b; i>=t; i--)ans.add(matrix[i][l]); // 下到上
            if(++l>r) break;
        }
        return ans;
    }
}

（3）48. 旋转图像

①暴力。每次旋转包含四个数，从左上角开始遍历四分之一的位置，逆时针替换，计算每个替换值的位置，只需要记录一个变量

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 左上角
        for(int i=0;i<n/2;i++){
            for(int j=0;j<(n+1)/2;j++){
                // 逆时针修改
                int temp = matrix[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;
            }
        }
    }
}

②暴力，总结下一跳位置规律，对于每个位置i,j顺时针旋转到j,n-i-1。但是逆时针替换只需要一个变量，对于每个位置i,j用n-j-1,i的位置替换，最后一个替换单独处理

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i<n/2;i++){
            for(int j=0;j<(n+1)/2;j++){
                int x=i, y=j, temp=matrix[x][y];
                for(int k=0;k<3;k++){ // 逆时针
                    int nextX=n-y-1, nextY=x; // 下一跳规律
                    matrix[x][y]=matrix[nextX][nextY];
                    x=nextX; y=nextY;
                }
                matrix[x][y]=temp; // 最后一个单独处理
            }
        }
    }
}

③暴力，利用辅助数组逐个旋转，最后替换原数组的值，位置i,j旋转到j,n-i-1

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] newMatrix = new int[n][n]; // 辅助数组
        for(int i=0;i<n;i++){ // 旋转
            for(int j=0;j<n;j++){
                newMatrix[j][n-i-1]=matrix[i][j];
            }
        }
        for(int i=0;i<n;i++){ // 替换
            for(int j=0;j<n;j++){
                matrix[i][j]=newMatrix[i][j];
            }
        }
    }
}

④翻转，先转置为j,i，再左右对称翻转j,n-i-1

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length, temp = 0;
        for(int i=0;i<n;i++){ // 转置，j,i
            for(int j=0;j<i;j++){ // 下三角
                temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
        for(int i=0;i<n;i++){ // 左右对称翻转，j,n-i-1
            for(int j=0;j<n/2;j++){ // 左半部分
                temp=matrix[i][j];
                matrix[i][j]=matrix[i][n-j-1];
                matrix[i][n-j-1]=temp;
            }
        }
    }
}

（4）240. 搜索二维矩阵 II

①暴力，遍历判断

②递归，从对角线开始判断，找到对角线中第一个大于等于target的值，若相等则找到，若大于target，判断左下和右上区域

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length, n=matrix[0].length; // m行n列
        return check(matrix,0,m-1,0,n-1,target);
    }

    boolean check(int[][] matrix,int t,int b,int l,int r,int target){
        if(t>b||l>r)return false; // 区域不存在
        if(t==b&&l==r)return matrix[t][l]==target; // 一个元素
        // 对角线
        int i=t,j=l;
        for(;i<=b&&j<=r;i++,j++) if(matrix[i][j]>=target)break;
        if(i<=b&&j<=r&&matrix[i][j]==target)return true; // 在对角线上
        // 左下和右上
        return check(matrix,i,b,l,j-1,target)||check(matrix,t,i-1,j,r,target);
    }
}

③二分查找，对每行进行二分查找

④右上角，为一行最大和一列最小。若大于target，该列都大于target，y--；若小于target，该行都小于target，x++。直到找到。（类似从左下角开始也可以，条件反过来）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length, n=matrix[0].length;
        int x=0,y=n-1; // 右上角开始
        while(x<m&&y>=0){
            if(matrix[x][y]==target)return true; // 找到
            if(matrix[x][y]>target)y--; // y这列都大于target
            else x++; // x这行都小于target
        }
        return false;
    }
}

总结

        ①矩阵置零。使用第一行第一列来标记每行每列，注意特别判断[0][0]位置

        ②螺旋矩阵。用方向数组和下标模拟旋转；按层遍历，用lrtp记录上下左右要遍历的层，要注意判断边界是否合法

        ③旋转矩阵。总结旋转规律，i,j旋转到j,n-i-1，逆时针替换只需要记录一个变量；先转置为j,i，再左右翻转为j,n-i-1

        ④搜索二维矩阵Ⅱ。暴力遍历；递归，从对角线开始判断，划分四个区域，递归左下和右上；对每行用二分查找；利用右上或者左下的特殊性，每次收缩一行或一列。