难度说明：🟢简单🟡中等🔴困难

hot150-04-矩阵

🟡01-有效的数独（36）

1.题目内容

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

2.题解思路

👻方法1：遍历法（标记校验）

• 思路分析：根据规则进行校验，定义3个二维数组用于存储某个区域位置数字是否出现过

  • 初始化3个二维数组，用于存储当前number是否已出现过
    • 例如boolean[][] rowFlag = new boolean[9][10]：其中行表示对应行，列表示对应数字

/**
 * 036 有效的数独
 */
public class Solution1 {
    /**
     * 标记法：3个二维数组用于判断对应位置是否已经出现过该数字
     * 1.数独是9*9表格，因此在遍历的过程中可以将数独的数字和对应矩阵的下标进行对照
     * 2.借助数组存储指定位置上数字是否出现过的标记
     * - 1-9 在每行只能出现一次
     * - 1-9 在每列只能出现一次
     * - 1-9 在每个9宫格只能出现一次
     */
    public boolean isValidSudoku(char[][] board) {

        // 定义哈希表存储数字出现的标记
        boolean[][] rowFlag = new boolean[9][10]; // 表示某一行的每个数是否出现过，取下标1-9的位置操作
        boolean[][] colFlag = new boolean[9][10]; // 表示某一列的每个数是否出现过，取下标1-9的位置操作
        boolean[][] boxFlag = new boolean[9][10]; // 表示某个box的每个数是否出现过，取下标1-9的位置操作

        // 遍历矩阵元素，依次进行判断
        int m = board.length, n = board[0].length;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 判断某行某列的对应元素在相应的区域内是否已经出现过
                if (board[i][j] == '.') {
                    continue; // '.' 表示待填充区域跳过当次判断
                }
                // 将对应数字字符串转化为int类型
                int curNumber = board[i][j] - '0';
                // 将数字与对应的哈希表存储位置对照
                if (rowFlag[i][curNumber]) { // 校验规则1：判断行
                    return false; // 表示第i行的当前数字已经出现过，直接返回false
                } else {
                    rowFlag[i][curNumber] = true; // 未出现过，则进行标记
                }

                if (colFlag[j][curNumber]) { // 校验规则2：判断列
                    return false; // 表示第j列的当前数字已经出现过，直接返回false
                } else {
                    colFlag[j][curNumber] = true; // 未出现过，则进行标记
                }

                if (boxFlag[j / 3 + (i / 3) * 3][curNumber]) {
                    return false; // 表示对应box的当前数字已经出现过，直接返回false
                } else {
                    boxFlag[j / 3 + (i / 3) * 3][curNumber] = true; // 未出现过，则进行标记
                }
            }
        }
        return true;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

代码结构优化：将判断放在前列，不满足则直接返回false，因此对于当前元素，三个规则校验都通过之后再进行标记也可以，消除if...else...语句

public class Solution2 {
    /**
     * 标记法：3个二维数组用于判断对应位置是否已经出现过该数字
     * 1.数独是9*9表格，因此在遍历的过程中可以将数独的数字和对应矩阵的下标进行对照
     * 2.借助数组存储指定位置上数字是否出现过的标记
     * - 1-9 在每行只能出现一次
     * - 1-9 在每列只能出现一次
     * - 1-9 在每个9宫格只能出现一次
     */
    public boolean isValidSudoku(char[][] board) {

        // 定义哈希表存储数字出现的标记
        boolean[][] rowFlag = new boolean[9][10]; // 表示某一行的每个数是否出现过，取下标1-9的位置操作
        boolean[][] colFlag = new boolean[9][10]; // 表示某一列的每个数是否出现过，取下标1-9的位置操作
        boolean[][] boxFlag = new boolean[9][10]; // 表示某个box的每个数是否出现过，取下标1-9的位置操作

        // 遍历矩阵元素，依次进行判断
        int m = board.length, n = board[0].length;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 判断某行某列的对应元素在相应的区域内是否已经出现过
                if (board[i][j] == '.') {
                    continue; // '.' 表示待填充区域跳过当次判断
                }
                // 将对应数字字符串转化为int类型
                int curNumber = board[i][j] - '0';
                // 将数字与对应的哈希表存储位置对照
                if (rowFlag[i][curNumber]) { // 校验规则1：判断行
                    return false; // 表示第i行的当前数字已经出现过，直接返回false
                }
                if (colFlag[j][curNumber]) { // 校验规则2：判断列
                    return false; // 表示第j列的当前数字已经出现过，直接返回false
                }
                if (boxFlag[j / 3 + (i / 3) * 3][curNumber]) {
                    return false; // 表示对应box的当前数字已经出现过，直接返回false
                }

                // 统一标记
                rowFlag[i][curNumber] = true; // 未出现过，则进行标记
                colFlag[j][curNumber] = true; // 未出现过，则进行标记
                boxFlag[j / 3 + (i / 3) * 3][curNumber] = true; // 未出现过，则进行标记
            }
        }
        return true;
    }

}

