当前位置： 首页 > article >正文

【LeetCode 面试经典150题】详细题解之矩阵篇

article 2025/1/3 20:09:13

【LeetCode 面试经典150题】详细题解之矩阵篇

  • 1 矩阵的基础
    • 1.1 表示矩阵
    • 1.2 创建矩阵
    • 相关题目
  • 2 36.有效的数独 （需要复习）
    • 分析
    • 代码
  • 3 54.螺旋矩阵（需要复习）
    • 分析
    • 代码
  • 4 48.旋转图像
    • 思路
    • 代码
  • 5 73.矩阵置零 （一遍过）
    • 5.1 思路
    • 5.2 代码
  • 6 289.生命游戏 （一遍过）
    • 分析
    • 代码

1 矩阵的基础

感觉矩阵的题很简单。迅速过完

12.23 一刷

1.1 表示矩阵

在Java中，矩阵通常可以用二维数组（int[][]、double[][]等）来表示。每个内部数组代表矩阵的一行。

int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

1.2 创建矩阵

创建矩阵可以通过直接声明和初始化，或者使用循环动态创建。

int rows = 3;
int columns = 3;
int[][] matrix = new int[rows][columns];
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
        matrix[i][j] = i * columns + j;
    }
}

相关题目

36.有效的数独 （看题解做出来，需要复习）

54.螺旋矩阵（做了一次没做对，需要复习）

48.旋转图像（一遍过）

73.矩阵置零 （一遍过）

289.生命游戏 （一遍过）

2 36.有效的数独 （需要复习）

36. 有效的数独

中等

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

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

注意：

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

示例 1：

img

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

分析

题目不难。做的时候没想到的是

  1. 没有想到如何判断3*3宫格。（可以用两个坐标来表示9个3*3宫格）
  2. 用数组代替hash表存储该行/该列/该3*3宫格是否出现该数字
        不用完成数独，但是需要判断给出的数独是否是合法数独。核心思想如下：
        1.每行每列每个九宫格均使用一个hash来存储，以此判断该行该列该九宫格是否出现重复数字
        
        具体实现注意以下几点
            （1）可以使用数组代替hash，每行每列都使用一个大小为9*10的二维数组row[9][10] ,col[9][10]来代表hash表，此外，对于九宫格，则使用一个3*3*10维的,subboard[3][3][10]
            row[i][num]:代表第i行出现数字num+1的次数
            col[j][num]:代表第j列出现数字num+1的次数
            subboard[i][j][num]:代表第[i,j]个九宫格中出现数字 num+1的次数
            举个例子，board[i][j]=num,那么，可以用row[i][num-1]++,col[j][num-1]++来表示该行该列出现了数字num
            （2）如何将位置board中的位置映射到对应的九宫格中
            之前纠结于如何判断属于哪个九宫格，认为一共需要9个数来代表9宫格。
        看题解后发现可以用两个数来代表九宫格
        这样一共九个九宫格可以表述如下
        [0,0] [0,1] [0,2]
        [1,0] [1,1] [1,2]
        [2,0] [2,1] [2,2]
        与之对应的，举个例子 [0,0]九宫格中的数的i∈[0,2],j∈[0,2] 
        [0,1]:i∈[0,2],j∈[3,5] 
        [0,2]:i∈[0,2],j∈[6,8]
        可以看到，对于任意坐标(i,j)他会属于[i/3,j/3]九宫格

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {

        //1.初始化数组存储每行每列每个九宫格出现的数字
        int[][] row = new int[9][10];
        int[][] col = new int[9][10];
        int[][][] subboard = new int[3][3][10];

        //2.遍历board中的每个元素
        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j]=='.')continue;
                //2.1 遍历时，将该元素加入1中初始化的数组中，判断结果是否>1,是的话直接返回false
                int num = board[i][j]-'0';
                row[i][num-1]++;
                col[j][num-1]++;
                subboard[i/3][j/3][num-1]++;
                if(row[i][num-1]>1 || col[j][num-1]>1 || subboard[i/3][j/3][num-1]>1){
                    return false;
                }
            }
        }
        return true;
        

    }

}

