矩阵置零73. 矩阵置零 - 力扣LeetCode给定一个mxn的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法。示例 1输入matrix [[1,1,1],[1,0,1],[1,1,1]]输出[[1,0,1],[0,0,0],[1,0,1]]输入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]]解法及思路用第一行和第一列做标记核心思想不用额外数组直接用矩阵的第一行和第一列来标记 matrix[i][0] 0 → 第i行要置零 matrix[0][j] 0 → 第j列要置零但是问题来了第一行和第一列本身也可能要置零 如果用它们做标记就分不清 matrix[0][j]0 是原本就是0还是标记所以需要额外两个变量boolean firstRowZero false; // 第一行本身是否要置零 boolean firstColZero false; // 第一列本身是否要置零举例matrix [[1, 2, 3, 4],[5, 0, 7, 8],[9, 10, 0, 12],[13, 14, 15, 16]]第1步检查第一行是否有0第一行[1, 2, 3, 4]没有0 → firstRowZero false第2步检查第一列是否有0第一列[1, 5, 9, 13]没有0 → firstColZero false第3步用第一行/列标记内层遍历内层i1, j1: matrix[1][1]0 matrix[1][0] 0 ← 标记第1行 matrix[0][1] 0 ← 标记第1列 i1, j2: matrix[1][2]7不是0 i1, j3: matrix[1][3]8不是0 i2, j1: matrix[2][1]10不是0 i2, j2: matrix[2][2]0 matrix[2][0] 0 ← 标记第2行 matrix[0][2] 0 ← 标记第2列 i2, j3: matrix[2][3]12不是0 i3, j1: matrix[3][1]14不是0 i3, j2: matrix[3][2]15不是0 i3, j3: matrix[3][3]16不是0标记后矩阵[1, 0, 0, 4] ← matrix[0][1]0, matrix[0][2]0 [0, 0, 7, 8] ← matrix[1][0]0 [0, 10, 0, 12] ← matrix[2][0]0 [13, 14, 15, 16]第一行标记了第1列和第2列第一列标记了第1行和第2行第4步根据标记置零内层遍历内层i1, j1: matrix[1][0]0 → 置0 矩阵[1,0,0,4] [0,0,7,8] [0,10,0,12] [13,14,15,16] i1, j2: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,8] [0,10,0,12] [13,14,15,16] i1, j3: matrix[1][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,10,0,12] [13,14,15,16] i2, j1: matrix[2][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,12] [13,14,15,16] i2, j2: matrix[2][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,12] [13,14,15,16] i2, j3: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,14,15,16] i3, j1: matrix[3][0]13, matrix[0][1]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,15,16] i3, j2: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,0,16] i3, j3: matrix[3][0]13, matrix[0][3]4 → 不置零 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,0,16]置零后矩阵[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]第5步处理第一行firstRowZero false→ 不处理[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]第6步处理第一列firstColZero false→ 不处理[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]最终结果[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16] ✅class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; int n matrix[0].length; boolean firstRowZero false; boolean firstColZero false; // 第1步检查第一行 for (int j 0; j n; j) { if (matrix[0][j] 0) firstRowZero true; } // 第2步检查第一列 for (int i 0; i m; i) { if (matrix[i][0] 0) firstColZero true; } // 第3步标记 for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; // 标记行 matrix[0][j] 0; // 标记列 } } } // 第4步置零 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; } } } // 第5步处理第一行 if (firstRowZero) { for (int j 0; j n; j) matrix[0][j] 0; } // 第6步处理第一列 if (firstColZero) { for (int i 0; i m; i) matrix[i][0] 0; } } }螺旋矩阵54. 螺旋矩阵 - 力扣LeetCode给你一个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]解法及思路边界收缩用四个边界top 0 上边界 bottom m - 1 下边界 left 0 左边界 right n - 1 右边界按顺序遍历1. 从左到右top 行left → right 2. 从上到下right 列top → bottom 3. 从右到左bottom 行right → left 4. 从下到上left 列bottom → top 每遍历完一条边收缩对应边界输入[1, 2, 3] [4, 5, 6] [7, 8, 9]初始边界top0, bottom2, left0, right2第1步从左到右top行top0, left→right: 1, 2, 3 结果[1, 2, 3] top → top1第2步从上到下right列right2, top→bottom: 6, 9 结果[1, 2, 3, 6, 9] right-- → right1第3步从右到左bottom行bottom2, right→left: 8, 7 结果[1, 2, 3, 6, 9, 8, 7] bottom-- → bottom1第4步从下到上left列left0, bottom→top: 4 结果[1, 2, 3, 6, 9, 8, 7, 4] left → left1第5步从左到右top行top1, left→right: 5 结果[1, 2, 3, 6, 9, 8, 7, 4, 5] top → top2结束top2 bottom1退出循环结果[1, 2, 3, 6, 9, 8, 7, 4, 5]✅class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0) return result; int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (top bottom left right) { // 1. 从左到右 for (int j left; j right; j) { result.add(matrix[top][j]); } top; // 2. 从上到下 for (int i top; i bottom; i) { result.add(matrix[i][right]); } right--; // 3. 从右到左需要判断是否还有行 if (top bottom) { for (int j right; j left; j--) { result.add(matrix[bottom][j]); } bottom--; } // 4. 从下到上需要判断是否还有列 if (left right) { for (int i bottom; i top; i--) { result.add(matrix[i][left]); } left; } } return result; } }旋转图像48. 旋转图像 - 力扣LeetCode给定一个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]]解法及思路先转置再反转顺时针旋转 90 度 转置 每行反转第1步转置行列互换 [1, 2, 3] [1, 4, 7] [4, 5, 6] → [2, 5, 8] [7, 8, 9] [3, 6, 9] 第2步每行反转 [1, 4, 7] [7, 4, 1] [2, 5, 8] → [8, 5, 2] [3, 6, 9] [9, 6, 3] ✅输入[1, 2, 3] [4, 5, 6] [7, 8, 9]第1步转置转置就是matrix[i][j]和matrix[j][i]交换。i0, j1: 交换 matrix[0][1] 和 matrix[1][0] 2 和 4 交换 [1, 4, 3] [2, 5, 6] [7, 8, 9] i0, j2: 交换 matrix[0][2] 和 matrix[2][0] 3 和 7 交换 [1, 4, 7] [2, 5, 6] [3, 8, 9] i1, j2: 交换 matrix[1][2] 和 matrix[2][1] 6 和 8 交换 [1, 4, 7] [2, 5, 8] [3, 6, 9] 转置完成第2步每行反转第0行[1, 4, 7] → [7, 4, 1] 第1行[2, 5, 8] → [8, 5, 2] 第2行[3, 6, 9] → [9, 6, 3] 结果 [7, 4, 1] [8, 5, 2] [9, 6, 3] ✅class Solution { public void rotate(int[][] matrix) { int n matrix.length; // 第1步转置 for (int i 0; i n; i) { for (int j i 1; j n; j) {// 注意j 从 i1 开始,只遍历上三角避免重复交换 int temp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] temp; } } // 第2步每行反转 for (int i 0; i n; i) { for (int j 0; j n / 2; j) {// 只遍历前一半 int temp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] temp; } } } }搜索二维矩阵||240. 搜索二维矩阵 II - 力扣LeetCode编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5输出true示例 2输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 20输出false解法及思路从右上角开始关键右上角的元素有特殊性质。右上角15 比15小的左边所有元素同一行左边 比15大的下边所有元素同一列下边 所以 target 15 → 往左走排除这一列 target 15 → 往下走排除这一行 target 15 → 找到为什么从右上角因为右上角是这一行最大这一列最小 可以明确判断往哪走输入[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10, 13, 14, 17, 24] [18, 21, 23, 26, 30] target 5从右上角开始初始row0, col4 matrix[0][4] 15 15 5 → 往左走col3 matrix[0][3] 11 11 5 → 往左走col2 matrix[0][2] 7 7 5 → 往左走col1 matrix[0][1] 4 4 5 → 往下走row1 matrix[1][1] 5 5 5 → 找到✅class Solution { public boolean searchMatrix(int[][] matrix, int target) { int mmatrix.length; int nmatrix[0].length; int row 0; // 从右上角开始 int col n - 1; while(rowmcol0){ if(matrix[row][col]target){ return true; }else if(matrix[row][col]target){ col--;//大了往左 }else{ row;//小了往下 } } return false; } }
矩阵置零73. 矩阵置零 - 力扣LeetCode给定一个mxn的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法。示例 1输入matrix [[1,1,1],[1,0,1],[1,1,1]]输出[[1,0,1],[0,0,0],[1,0,1]]输入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]]解法及思路用第一行和第一列做标记核心思想不用额外数组直接用矩阵的第一行和第一列来标记 matrix[i][0] 0 → 第i行要置零 matrix[0][j] 0 → 第j列要置零但是问题来了第一行和第一列本身也可能要置零 如果用它们做标记就分不清 matrix[0][j]0 是原本就是0还是标记所以需要额外两个变量boolean firstRowZero false; // 第一行本身是否要置零 boolean firstColZero false; // 第一列本身是否要置零举例matrix [[1, 2, 3, 4],[5, 0, 7, 8],[9, 10, 0, 12],[13, 14, 15, 16]]第1步检查第一行是否有0第一行[1, 2, 3, 4]没有0 → firstRowZero false第2步检查第一列是否有0第一列[1, 5, 9, 13]没有0 → firstColZero false第3步用第一行/列标记内层遍历内层i1, j1: matrix[1][1]0 matrix[1][0] 0 ← 标记第1行 matrix[0][1] 0 ← 标记第1列 i1, j2: matrix[1][2]7不是0 i1, j3: matrix[1][3]8不是0 i2, j1: matrix[2][1]10不是0 i2, j2: matrix[2][2]0 matrix[2][0] 0 ← 标记第2行 matrix[0][2] 0 ← 标记第2列 i2, j3: matrix[2][3]12不是0 i3, j1: matrix[3][1]14不是0 i3, j2: matrix[3][2]15不是0 i3, j3: matrix[3][3]16不是0标记后矩阵[1, 0, 0, 4] ← matrix[0][1]0, matrix[0][2]0 [0, 0, 7, 8] ← matrix[1][0]0 [0, 10, 0, 12] ← matrix[2][0]0 [13, 14, 15, 16]第一行标记了第1列和第2列第一列标记了第1行和第2行第4步根据标记置零内层遍历内层i1, j1: matrix[1][0]0 → 置0 矩阵[1,0,0,4] [0,0,7,8] [0,10,0,12] [13,14,15,16] i1, j2: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,8] [0,10,0,12] [13,14,15,16] i1, j3: matrix[1][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,10,0,12] [13,14,15,16] i2, j1: matrix[2][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,12] [13,14,15,16] i2, j2: matrix[2][0]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,12] [13,14,15,16] i2, j3: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,14,15,16] i3, j1: matrix[3][0]13, matrix[0][1]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,15,16] i3, j2: matrix[0][2]0 → 置0 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,0,16] i3, j3: matrix[3][0]13, matrix[0][3]4 → 不置零 矩阵[1,0,0,4] [0,0,0,0] [0,0,0,0] [13,0,0,16]置零后矩阵[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]第5步处理第一行firstRowZero false→ 不处理[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]第6步处理第一列firstColZero false→ 不处理[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16]最终结果[1, 0, 0, 4] [0, 0, 0, 0] [0, 0, 0, 0] [13, 0, 0, 16] ✅class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; int n matrix[0].length; boolean firstRowZero false; boolean firstColZero false; // 第1步检查第一行 for (int j 0; j n; j) { if (matrix[0][j] 0) firstRowZero true; } // 第2步检查第一列 for (int i 0; i m; i) { if (matrix[i][0] 0) firstColZero true; } // 第3步标记 for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; // 标记行 matrix[0][j] 0; // 标记列 } } } // 第4步置零 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; } } } // 第5步处理第一行 if (firstRowZero) { for (int j 0; j n; j) matrix[0][j] 0; } // 第6步处理第一列 if (firstColZero) { for (int i 0; i m; i) matrix[i][0] 0; } } }螺旋矩阵54. 螺旋矩阵 - 力扣LeetCode给你一个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]解法及思路边界收缩用四个边界top 0 上边界 bottom m - 1 下边界 left 0 左边界 right n - 1 右边界按顺序遍历1. 从左到右top 行left → right 2. 从上到下right 列top → bottom 3. 从右到左bottom 行right → left 4. 从下到上left 列bottom → top 每遍历完一条边收缩对应边界输入[1, 2, 3] [4, 5, 6] [7, 8, 9]初始边界top0, bottom2, left0, right2第1步从左到右top行top0, left→right: 1, 2, 3 结果[1, 2, 3] top → top1第2步从上到下right列right2, top→bottom: 6, 9 结果[1, 2, 3, 6, 9] right-- → right1第3步从右到左bottom行bottom2, right→left: 8, 7 结果[1, 2, 3, 6, 9, 8, 7] bottom-- → bottom1第4步从下到上left列left0, bottom→top: 4 结果[1, 2, 3, 6, 9, 8, 7, 4] left → left1第5步从左到右top行top1, left→right: 5 结果[1, 2, 3, 6, 9, 8, 7, 4, 5] top → top2结束top2 bottom1退出循环结果[1, 2, 3, 6, 9, 8, 7, 4, 5]✅class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0) return result; int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (top bottom left right) { // 1. 从左到右 for (int j left; j right; j) { result.add(matrix[top][j]); } top; // 2. 从上到下 for (int i top; i bottom; i) { result.add(matrix[i][right]); } right--; // 3. 从右到左需要判断是否还有行 if (top bottom) { for (int j right; j left; j--) { result.add(matrix[bottom][j]); } bottom--; } // 4. 从下到上需要判断是否还有列 if (left right) { for (int i bottom; i top; i--) { result.add(matrix[i][left]); } left; } } return result; } }旋转图像48. 旋转图像 - 力扣LeetCode给定一个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]]解法及思路先转置再反转顺时针旋转 90 度 转置 每行反转第1步转置行列互换 [1, 2, 3] [1, 4, 7] [4, 5, 6] → [2, 5, 8] [7, 8, 9] [3, 6, 9] 第2步每行反转 [1, 4, 7] [7, 4, 1] [2, 5, 8] → [8, 5, 2] [3, 6, 9] [9, 6, 3] ✅输入[1, 2, 3] [4, 5, 6] [7, 8, 9]第1步转置转置就是matrix[i][j]和matrix[j][i]交换。i0, j1: 交换 matrix[0][1] 和 matrix[1][0] 2 和 4 交换 [1, 4, 3] [2, 5, 6] [7, 8, 9] i0, j2: 交换 matrix[0][2] 和 matrix[2][0] 3 和 7 交换 [1, 4, 7] [2, 5, 6] [3, 8, 9] i1, j2: 交换 matrix[1][2] 和 matrix[2][1] 6 和 8 交换 [1, 4, 7] [2, 5, 8] [3, 6, 9] 转置完成第2步每行反转第0行[1, 4, 7] → [7, 4, 1] 第1行[2, 5, 8] → [8, 5, 2] 第2行[3, 6, 9] → [9, 6, 3] 结果 [7, 4, 1] [8, 5, 2] [9, 6, 3] ✅class Solution { public void rotate(int[][] matrix) { int n matrix.length; // 第1步转置 for (int i 0; i n; i) { for (int j i 1; j n; j) {// 注意j 从 i1 开始,只遍历上三角避免重复交换 int temp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] temp; } } // 第2步每行反转 for (int i 0; i n; i) { for (int j 0; j n / 2; j) {// 只遍历前一半 int temp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] temp; } } } }搜索二维矩阵||240. 搜索二维矩阵 II - 力扣LeetCode编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5输出true示例 2输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 20输出false解法及思路从右上角开始关键右上角的元素有特殊性质。右上角15 比15小的左边所有元素同一行左边 比15大的下边所有元素同一列下边 所以 target 15 → 往左走排除这一列 target 15 → 往下走排除这一行 target 15 → 找到为什么从右上角因为右上角是这一行最大这一列最小 可以明确判断往哪走输入[1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] [10, 13, 14, 17, 24] [18, 21, 23, 26, 30] target 5从右上角开始初始row0, col4 matrix[0][4] 15 15 5 → 往左走col3 matrix[0][3] 11 11 5 → 往左走col2 matrix[0][2] 7 7 5 → 往左走col1 matrix[0][1] 4 4 5 → 往下走row1 matrix[1][1] 5 5 5 → 找到✅class Solution { public boolean searchMatrix(int[][] matrix, int target) { int mmatrix.length; int nmatrix[0].length; int row 0; // 从右上角开始 int col n - 1; while(rowmcol0){ if(matrix[row][col]target){ return true; }else if(matrix[row][col]target){ col--;//大了往左 }else{ row;//小了往下 } } return false; } }
