青岛建网站需要花多少钱_如何制作应用软件_今日头条新闻_如何网络媒体推广

在力扣（LeetCode）平台上，热题 100 是许多开发者提升算法能力的必刷清单。今天，我们就来详细解析热题 100 中与矩阵相关的四道题，帮助大家更好地理解解题思路和技巧。

一、矩阵置零（题目 73）

1. 题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在的行和列的所有元素都设置为 0。你需要原地修改矩阵。

2. 示例

示例 1：

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

输出：[[1,0,1],[0,0,0],[1,0,1]]

解释：矩阵中有一个元素为 0，将其所在的行和列的所有元素都设置为 0。

3. 解题思路

这道题主要考察矩阵的操作和空间优化。我们可以使用矩阵的第一行和第一列来记录每一行和每一列是否需要置零。具体步骤如下：

1. 使用两个变量 firstRowHasZero 和 firstColHasZero 来记录第一行和第一列是否包含 0。
2. 遍历矩阵，如果 matrix[i][j] == 0，则将 matrix[i][0] 和 matrix[0][j] 设置为 0。
3. 遍历矩阵，根据第一行和第一列的标记，将对应的元素置零。
4. 如果 firstRowHasZero 为 true，将第一行的所有元素置零；如果 firstColHasZero 为 true，将第一列的所有元素置零。

4. 代码实现（Java）

public class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean firstRowHasZero = false, firstColHasZero = false;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {if (i == 0) firstRowHasZero = true;if (j == 0) firstColHasZero = true;if (i != 0 && j != 0) {matrix[i][0] = 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 (firstRowHasZero) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}if (firstColHasZero) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}}
}

5. 复杂度分析

• 时间复杂度 ：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。我们需要遍历矩阵两次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

二、螺旋矩阵（题目 54）

1. 题目描述

给定一个 m x n 的矩阵，返回以螺旋顺序遍历矩阵的结果。

2. 示例

示例 1：

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

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

解释：矩阵以螺旋顺序遍历的结果为 [1, 2, 3, 6, 9, 8, 7, 4, 5]。

3. 解题思路

这道题主要考察矩阵的遍历和边界控制。我们可以使用四个变量 top、bottom、left 和 right 来表示当前遍历的边界，然后按照顺时针方向依次遍历矩阵的元素。具体步骤如下：

1. 初始化四个边界变量 top = 0、bottom = m - 1、left = 0、right = n - 1。
2. 按照顺时针方向依次遍历矩阵的元素：
   • 从左到右遍历 top 行的元素。
   • 从上到下遍历 right 列的元素。
   • 从右到左遍历 bottom 行的元素。
   • 从下到上遍历 left 列的元素。
3. 更新边界变量，缩小遍历范围，重复步骤 2，直到遍历完整个矩阵。

4. 代码实现（Java）

public class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new ArrayList<>();if (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) {// 从左到右for (int j = left; j <= right; j++) {result.add(matrix[top][j]);}// 从上到下for (int i = top + 1; i <= bottom; i++) {result.add(matrix[i][right]);}// 从右到左if (top < bottom) {for (int j = right - 1; j >= left; j--) {result.add(matrix[bottom][j]);}}// 从下到上if (left < right) {for (int i = bottom - 1; i > top; i--) {result.add(matrix[i][left]);}}top++;bottom--;left++;right--;}return result;}
}

5. 复杂度分析

• 时间复杂度 ：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。我们需要遍历矩阵中的每个元素一次。
• 空间复杂度 ：O(m * n)，需要使用一个列表来存储遍历的结果。

三、旋转图像（题目 48）

1. 题目描述

给定一个 n x n 的矩阵，将其顺时针旋转 90 度。

2. 示例

示例 1：

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

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

解释：矩阵顺时针旋转 90 度后的结果为 [[7, 4, 1], [8, 5, 2], [9, 6, 3]]。

3. 解题思路

这道题主要考察矩阵的旋转和原地操作。我们可以先将矩阵转置，然后将每一行反转，从而实现顺时针旋转 90 度。具体步骤如下：

1. 将矩阵转置，即交换 matrix[i][j] 和 matrix[j][i]。
2. 将每一行反转，即交换 matrix[i][j] 和 matrix[i][n - 1 - j]。

4. 代码实现（Java）

public class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 转置矩阵for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}// 反转每一行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;}}}
}

5. 复杂度分析

• 时间复杂度 ：O(n^2)，其中 n 是矩阵的边长。我们需要遍历矩阵中的每个元素一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

四、搜索二维矩阵 II（题目 240）

1. 题目描述

给定一个 m x n 的矩阵，每一行和每一列都按升序排列。请在矩阵中查找一个目标值，如果找到则返回 true，否则返回 false。

2. 示例

示例 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

解释：目标值 5 存在于矩阵中。

3. 解题思路

这道题主要考察矩阵的搜索和二分查找。我们可以从矩阵的右上角开始搜索，根据目标值与当前元素的大小关系，决定向左还是向下移动。具体步骤如下：

1. 初始化两个指针 i = 0 和 j = n - 1，分别指向矩阵的行首和列尾。
2. 遍历矩阵，直到 i 超过行数或 j 小于 0：
   • 如果 matrix[i][j] == target，返回 true。
   • 如果 matrix[i][j] > target，向左移动一列（j--）。
   • 如果 matrix[i][j] < target，向下移动一行（i++）。
3. 如果遍历完整个矩阵仍未找到目标值，返回 false。

4. 代码实现（Java）

public class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix.length == 0 || matrix[0].length == 0) return false;int m = matrix.length, n = matrix[0].length;int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target) {return true;} else if (matrix[i][j] > target) {j--;} else {i++;}}return false;}
}

5. 复杂度分析

• 时间复杂度 ：O(m + n)，其中 m 和 n 分别是矩阵的行数和列数。我们最多需要遍历矩阵的行数和列数之和。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

以上就是力扣热题 100 中与矩阵相关的四道题的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。