🟡02-螺旋矩阵（54）

1.题目内容

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

2.题解思路

👻方法1：四指针循环遍历

• 思路分析
  • 定义4个指针，分别用作指针边界，当遍历完一行就进行缩边，指针相遇则遍历结束（左右指针、上下指针都相遇则遍历结束）
  • 遍历顺序：从左到右（遍历top行）、从上到下（遍历right行）、从右到左（遍历bottom行）、从下到上（遍历left行）
  • 每遍历完一行，则对应行缩边（即向中间走，例如left++；right--；bottom--；top++），遍历过程中注意行和列的变化（不要死记硬背）
    • 例如遍历top行，则top是不变的（即行不变、列变），即加入的元素是arr[top][i]，该行遍历完成后则top++
    • 例如遍历right列，则right是不变的（即行变、列不变），即加入的元素是arr[i][right]，以此类推
    • 还需因为m、n并不是等长的（即矩阵有可能并不是正方形的），因此遍历过程中还需判断内部遍历是否某个边界提前相遇了，如果是则限制

/**
 * 螺旋矩阵
 */
public class Solution1 {
    /**
     * 螺旋矩阵：顺时针螺旋顺序，遍历矩阵元素
     * 通过4个指针进行控制（设定边界），到达边界则切换方向并进行缩边
     */
    public List<Integer> spiralOrder(int[][] matrix) {

        // 定义返回结果，封装遍历元素
        List<Integer> list = new ArrayList<>();

        // 获取矩阵属性
        int m = matrix.length;
        int n = matrix[0].length;

        // 定义4个指针边界
        int left = 0, right = n - 1, top = 0, bottom = m - 1;

        // 按照指定方向次序遍历元素(指针相遇则遍历结束)
        while (left <= right && top <= bottom) {
            // 从左往右遍历
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            top++; // top 缩边

            // 从上往下遍历
            for (int i = top; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            right--; // right 缩边

            // 从右往左遍历
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    list.add(matrix[bottom][i]);
                }
                bottom--; // bottom 缩边
            }

            // 从下往上遍历
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    list.add(matrix[i][left]);
                }
                left++; // left 缩边
            }
        }

        return list;
    }
}

• 复杂度分析

  • 时间复杂度：O（m×n）（m n 分别是矩阵的行数和列数），矩阵中的每个元素都要被访问一次

  • 空间复杂度：O（1）

🟡03-旋转图像（48）

1.题目内容

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

2.题解思路

👻方法1：旋转规律法（❌）

由于题目本意是希望使用原地算法，不可以借助额外的矩阵来旋转，因此这种思路仅作参考，非标答

• 思路分析
  • 观察旋转规律，发现旋转的结果可以理解为就将每一行转为对应的列（例如第1行旋转后就是对应在第1列，以此类推）
    • 即matrix[row][col]旋转后的对应位置为：matrix[col][n-row-1]
  • 基于旋转规律，则可构建一个辅助矩阵依次存放旋转后的元素信息，随后将这个旋转后的辅助矩阵copy到原矩阵

