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。
具体实现
点击查看代码class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(); //行
int n = matrix.size(); //列
bool row0flag = false, column0flag = false;
for (int i = 0; i < n; ++i) {
if (matrix == 0)
row0flag = true;
}
for (int i = 0; i < m; ++i) {
if (matrix == 0)
column0flag = true;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix == 0) {
matrix = 0;
matrix = 0;
}
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix == 0 || matrix == 0) {
matrix = 0; //清0
}
}
}
if (row0flag) {
for (int i = 0; i < n; ++i)
matrix = 0;
}
if (column0flag) {
for (int i = 0; i < m; ++i)
matrix = 0;
}
}
};时间复杂度：\(O(n^{2})\)
空间复杂度：O(1)
54 螺旋矩阵
思路
这道题我好想也做过，但是已经忘记咋做的了。
外面的大循环循环几次呢，
这道题，，，，真的好恶心。
算了，不会写。
啊啊啊啊，感觉不行了。原来代码随想录那道题针对的是螺旋矩阵 II。不过话说回来，螺旋矩阵II咋写我也忘得差不多了。
题解
方法一：模拟机器人，修改数组
点击查看代码class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(); //行
int n = matrix.size(); //列
vector<int> ans(m*n);
vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟向右向下向左向上
int i = 0, j = 0, di = 0;
for (int k = 0; k < m*n; ++k) {
ans = matrix;
matrix = INT_MAX; //已经被访问过
int x = i + DIRS;
int y = j + DIRS;
if (x < 0 || x >= m || y < 0 || y >= n || matrix == INT_MAX) { //下一个位置越界吗？
di =(di + 1) % 4; //右转
}
i += DIRS;
j += DIRS;
}
return ans;
}
};天哪，不得不说，灵神这个思路真的太好了！
方法二：继续优化，不修改数组
点击查看代码class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(); //行
int n = matrix.size(); //列
vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟机器人向右向下向左向上
vector<int> ans;
int i = 0, j = -1; //从这个点开始
for (di = 0; ans.size() < m*n; di = (di + 1) % 4) { //外层循环控制方向
for (int k = 0; k < n; ++k) { //第1次走n列步
i += DIRS;
j += DIRS;
ans.push_back(matrix);
}
--m; //--行
swap(m, n);
}
return ans;
}
};方法二更神，愣是教我看了半个小时。
OK，做完这道题，我们明天再去试着去做螺旋数组II。
今天就做到这里吧，累了。2025-06-04 10:48:00 星期三
2025-06-05 08:44:39 星期四
下面我们尝试一下螺旋矩阵II
59 螺旋矩阵II
这道题看上去也能用上面的方法做，
点击查看代码class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //模拟机器人向右向下向左向上
int m = n; //行
vector<vector<int>> ans(m, vector<int>(n));
int i = 0, j = -1;
int size = m*n;
for (int di = 0, step = 1; step <= size; di = (di + 1)%4) {
for (int k = 0; k < n; ++k) {
i += DIRS;
j += DIRS;
ans = step;
++step;
}
--m;
swap(m, n);
}
return ans;
}
};OK，这道题就先到这里吧。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]