3 54.螺旋矩阵（需要复习）

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

示例 1：

img

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

输入：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.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

分析

之前做过很多次。但是再做仍然会出现问题。具体是一些细节上的问题。

这次做能够知道3，4需要判断当前行是否遍历过，当前列是否遍历过

但是没有注意到的点为

  1. 举个例子，往右的时候需要初始化当前列，即j=left。就是在往一个方向遍历移动的时候，需要初始化最开始移动的那个下标。

    第一次做的时候，里面的移动用的是for循环，而不是while，所以使用while来遍历的话，就需要在遍历的一开始指定j

                j = left;
            while(j<right){
                res.add(matrix[top][j]);
                j++;
                num++;
            }
            top++;

        模拟。
        用四个指针作为边界，分别为top，bottom，left，right作为上下左右的边界[top,bottom),[left,right)
        i，j则指向当前元素

        具体而言
        1.j<right的时候，往右，到右边界时，top++,往下
        2.i<bottom的时候，往下，到下边界时，right--,往左
        3.j>=left的时候，往左，到左边界时，bottom--,往上。
        4.i>=top的时候，往上，到上边界时，left++,继续重复1-4的步骤

        注意，3，4要判断一下，对于3要判断当前行是否遍历过，即判断top<bottom,对于4的话则是判断left<right,满足的话才往左往上遍历

代码

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        /**

         */
        int top = 0,bottom = matrix.length,left=0,right=matrix[0].length;
        int num=0;
        int i=0,j=0;
        List<Integer> res = new ArrayList<>();
        while(num<matrix.length*matrix[0].length){
            j = left;
            while(j<right){
                res.add(matrix[top][j]);
                j++;
                num++;
            }
            top++;

            i=top;
            while(i<bottom){
                res.add(matrix[i][right-1]);
                i++;
                num++;
            }
            right--;

            j=right-1;
            while(top<bottom && j>=left){
                res.add(matrix[bottom-1][j]);
                j--;
                num++;
            }
            bottom--;

            i=bottom-1;
            while(left<right && i>=top){
                res.add(matrix[i][left]);
                i--;
                num++;
            }
            left++;
        }
        return res;
    }
}

4 48.旋转图像

48. 旋转图像

中等

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

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

示例 1：

img

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

输入：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].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

思路

没什么好说的，一遍过。

做过之后就是挺简单的题目

    容易证明
    先上下翻转
    之后按照从左上->右下的对角线反转，即为结果

代码

class Solution {
    public void rotate(int[][] matrix) {
        /**

         */
        //1.先上下翻转,matrix[i][j] <->matrix[n-i-1][j]
        int n = matrix.length;
        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.按照对角线翻转matrix[i][j] <-> matrix[j][i]
        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;
            }
        }
        return;
    }
}

5 73.矩阵置零 （一遍过）

73. 矩阵置零

中等

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

示例 1：

img

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

输入：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.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

进阶：

  • 一个直观的解决方案是使用 O(*m**n*) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

5.1 思路

用了标记数组。

        两个数组标记
        row[m]:row[i]标记第i行是否出现0
        col[n]:col[j]标记第j行是否出现0

        1.遍历matrix数字，为row和col两个标记数组赋值，从而得到 每行/每列是否出现0 的结果
        2.根据row和col两个数组，为原数组赋值

5.2 代码

class Solution {
    public void setZeroes(int[][] matrix) {
        /**

         */
        int m = matrix.length;
        int n = matrix[0].length;
        int[] row = new int[m];
        int[] col = new int[n];

        for(int i=0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(matrix[i][j]==0){
                    row[i]=1;
                    col[j]=1;
                }
            }
        }

        for(int i = 0;i<m;i++){
            if(row[i]==1){
                for(int j = 0;j<n;j++){
                    matrix[i][j]=0;
                }
            }
        }

        for(int j = 0;j<n;j++){
            if(col[j]==1){
                for(int i=0;i<m;i++){
                    matrix[i][j]=0;
                }
            }
        }
        return;
    }
}

