LeetCode 热题 100 | 矩阵

矩阵底子

  

• 使用哈希数组来标记当前行或者列是否出现0
  
• 按层模拟
  
• 旋转90度可以先水平翻，然后再对角线翻
  

    73. 矩阵置零

  标题讲授：LeetCode
重点：
  

• 使用标记数组：用两个标记数组分别记录每一行和每一列是否有零出现。
  
• 使用两个标记变量：用矩阵的第一行和第一列代替两个标记数组。再额外使用两个标记变量分别记录第一行和第一列是否本来包罗 0。
  

  思路：
  

• 使用标记数组
  1.起首遍历该数组一次，假如某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。
  2.末了我们再次遍历该数组，用标记数组更新原数组即可。
  
• 使用两个标记变量
  1.起首预处理出两个标记变量，接着使用其他行与列行止理第一行与第一列。
  2.然后反过来使用第一行与第一列去更新其他行与列，末了使用两个标记变量更新第一行与第一列即可。
  

  复杂度：
  

• m 是矩阵的行数，n 是矩阵的列数
  
• 使用标记数组
  时间复杂度：O(mn)
  空间复杂度：O(m+n)
  
• 使用两个标记变量
  时间复杂度：O(mn)
  空间复杂度：O(1)
  

1. // 使用标记数组
2. public void setZeroes(int[][] matrix) {
3.     // 重点: 用两个标记数组分别记录每一行和每一列是否有零出现
4.     boolean[] row = new boolean[matrix.length];
5.     boolean[] col = new boolean[matrix[0].length];
6.     for (int i = 0; i < matrix.length; i++) {
7.         for (int j = 0; j < matrix[0].length; j++) {
8.             if (matrix[i][j] == 0) {
9.                 row[i] = true;
10.                 col[j] = true;
11.             }
12.         }
13.     }
14.     for (int i = 0; i < matrix.length; i++) {
15.         for (int j = 0; j < matrix[0].length; j++) {
16.             if (row[i] || col[j]) matrix[i][j] = 0;
17.         }
18.     }
19. }

复制代码

1. // 使用两个标记变量
2. public void setZeroes(int[][] matrix) {
3.     boolean row0Flag = false;
4.     boolean col0Flag = false;
5.     for (int j = 0; j < matrix[0].length; j++) {
6.         if (matrix[0][j] == 0) {
7.             row0Flag = true;
8.             break;
9.         }
10.     }
11.     for (int i = 0; i < matrix.length; i++) {
12.         if (matrix[i][0] == 0) {
13.             col0Flag = true;
14.             break;
15.         }
16.     }
17.     // 重点: 使用第一行和第一列标记
18.     for (int i = 1; i < matrix.length; i++) {
19.         for (int j = 1; j < matrix[0].length; j++) {
20.             if (matrix[i][j] == 0) {
21.                 matrix[0][j] = 0;
22.                 matrix[i][0] = 0;
23.             }
24.         }
25.     }
26.     for (int i = 1; i < matrix.length; i++) {
27.         for (int j = 1; j < matrix[0].length; j++) {
28.             if (matrix[0][j] == 0 || matrix[i][0] == 0) {
29.                 matrix[i][j] = 0;
30.             }
31.         }
32.     }
33.     // 重点: 再用两个标记变量处理第一行和第一列
34.     if (row0Flag) {
35.         Arrays.fill(matrix[0], 0);
36.     }
37.     if (col0Flag) {
38.         for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0;
39.     }
40. }

复制代码

  54. 螺旋矩阵

  标题讲授：LeetCode
重点：
  

• 按层模拟。四个标记。
  

  思路：
  

• 按层模拟
  1.每一层遍历 顶 右 底 左。每遍历完一个对应的边界需要处理。
  

  复杂度：
  

• m 和 n 分别是行数和列数
  
• 时间复杂度：O(mn)。每个元素都要被访问一次。
  
• 空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。
  

1. public List<Integer> spiralOrder(int[][] matrix) {
2.     List<Integer> result = new ArrayList<>();
3.     int curTop = 0;
4.     int curRight = matrix[0].length - 1;
5.     int curBottom = matrix.length - 1;
6.     int curLeft = 0;
7.     // 重点: 按层模拟, 每一层遍历 顶 右 底 左
8.     while (curLeft <= curRight && curTop <= curBottom) {
9.         // 当前层的最顶行
10.         for (int i = curLeft; i <= curRight; i++) {
11.             result.add(matrix[curTop][i]);
12.         }
13.         curTop++;
14.         // 当前层的最右列
15.         for (int i = curTop; i <= curBottom; i++) {
16.             result.add(matrix[i][curRight]);
17.         }
18.         curRight--;
19.         // 当前外层的最底行还存在
20.         if (curTop <= curBottom) {
21.             for (int i = curRight; i >= curLeft; i--) {
22.                 result.add(matrix[curBottom][i]);
23.             }
24.         }
25.         curBottom--;
26.         // 当前外层的最左列还存在
27.         if (curLeft <= curRight) {
28.             for (int i = curBottom; i >= curTop; i--) {
29.                 result.add(matrix[i][curLeft]);
30.             }
31.         }
32.         curLeft++;
33.     }
34.     return result;
35. }

复制代码

  48. 旋转图像

  标题讲授：LeetCode
重点：
  

• 原地旋转代码背下来。
  
• 用翻转代替旋转。水平翻，然后对角线翻。
  

  思路：
  

• 原地旋转
  

  

• 逆时间的顺序来替换。背下来。
  

  

• 用翻转代替旋转
  

  

• 先水平翻转
  
• 再对角线翻转
  

  复杂度：
  

• N 是 matrix 的边长
  
• 原地旋转
  时间复杂度：O(N^2)
  空间复杂度：O(1)
  
• 用翻转代替旋转
  时间复杂度：O(N^2)
  空间复杂度：O(1)
  

1. // 原地旋转
2. public void rotate(int[][] matrix) {
3.     int n = matrix.length;
4.     // 替换一半另一半就相当于自动替换过去了
5.     for (int i = 0; i < n / 2; i++) {
6.         // 内层要加一是因为n为奇数时需要多遍历一遍
7.         for (int j = 0; j < (n + 1) / 2; j++) {
8.             int temp = matrix[i][j];
9.             // 逆时针替换
10.             // 左上
11.             matrix[i][j] = matrix[n - j - 1][i];
12.             // 左下
13.             matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
14.             // 右下
15.             matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
16.             // 右上
17.             matrix[j][n - i - 1] = temp;
18.         }
19.     }
20. }

复制代码

1. // 用翻转代替旋转
2. public void rotate(int[][] matrix) {
3.     int n = matrix.length;
4.     // 重点: 先水平翻转
5.     for (int i = 0; i < matrix.length / 2; i++) {
6.         for (int j = 0; j < matrix[0].length; j++) {
7.             int temp = matrix[i][j];
8.             matrix[i][j] = matrix[n - i - 1][j];
9.             matrix[n - i - 1][j] = temp;
10.         }
11.     }
12.     // 重点: 再对角线翻转, 循环条件看作楼梯, 外层循环i=0则为对角线左侧楼梯顶层
13.     for (int i = 0; i < matrix.length; i++) {
14.         for (int j = 0; j < i; j++) {
15.             int temp = matrix[i][j];
16.             matrix[i][j] = matrix[j][i];
17.             matrix[j][i] = temp;
18.         }
19.     }
20. }

复制代码

  

  标题讲授：LeetCode
重点：
1.
  思路：
1.
  复杂度：

  

• 时间复杂度：
  
• 空间复杂度：
  

  [code][/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。