LeetCode 热题 100 | 矩阵
矩阵底子[*]使用哈希数组来标记当前行或者列是否出现0
[*]按层模拟
[*]旋转90度可以先水平翻，然后再对角线翻
73. 矩阵置零
标题讲授：LeetCode
重点：
[*]使用标记数组：用两个标记数组分别记录每一行和每一列是否有零出现。
[*]使用两个标记变量：用矩阵的第一行和第一列代替两个标记数组。再额外使用两个标记变量分别记录第一行和第一列是否本来包罗 0。
思路：
[*]使用标记数组
1.起首遍历该数组一次，假如某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。
2.末了我们再次遍历该数组，用标记数组更新原数组即可。
[*]使用两个标记变量
1.起首预处理出两个标记变量，接着使用其他行与列行止理第一行与第一列。
2.然后反过来使用第一行与第一列去更新其他行与列，末了使用两个标记变量更新第一行与第一列即可。
复杂度：
[*]m 是矩阵的行数，n 是矩阵的列数
[*]使用标记数组
时间复杂度：O(mn)
空间复杂度：O(m+n)
[*]使用两个标记变量
时间复杂度：O(mn)
空间复杂度：O(1)
// 使用标记数组
public void setZeroes(int[][] matrix) {
// 重点: 用两个标记数组分别记录每一行和每一列是否有零出现
boolean[] row = new boolean;
boolean[] col = new boolean.length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (matrix == 0) {
row = true;
col = true;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (row || col) matrix = 0;
}
}
}
// 使用两个标记变量
public void setZeroes(int[][] matrix) {
boolean row0Flag = false;
boolean col0Flag = false;
for (int j = 0; j < matrix.length; j++) {
if (matrix == 0) {
row0Flag = true;
break;
}
}
for (int i = 0; i < matrix.length; i++) {
if (matrix == 0) {
col0Flag = true;
break;
}
}
// 重点: 使用第一行和第一列标记
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix.length; j++) {
if (matrix == 0) {
matrix = 0;
matrix = 0;
}
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix.length; j++) {
if (matrix == 0 || matrix == 0) {
matrix = 0;
}
}
}
// 重点: 再用两个标记变量处理第一行和第一列
if (row0Flag) {
Arrays.fill(matrix, 0);
}
if (col0Flag) {
for (int i = 0; i < matrix.length; i++) matrix = 0;
}
}
54. 螺旋矩阵
标题讲授：LeetCode
重点：
[*]按层模拟。四个标记。
思路：
[*]按层模拟
1.每一层遍历 顶 右 底 左。每遍历完一个对应的边界需要处理。
复杂度：
[*]m 和 n 分别是行数和列数
[*]时间复杂度：O(mn)。每个元素都要被访问一次。
[*]空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int curTop = 0;
int curRight = matrix.length - 1;
int curBottom = matrix.length - 1;
int curLeft = 0;
// 重点: 按层模拟, 每一层遍历 顶 右 底 左
while (curLeft <= curRight && curTop <= curBottom) {
// 当前层的最顶行
for (int i = curLeft; i <= curRight; i++) {
result.add(matrix);
}
curTop++;
// 当前层的最右列
for (int i = curTop; i <= curBottom; i++) {
result.add(matrix);
}
curRight--;
// 当前外层的最底行还存在
if (curTop <= curBottom) {
for (int i = curRight; i >= curLeft; i--) {
result.add(matrix);
}
}
curBottom--;
// 当前外层的最左列还存在
if (curLeft <= curRight) {
for (int i = curBottom; i >= curTop; i--) {
result.add(matrix);
}
}
curLeft++;
}
return result;
}
48. 旋转图像
标题讲授：LeetCode
重点：
[*]原地旋转代码背下来。
[*]用翻转代替旋转。水平翻，然后对角线翻。
思路：
[*]原地旋转
[*]逆时间的顺序来替换。背下来。
[*]用翻转代替旋转
[*]先水平翻转
[*]再对角线翻转
复杂度：
[*]N 是 matrix 的边长
[*]原地旋转
时间复杂度：O(N^2)
空间复杂度：O(1)
[*]用翻转代替旋转
时间复杂度：O(N^2)
空间复杂度：O(1)
// 原地旋转
public void rotate(int[][] matrix) {
int n = matrix.length;
// 替换一半另一半就相当于自动替换过去了
for (int i = 0; i < n / 2; i++) {
// 内层要加一是因为n为奇数时需要多遍历一遍
for (int j = 0; j < (n + 1) / 2; j++) {
int temp = matrix;
// 逆时针替换
// 左上
matrix = matrix;
// 左下
matrix = matrix;
// 右下
matrix = matrix;
// 右上
matrix = temp;
}
}
}
// 用翻转代替旋转
public void rotate(int[][] matrix) {
int n = matrix.length;
// 重点: 先水平翻转
for (int i = 0; i < matrix.length / 2; i++) {
for (int j = 0; j < matrix.length; j++) {
int temp = matrix;
matrix = matrix;
matrix = temp;
}
}
// 重点: 再对角线翻转, 循环条件看作楼梯, 外层循环i=0则为对角线左侧楼梯顶层
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix;
matrix = matrix;
matrix = temp;
}
}
}
标题讲授：LeetCode
重点：
1.
思路：
1.
复杂度：
[*]时间复杂度：
[*]空间复杂度：
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]