18 矩阵置0 73

目录

• 73 矩阵置0
  
  
  
  • 思路
    
  • 具体实现
    
  
  
• 54 螺旋矩阵
  
  
  
  • 思路
    
  • 题解
    
    
    
    • 方法一：模拟机器人，修改数组
      
    • 方法二：继续优化，不修改数组
      
    
    
  
  
• 59 螺旋矩阵II
  
  
  
  • 题解
    
  
  

73 矩阵置0

思路

要求使用原地算法，那应该就是O(1)的空间复杂度。
那我曾经做过这道题，我有点印象，做法应该是
假如
1 1 1
1 0 1
1 1 1
我就先遍历
0 1
1 1
然后将0元素对应的0行元素和0列元素置0。
那这样做的话，还需要提前标记好第0行第0列是否需要清0。
具体实现

点击查看代码

1. class Solution {
2. public:
3.     void setZeroes(vector<vector<int>>& matrix) {
4.         int m = matrix.size(); //行
5.         int n = matrix[0].size(); //列
6.         bool row0flag = false, column0flag = false;
7.         for (int i = 0; i < n; ++i) {
8.             if (matrix[0][i] == 0)
9.                 row0flag = true;
10.         }
11.         for (int i = 0; i < m; ++i) {
12.             if (matrix[i][0] == 0)
13.                 column0flag = true;
14.         }
15.         for (int i = 1; i < m; ++i) {
16.             for (int j = 1; j < n; ++j) {
17.                 if (matrix[i][j] == 0) {
18.                     matrix[0][j] = 0;
19.                     matrix[i][0] = 0;
20.                 }
21.             }
22.         }
23.         for (int i = 1; i < m; ++i) {
24.             for (int j = 1; j < n; ++j) {
25.                 if (matrix[i][0] == 0 || matrix[0][j] == 0)           {
26.                     matrix[i][j] = 0; //清0
27.                 }
28.             }
29.         }
30.         if (row0flag) {
31.             for (int i = 0; i < n; ++i)
32.                 matrix[0][i] = 0;
33.         }
34.         if (column0flag) {
35.             for (int i = 0; i < m; ++i)
36.                 matrix[i][0] = 0;
37.         }
38.     }
39. };

复制代码

时间复杂度：\(O(n^{2})\)
空间复杂度：O(1)
54 螺旋矩阵

思路

这道题我好想也做过，但是已经忘记咋做的了。
外面的大循环循环几次呢，
这道题，，，，真的好恶心。
算了，不会写。
啊啊啊啊，感觉不行了。原来代码随想录那道题针对的是螺旋矩阵 II。不过话说回来，螺旋矩阵II咋写我也忘得差不多了。
题解

方法一：模拟机器人，修改数组

点击查看代码

1. class Solution {
2. public:
3.     vector<int> spiralOrder(vector<vector<int>>& matrix) {
4.         int m = matrix.size(); //行
5.         int n = matrix[0].size(); //列
6.         vector<int> ans(m*n);
7.         vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟向右向下向左向上
8.         int i = 0, j = 0, di = 0;
9.         for (int k = 0; k < m*n; ++k) {
10.             ans[k] = matrix[i][j];
11.             matrix[i][j] = INT_MAX; //已经被访问过
12.             int x = i + DIRS[di][0];
13.             int y = j + DIRS[di][1];
14.             if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) { //下一个位置越界吗？
15.                 di =  (di + 1) % 4; //右转
16.             }
17.             i += DIRS[di][0];
18.             j += DIRS[di][1];
19.         }
20.         return ans;
21.     }
22. };

复制代码

天哪，不得不说，灵神这个思路真的太好了！
方法二：继续优化，不修改数组

点击查看代码

1. class Solution {
2. public:
3.     vector<int> spiralOrder(vector<vector<int>>& matrix) {
4.         int m = matrix.size(); //行
5.         int n = matrix[0].size(); //列
6.         vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟机器人向右向下向左向上
7.         vector<int> ans;
8.         int i = 0, j = -1; //从这个点开始
9.         for (di = 0; ans.size() < m*n; di = (di + 1) % 4) { //外层循环控制方向
10.             for (int k = 0; k < n; ++k) { //第1次走n列步
11.                 i += DIRS[di][0];
12.                 j += DIRS[di][0];
13.                 ans.push_back(matrix[i][j]);
14.             }
15.             --m; //--行
16.             swap(m, n);
17.         }
18.         return ans;
19.     }
20. };

复制代码

方法二更神，愣是教我看了半个小时。
OK，做完这道题，我们明天再去试着去做螺旋数组II。
今天就做到这里吧，累了。2025-06-04 10:48:00 星期三
2025-06-05 08:44:39 星期四
下面我们尝试一下螺旋矩阵II
59 螺旋矩阵II

这道题看上去也能用上面的方法做，
点击查看代码

1. class Solution {
2. public:
3.     vector<vector<int>> generateMatrix(int n) {
4.         vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟机器人向右向下向左向上
5.         int m = n; //行
6.         vector<vector<int>> ans(m, vector<int>(n));
7.         int i = 0, j = -1;
8.         int size = m*n;
9.         for (int di = 0, step = 1; step <= size; di = (di + 1)%4) {
10.             for (int k = 0; k < n; ++k) {
11.                 i += DIRS[di][0];
12.                 j += DIRS[di][1];
13.                 ans[i][j] = step;
14.                 ++step;
15.             }
16.             --m;
17.             swap(m, n);
18.         }
19.         return ans;   
20.     }
21. };

复制代码

OK，这道题就先到这里吧。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！