【LeetCode 热题 100】矩阵 专题（大多原地算法，需要一定思维）

解题思路 在 代码注释中！

73. 矩阵置零

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {// 难点：原地算法// 直接复用 matrix 第一行 和 第一列，但是会 覆盖， 所以  单独两个变量 记录 第一行，第一列// 单独两个变量 记录 第一行，第一列int r0 = 1, c0 = 1;int n = matrix.size(), m = matrix[0].size();for(int j = 0;j < m;j ++ ) {if(matrix[0][j] == 0) r0 = 0;}for(int i = 0;i < n;i ++ ){if(matrix[i][0] == 0) c0 = 0;}for(int i = 1;i < n;i ++ ){for(int j = 0; j < m;j ++ ){if(matrix[i][j] == 0) matrix[0][j] = matrix[i][0] = 0;}}// 置0for(int j = 1; j < m;j ++ ){if(matrix[0][j] == 0){for(int i = 0;i < n;i ++ ) matrix[i][j] = 0;}}for(int i = 1;i < n;i ++ ){if(matrix[i][0] == 0){for(int j = 0;j < m;j ++ ) matrix[i][j] = 0;}}// 单独的行列if(!r0)for(int j = 0;j < m;j ++ ) matrix[0][j] = 0;if(!c0)for(int i = 0;i < n;i ++ ) matrix[i][0] = 0;}
};

54. 螺旋矩阵

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {// 方向矢量 模拟int n = matrix.size(), m = matrix[0].size();int k = 0;int dx[4] = {-1,0,1,0}, dy[] = {0,1,0,-1};bool st[n][m];memset(st, 0, sizeof st);vector<int> res;int x = 0, y = 0, d = 1;int a, b;while(k < n * m){res.push_back(matrix[x][y]);st[x][y] = true;int a = x + dx[d], b = y + dy[d];if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;k ++ ;}return res;}
};

48. 旋转图像

class Solution {
public:void rotate(vector<vector<int>>& matrix) {// 原地算法// 先 对角线翻转(=顺时针180)， 然后 左右翻转（=逆时针90） = 顺时针旋转 90 度int n = matrix.size(), m = matrix[0].size();// 对角线 翻转for(int i = 0;i < n;i ++ ){for(int j = 0;j < i;j ++ ){swap(matrix[i][j], matrix[j][i]);}}// 左右翻转for(int i = 0; i < n;i ++ ){for(int j = 0, k = m - 1; j < k;j ++ , k -- ) swap(matrix[i][j], matrix[i][k]);}}
};

240. 搜索二维矩阵 II

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {// 从右上角开始 搜索int n = matrix.size(), m = matrix[0].size();int i = 0, j = m - 1;while(i < n && j >= 0){if(target > matrix[i][j]) i ++ ;else if(target < matrix[i][j]) j -- ;else if(target == matrix[i][j]) return true;}return false;}
};