免费建造公司网站,网页设计公司背景图,金华网站制作费用,网站没有收录原因矩阵 1. 矩阵置零#xff08;Set Matrix Zeroes#xff09;解题思路步骤#xff1a; 代码实现 2. 螺旋矩阵#xff08;Spiral Matrix#xff09;解题思路具体步骤#xff1a; 代码实现 3. 旋转矩阵 90 度解决思路代码实现 5. 搜索二维矩阵中的目标值解决思路代码实现 1. … 矩阵 1. 矩阵置零Set Matrix Zeroes解题思路步骤 代码实现 2. 螺旋矩阵Spiral Matrix解题思路具体步骤 代码实现 3. 旋转矩阵 90 度解决思路代码实现 5. 搜索二维矩阵中的目标值解决思路代码实现 1. 矩阵置零Set Matrix Zeroes
给定一个 m x n 的矩阵 matrix如果一个元素是 0则将其所在的整行和整列都设置为 0。你需要 原地 修改输入矩阵不能 使用额外的矩阵。
解题思路
要实现原地修改矩阵可以借助矩阵的第一行和第一列作为辅助存储记录哪些行和列需要被置零。
步骤 检查第一行和第一列是否包含零 由于我们使用第一行和第一列来标记其他行列是否需要置零所以需要先检查第一行和第一列是否包含零。如果包含零我们分别用 rowFlag 和 colFlag 进行标记。 遍历矩阵 从第二行第二列开始遍历整个矩阵。如果某个元素是零则将其所在的第一行和第一列对应的元素设为零表示该行和该列后续需要置零。 根据标记置零 再次遍历矩阵根据第一行和第一列的标记将需要置零的位置修改为零。 处理第一行和第一列 最后根据 rowFlag 和 colFlag 的值单独处理第一行和第一列的置零问题。
代码实现
class Solution {public void setZeroes(int[][] matrix) {int n matrix[0].length; // 列数int m matrix.length; // 行数boolean colFlag false, rowFlag false;// 检查第一列是否包含零for (int i 0; i m; i) {if (matrix[i][0] 0) {colFlag true;break;}}// 检查第一行是否包含零for (int j 0; j n; j) {if (matrix[0][j] 0) {rowFlag true;break;}}// 遍历矩阵使用第一行和第一列标记零的位置for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i][j] 0) {matrix[0][j] 0; // 标记该列matrix[i][0] 0; // 标记该行}}}// 根据第一行和第一列的标记进行置零for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[0][j] 0 || matrix[i][0] 0) {matrix[i][j] 0;}}}// 处理第一列置零if (colFlag) {for (int i 0; i m; i) {matrix[i][0] 0;}}// 处理第一行置零if (rowFlag) {for (int j 0; j n; j) {matrix[0][j] 0;}}}
}2. 螺旋矩阵Spiral Matrix
给定一个 m x n 的矩阵按螺旋顺序返回矩阵中的所有元素。
解题思路
我们可以模拟螺旋遍历的过程使用四个边界来控制当前遍历的范围。随着遍历的进行逐步缩小这些边界直到遍历完成整个矩阵。
具体步骤 定义边界 l 表示左边界初始为 0。r 表示右边界初始为 m-1。t 表示上边界初始为 0。b 表示下边界初始为 n-1。 遍历顺序 按照螺旋顺序从左到右遍历上边界向下遍历右边界从右到左遍历下边界向上遍历左边界。每次遍历完一条边后更新相应的边界。 终止条件 当结果列表的大小等于 m * n 时遍历结束。
代码实现
class Solution {public ListInteger spiralOrder(int[][] matrix) {ListInteger list new ArrayList();int m matrix[0].length, n matrix.length;int l 0, r m - 1, t 0, b n - 1;// 继续遍历直到所有元素都被加入列表while (list.size() m * n) {// 从左到右遍历上边界for (int i l; i r; i) {if (list.size() m * n) break;list.add(matrix[t][i]);}t; // 缩小上边界的范围// 从上到下遍历右边界for (int i t; i b; i) {if (list.size() m * n) break;list.add(matrix[i][r]);}r--; // 缩小右边界的范围// 从右到左遍历下边界for (int i r; i l; i--) {if (list.size() m * n) break;list.add(matrix[b][i]);}b--; // 缩小下边界的范围// 从下到上遍历左边界for (int i b; i t; i--) {if (list.size() m * n) break;list.add(matrix[i][l]);}l; // 缩小左边界的范围}return list;}
}3. 旋转矩阵 90 度
给定一个 n x n 的二维矩阵编写一个函数将该矩阵顺时针旋转 90 度。你必须在原地即不使用额外的二维数组完成旋转。
解决思路
该问题可以通过两步操作实现
水平翻转将矩阵上下翻转。对角线翻转再将矩阵沿主对角线进行翻转。
通过这两步操作我们可以原地完成矩阵的 90 度顺时针旋转。
代码实现
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; j) {int temp matrix[i][j];matrix[i][j] matrix[n-i-1][j];matrix[n-i-1][j] temp;}}// 再沿着对角线翻转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;}}}
}
5. 搜索二维矩阵中的目标值
给定一个 m x n 的矩阵 matrix 和一个目标值 target编写一个函数判断目标值是否在矩阵中。矩阵中的元素按照以下规则排序
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
你需要在 O(m n) 时间复杂度内完成这个搜索。
解决思路
由于矩阵的元素是按行升序、按列升序排列的我们可以使用一种特殊的搜索方法 从矩阵的右上角开始搜索 如果当前元素等于目标值直接返回 true。如果当前元素大于目标值说明目标值可能在该元素的左边向左移动一列。如果当前元素小于目标值说明目标值可能在该元素的下方向下移动一行。 这样每次搜索都可以排除一行或一列因此我们可以在 O(m n) 时间复杂度内完成搜索。
代码实现
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; // 找到目标值} else if (matrix[x][y] target) {y--; // 当前值大于目标值向左移动} else {x; // 当前值小于目标值向下移动}}return false; // 未找到目标值}
}