/**
 * 048 旋转图像
 */
public class Solution1 {
    /**
     * 借助辅助矩阵存储旋转后的元素
     * - matrix[row][col]旋转后对应位置为matrix[col][n-row-1]
     * - 旋转矩阵规格都是n*n
     */
    public void rotate(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int[][] temp = new int[m][n];
        // 遍历矩阵元素，将元素与旋转后的位置对照
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                temp[j][n-i-1] = matrix[i][j];
            }
        }

        // 再次遍历旋转后的矩阵元素，覆盖对应位置
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                matrix[i][j] = temp[i][j];
            }
        }
    }
}

• 复杂度分析

  • 时间复杂度：O（n²）n 矩阵规格

  • 空间复杂度：O（n²）n 矩阵规格

👻方法2：原地旋转（🟡）：旋转位置变换规律+旋转范围

​ 基于方法1分析，之所以要引入矩阵存储旋转后的元素，是由于旋转的规律限制（旋转后会覆盖原来位置的记录，因此会打乱原有矩阵）。为了避免旋转后打断原有矩阵的规则，需进一步拆解，如果存储才能去除这种影响。于是考虑借助临时变量temp存储数据，避免结果直接被覆盖

• 原地旋转矩阵的规律

• （1）旋转等式：matrix[row][col]=》matrix[col][n-row-1]

• （2）如果直接旋转会导致matrix[col][n-row-1]元素被覆盖，因此需要考虑用临时变量存储matrix[col][n-row-1]的值，进一步拆解等式

  • temp=matrix[col][n-row-1]
  • matrix[col][n-row-1]=matrix[row][col]

• （3）继续思考matrix[col][n-row-1]旋转后会到哪个位置，还是使用方法1的关键等式，不过此处需要代入

  • 代入等式：将row=col、col=n-row-1这两个关键等式代入旋转等式matrix[col][n-row-1]=matrix[row][col]（即将row、col分别用相应的等式替换）
  • 得到matrix[n-row-1][n-col-1]=matrix[col][n-row-1]
  • 同样需要借助临时变量存储，因此等式会被扩展为：
    • temp=matrix[n-row-1][n-col-1]
    • matrix[n-row-1][n-col-1]=matrix[col][n-row-1]
    • matrix[col][n-row-1]=matrix[row][col]

• （4）再重复一次步骤（3）操作，看matrix[n-row-1][n-col-1]会存到什么位置：

  • 代入等式得到：matrix[n-col-1][row]，类似地继续扩展等式
    • temp=matrix[n-col-1][row]
    • matrix[n-col-1][row]=matrix[n-row-1][n-col-1]
    • matrix[n-row-1][n-col-1]=matrix[col][n-row-1]
    • matrix[col][n-row-1]=matrix[row][col]

• （5）继续重复步骤（3），看matrix[n-col-1][row]会存到什么位置：

  • 代入等式得到：matrix[row][col]，可以看到这个位置实际上就是原旋转元素所在位置，那么基于此，旋转规律可以最终扩展为：
    • temp=matrix[row][col]
    • matrix[row][col]=matrix[n-col-1][row]
    • matrix[n-col-1][row]=matrix[n-row-1][n-col-1]
    • matrix[n-row-1][n-col-1]=matrix[col][n-row-1]
    • matrix[col][n-row-1]=matrix[row][col]

• 原地旋转范围：row（0-m/2）、col（0-(n+1)/2）

  • 原地旋转范围的思考可以举例理解分析

    • n 为偶数：需要枚举n²/4=（n/2）×（n/2）个位置（将矩阵分为4块）

    • n 为奇数：中心位置经过旋转后位置不变，因此需要枚举的位置是(n²−1)/4=((n−1)/2)×((n+1)/2)个位置

      

/**
 * 048 旋转图像
 */
