苏州网站建设代理渠道,游戏网官网,永嘉规划建设局网站,医疗器械解题思路 在 代码注释中#xff01; 文章目录 73. 矩阵置零54. 螺旋矩阵48. 旋转图像240. 搜索二维矩阵 II 73. 矩阵置零
class Solution {
public:void setZeroes(vectorvectorint matrix) {// 难点#xff1a;原地算法// 直接复用 matrix 第一行 和 …解题思路 在 代码注释中 文章目录 73. 矩阵置零54. 螺旋矩阵48. 旋转图像240. 搜索二维矩阵 II 73. 矩阵置零
class Solution {
public:void setZeroes(vectorvectorint 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:vectorint spiralOrder(vectorvectorint 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);vectorint 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(vectorvectorint 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(vectorvectorint 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;}
};