Hot100之矩阵

73矩阵置零

题目

思路解析

收集0位置所在的行和列

然后该行全部初始化为0

该列全部初始化为0

代码

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;List<Integer> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {list1.add(i);list2.add(j);}}}for (int temp : list1) {for (int i = 0; i < n; i++) {matrix[temp][i] = 0;}}for (int temp : list2) {for (int i = 0; i < m; i++) {matrix[i][temp] = 0;}}}
}

---

54螺旋矩阵

题目

思路解析

直接左右下左上

这样子循环遍历就好了

主要注意的是我们的边界处理问题

代码

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> ans = new ArrayList<>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;int up = 0, down = matrix.length - 1;int left = 0, right = matrix[0].length - 1;while (true) {for (int i = left; i <= right; i++) { // 左->右ans.add(matrix[up][i]);}if (++up > down) break;for (int i = up; i <= down; i++) { // 上->下ans.add(matrix[i][right]);}if (--right < left) break;for (int i = right; i >= left; i--) { // 右->左ans.add(matrix[down][i]);}if (--down < up) break;for (int i = down; i >= up; i--) { // 下->上ans.add(matrix[i][left]);}if (++left > right) break;}return ans;}
}

---

48旋转图像

题目

思路解析

辅助矩阵

我们clone一个矩阵辅助我们，然后根据公式计算

原地修改

如上图所示，一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。

具体来看，当矩阵大小 n 为偶数时，取前 n/2 行、前 n/2 列的元素为起始点；

当矩阵大小 n 为奇数时，取前 n/2 行、前 (n+1)/2 列的元素为起始点

i=0，j=0

i=0,j=1

i=1,j=0

i=1,j=1

代码

辅助矩阵

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 深拷贝 matrix -> tmpint[][] tmp = new int[n][];for (int i = 0; i < n; i++)tmp[i] = matrix[i].clone();// 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[j][n - 1 - i] = tmp[i][j];}}}
}

原地修改

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 + 1) / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][i];matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];matrix[j][n - 1 - i] = tmp;}}}
}

---

240搜索二维矩阵

题目

思路解析

灵神题解-排除法

我们从右上角开始

我们先通过每行最后一个位置来排除行

行排除完之后，我们再根据列最小的位置来排除列

代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = 0;int j = matrix[0].length - 1; // 从右上角开始while (i < matrix.length && j >= 0) { // 还有剩余元素if (matrix[i][j] == target) {return true; // 找到 target}if (matrix[i][j] < target) {i++; // 这一行剩余元素全部小于 target，排除} else {j--; // 这一列剩余元素全部大于 target，排除}}return false;}
}