public class Solution2 {
    /**
     * 原地旋转法：寻找原地旋转规律
     */
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        // 遍历矩阵元素进行原地旋转
        for (int row = 0; row < m / 2; row++) {
            for (int col = 0; col < (n + 1) / 2; col++) {
                /**
                 * 旋转规律算法：核心等式（row=col，col=n-row-1）,依次分析每个元素旋转后会覆盖到哪个位置
                 * 【1】matrix[row][col]
                 * 【2】matrix[col][n-row-1]
                 * 【3】matrix[n-row-1][n-col-1]
                 * 【4】matrix[n-col-1][row]
                 * 【5】matrix[row][col]
                 * 可以看到元素的一个旋转路线，则可通过临时变量temp存储，然后从下往上依次覆盖
                 */
                int temp = matrix[row][col];
                matrix[row][col] = matrix[n - col - 1][row];
                matrix[n - col - 1][row] = matrix[n - row - 1][n - col - 1];
                matrix[n - row - 1][n - col - 1] = matrix[col][n - row - 1];
                matrix[col][n - row - 1] = temp;
            }
        }

    }
}

• 复杂度分析

  • 时间复杂度：O（n²）n 矩阵规格（枚举的子矩阵大小为 O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N*N)）

  • 空间复杂度：O（1）（原地旋转）

👻方法3：翻转法（🟢）水平翻转+主对角线翻转

• 思路分析（用反转代替旋转操作：旋转=通过水平轴翻转+通过主对角线翻转）
  • 水平翻转规律：matrix[row][col]=》matrix[n-row-1][col]（x轴相反、y轴不变）
  • 主对角线翻转规律：matrix[row][col]=》matrix[col][row]（x和y对调）
  • 整体执行分析：matrix[row][col]=水平翻转=》matrix[n-row-1][col]=主对角线翻转=》matrix[col][n-row-1]，可以看到和方法1中得到的关键等式是一致的，但是此处每次枚举只需要枚举一半的元素即可

public class Solution3 {
    /**
     * 原地旋转法：寻找原地旋转规律
     */
    public void rotate(int[][] matrix) {
        // 因为矩阵是正方形的，此处只需取一个长度
        int n = matrix.length;

        /**
         * 基于翻转的思路：水平翻转+对角线翻转（基于翻转思路可以交换元素，而不用像方法2那样绕圈圈考虑元素覆盖规律）
         * 1.水平翻转：matrix[row][col] => matrix[n-row-1]][col] (x翻转，y不变)
         * 2.对角线翻转：matrix[row][col] => matrix[col][row] (x、y对调)
         */
        // 1.进行水平翻转(翻转范围：翻转上面一半的位置)
        for (int i = 0; i < n / 2; i++) { // 限定水平线
            for (int j = 0; j < n; j++) {
                // 翻转元素（交换）
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }

        // 2.进行对角线翻转(翻转范围：主对角线一半的位置)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) { // 限定主对角线
                // 翻转元素（交换）
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

• 复杂度分析

  • 时间复杂度：O（n²）n 矩阵规格（涉及2次矩阵遍历，每次翻转只需要枚举矩阵中一半的元素，因此相当于一次完整的矩阵遍历）

  • 空间复杂度：O（1）（原地旋转）

🟡04-矩阵置零（73）

1.题目内容

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

2.题解思路

👻方法1：标记法（双数组）

/**
 * 073 矩阵置0
 */
public class Solution1 {
    /**
     * 标记法：遍历矩阵，将元素为0的数据所在行、列进行标记
     */
    public void setZeroes(int[][] matrix) {
        // 获取矩阵属性
        int m = matrix.length,n = matrix[0].length;
        // 定义两个数组分别存储矩阵元素对应行列的标记
        boolean[] row = new boolean[m];
        boolean[] 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;
                }
            }
        }
    }
}

• 复杂度分析

  • 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。至多只需要遍历该矩阵两次

  • 空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。需要分别记录每一行或每一列是否有零出现

🟡05-生命游戏（289）

1.题目内容

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

2.题解思路

