東莞住建局投訴電話是多少南寧seo平臺(tái)標(biāo)準(zhǔn)
解題思路 在 代碼注釋中！
文章目錄
- 73. 矩陣置零
- 54. 螺旋矩陣
- 48. 旋轉(zhuǎn)圖像
- 240. 搜索二維矩陣 II
73. 矩陣置零
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {// 難點(diǎn)：原地算法// 直接復(fù)用 matrix 第一行 和 第一列，但是會(huì) 覆蓋， 所以 單獨(dú)兩個(gè)變量 記錄 第一行，第一列// 單獨(dú)兩個(gè)變量 記錄 第一行，第一列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;}}// 單獨(dú)的行列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. 旋轉(zhuǎn)圖像
class Solution {
public:void rotate(vector<vector<int>>& matrix) {// 原地算法// 先 對(duì)角線翻轉(zhuǎn)(=順時(shí)針180)， 然后 左右翻轉(zhuǎn)（=逆時(shí)針90） = 順時(shí)針旋轉(zhuǎn) 90 度int n = matrix.size(), m = matrix[0].size();// 對(duì)角線 翻轉(zhuǎn)for(int i = 0;i < n;i ++ ){for(int j = 0;j < i;j ++ ){swap(matrix[i][j], matrix[j][i]);}}// 左右翻轉(zhuǎn)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;}
};