73.矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：输入：matrix = [
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：[
[1,0,1],
[0,0,0],
[1,0,1]
]示例 2：输入：matrix = [
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
] 输出：[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
分析:
1.我们先扫描一遍矩阵, 并用引入两个额外的数组去标记, 这行和这列是否存在过 0
2.然后再扫描一遍矩阵, 如果存在这行或者这列为 0 的情况, 那么全部标记为 0
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<bool> rowHasZeroFlag(m, false);
vector<bool> colHasZeroFlag(n, false);
for (int i = 0; i < m; ++i) {
for (int j = 0 ; j < n; ++j) {
if (matrix[i][j] == 0) {
rowHasZeroFlag[i] = true;
colHasZeroFlag[j] = true;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0 ; j < n; ++j) {
if (rowHasZeroFlag[i] || colHasZeroFlag[j]) {
matrix[i][j] = 0;
}
}
}
return;
}
};
54.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：输入：
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
] 输出：[1,2,3,6,9,8,7,4,5]示例 2：输入：
matrix = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
分析:
1.模拟旋转的过程, 维护上下左右四个终极边界, left, right, top, bottom, 然后在旋转过程中缩小边界, 直到边界发生某种重合; 向右和向下是必有的, 但是有时候向左和向上不是必须的, 因此需要一个判断; 判断可以回转的情况是两个边界不重合, 也就是 left < right && top < bottom
2.每次单项移动的时候, 都是卡着一个边界去移动
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if (matrix.size() == 0 || matrix[0].size() == 0) {
return ans;
}
int rowNum = matrix.size();
int colNum = matrix[0].size();
// left/right/top/bottom 模拟当前可执行螺旋的四个方向的边界
int left = 0;
int right = colNum - 1;
int top = 0;
int bottom = rowNum - 1;
while (left <= right && top <= bottom) {
for (int c = left; c <= right; ++c) {
ans.push_back(matrix[top][c]);
}
for (int r = top + 1; r <= bottom; ++r) {
ans.push_back(matrix[r][right]);
}
// 在需要缩小的情况下
if (left < right && top < bottom) {
// 先往左缩小
for (int c = right - 1; c > left; --c) {
ans.push_back(matrix[bottom][c]);
}
// 再向上缩小
for (int r = bottom; r > top; --r) {
ans.push_back(matrix[r][left]);
}
}
// 缩小一圈边界
++left;
--right;
++top;
--bottom;
}
return ans;
}
};
转载请注明来源 goldandrabbit.github.io