👻方法1：copy原数组模拟（外层填充0，内层更新状态）

​ 思路：外层填充0，下一个状态只受到周围数字1的影响，用count记录周围1的数量，然后进行更新

​ 此处需注意：细胞的出生和死亡是同时发生的，因此无法通过先更新某些格子然后根据这些更新后的格子状态再更新其他格子，是要保持同时更新

​ 也就是说，更新后的格子状态会联动影响到其他格子的状态，但题目的本意是要以原来的格子状态为参考，因此不能够边更新边判断，因此采用copy一份矩阵的思路，更新后的矩阵填充到新矩阵，所有的更新态都以原矩阵为参考进行判断，因此就不会受到"更新"的影响

​ 规则分析：

                            原本活（1）                                原本死（0）
----------------------------------------------------------------------------------------------------------
周围活的数量 < 2          1 -> 0                                      0 -> 0（状态未变，不用管了）          
----------------------------------------------------------------------------------------------------------
周围活的数量 = 2          1 -> 1（状态未变，不用管了)                   0 -> 0（状态未变，不用管了）          
----------------------------------------------------------------------------------------------------------
周围活的数量 = 3          1 -> 1（状态未变，不用管了）                  0 -> 1
----------------------------------------------------------------------------------------------------------
周围活的数量 > 3          1 -> 0                                      0 -> 0（状态未变，不用管了）          

• 思路分析
  • （1）定义tempBoard：外层填充0，内层填充源board矩阵元素
  • （2）tempBoard遍历、board更新：以tempBoard矩阵遍历为参考，将其作为细胞存活状态参考副本，对board矩阵进行更新
    • 统计tempBoard[i][j](范围：[1-m],[1-n])周围8个细胞的存活数量
    • 根据规则更新board[i-1][j-1](因为 tempBoard 是外层填充了0的，因此此处对照的 board 位置是[i-1][j-1])
      • 此处的更新规则有两条限制：细胞原来的存活状态、细胞原来周围的细胞存活数量影响

public class Solution1 {
    /**
     * 思路：copy一份数组进行模拟更新
     */
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

        // 构建一个新矩阵（外层填充0，内层存储元素）：因为只有活细胞数量才会对细胞状态有影响，因此周边填充0
        int[][] tempBoard = new int[m+2][n+2];
        for (int i = 0; i < m + 2; i++) {
            Arrays.fill(tempBoard[i], 0);
        }

        // 填充内存元素（对应tempBoard[1-m][1-n]范围数据）
        for (int i = 0; i < m; i++) {
            /*
            for (int j = 0; j < n; j++) {
                tempBoard[i+1][j+1] = board[i][j];
            }
             */
            System.arraycopy(board[i], 0, tempBoard[i + 1], 1, n); // 内层对照填充元素
        }

        // 根据规则更新细胞存活状态：计算每个元素位置周围8个格子的细胞存活数量
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 判断当前newBoard对应位置细胞存活状态，更新源矩阵
                int aliveCount = 0;
                // 统计当前细胞周围8个位置的活细胞数量
                aliveCount = tempBoard[i - 1][j - 1] + tempBoard[i - 1][j] + tempBoard[i - 1][j + 1]
                        + tempBoard[i][j - 1] + tempBoard[i][j + 1]
                        + +tempBoard[i + 1][j - 1] + tempBoard[i + 1][j] + tempBoard[i + 1][j + 1];
                // 根据规则判断存活状态，然后进行更新
                if (tempBoard[i][j] == 1 && aliveCount < 2) {
                    board[i-1][j-1] = 0;
                } else if (tempBoard[i][j] == 1 && ( aliveCount == 2 || aliveCount == 3)) {
                    board[i-1][j-1] = 1;
                } else if (tempBoard[i][j] == 1 &&  aliveCount > 3) {
                    board[i-1][j-1] = 0;
                } else if (tempBoard[i][j] == 0 && aliveCount == 3) {
                    board[i-1][j-1] = 1;
                }
            }
        }
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：