6 289.生命游戏 （一遍过）

289. 生命游戏

中等

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

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

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

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

给定当前 board 的状态，更新 board 到下一个状态。

注意 你不需要返回任何东西。

示例 1：

img

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

img

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] 为 0 或 1

进阶：

  • 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
  • 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

分析

之前做过有印象。

只要能明白下面的东西就好做了。

    活->死 的细胞，用-1表示
    死->活 的细胞，用-2表示

        总结一下规则
        活细胞：当且仅当周围8个位置只有2/3个活细胞的时候，才能活
        死细胞：当周围8个位置正好有3个活细胞的时候，才能复活

        假如要原地算法的话，我们在更新细胞的时候，会发现还存在两种状态，即原本是活细胞，现在死了，原本是死细胞，现在活了。这两个状态我们用另外两个数来代表
        活->死 的细胞，用-1表示
        死->活 的细胞，用-2表示

        那么，在第一遍遍历的时候，
        对活细胞，该细胞周围 状态绝对值为1的细胞个数为2，3 ，该细胞仍然活着，不更改装填
                否则，将该细胞状态从1置为-1
        对死细胞，该细胞周围 状态绝对值为1的细胞个数为3，该细胞死而复生，状态修改为-2

        第二遍遍历，根据-1和-2修改对用的值，-1状态的修改为0，因为死了已经。
        -2状态的修改为1，因为死细胞活了

代码

class Solution {
    public void gameOfLife(int[][] board) {
        /**

         */
        int m = board.length;
        int n = board[0].length;

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                int num = getLifeNum(board,i,j);
                if(board[i][j]==1 && num!=2 && num!=3){
                    board[i][j]=-1;
                }else if (board[i][j]==0 && num==3){
                    board[i][j]=-2;
                }
            }
        }

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(board[i][j]==-1){
                    board[i][j]=0;
                }else if(board[i][j]==-2){
                    board[i][j]=1;
                }
            }
        }
        return;
    }

    public int getLifeNum(int[][] board,int x,int y){
        int m = board.length;
        int n = board[0].length;
        int num=0;
        int[][] dirc = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        for(int i = 0;i<8;i++){
            if(x+dirc[i][0]>=0 && x+dirc[i][0]<m && y+dirc[i][1]>=0 && y+dirc[i][1]<n && Math.abs(board[x+dirc[i][0]][y+dirc[i][1]])==1){
                num++;
            }
        }
        return num;
    }
}

http://www.kler.cn/a/459819.html

相关文章：

  • C++STL中string头文件的各种函数以及使用方法与细节
  • SpringBoot整合篇 05、Springboot整合Redission
  • 机器人C++开源库The Robotics Library (RL)使用手册（四）
  • FPGA 4x4矩阵键盘 实现
  • 计算机专业考研 408 学科学习方法
  • 微信小程序调用 WebAssembly 烹饪指南
  • 人民医院网络安全规划与设计
  • 正大的资产配置理念解析
  • day-102 二进制矩阵中的最短路径
  • STM32 高级 WIFi案例1：测试AT指令
  • 数据库自增 id 过大导致前端时数据丢失
  • 活动预告 |【Part1】Microsoft Azure 在线技术公开课：数据基础知识
  • Debian12使用RKE2离线部署3master2node三主两从的k8s集群详细教程
  • 通过iptables限制docker 容器的运行端口
  • Spring Boot 项目 与 其他依赖版本兼容对应表
  • K8S网络流量路径
  • 数据库系列之分布式数据库下误删表怎么恢复？
  • UE5材质节点CameraDepthFade
  • Kafka安全优化文档：漏洞修复到安全加固
  • 【已解决】PDF文档有密码怎么办（2024新）免费在线工具PDF2Go
  • 项目需求分析流程
  • 用AI生成PPT，告别繁琐，一键生成高效方案
  • 深入解析 Conda 安装的默认依赖包及其作用：conda create安装了哪些包（中英双语）
  • Spring Boot 中 RabbitMQ 的使用
  • Java虚拟机——JVM
  • 安装与配置