36. 有效的數(shù)獨(dú)

LeetCode_link

---

請(qǐng)你判斷一個(gè) 9 x 9 的數(shù)獨(dú)是否有效。只需要 根據(jù)以下規(guī)則 ，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。（請(qǐng)參考示例圖）

注意：
一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。
只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
空白格用 '.' 表示。

示例 1：

輸入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

輸出：true

示例 2：

輸入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

輸出：false
解釋：除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。 但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無效的。

提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位數(shù)字（1-9）或者 '.'

---

思路：統(tǒng)計(jì)數(shù)字的出現(xiàn)次數(shù)，一旦出現(xiàn)超過一次，就失敗。注意這個(gè)題不需要判斷題是否有解。

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {int rows[9][9] = {0};int cols[9][9] = {0};int inside[9][9] = {0};for(int i = 0; i < 9; i ++){for(int j = 0; j < 9; j++){if(board[i][j] < '0' || board[i][j] > '9')  continue;int num = board[i][j] - '0';//行if(rows[i][num - 1] > 0){return false;}else{rows[i][num - 1] ++;}//列if(cols[j][num - 1] > 0){return false;}else{cols[j][num - 1] ++;}//內(nèi)if(inside[(i/3)*3 + j/3][num - 1] > 0){return false;}else{inside[(i/3)*3 + j/3][num - 1] ++;}}}return true;}
};

54. 螺旋矩陣

LeetCode_link

---

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

示例 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]

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

---

思路：一圈圈來

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int row = matrix.size(), col = matrix[0].size();int circle = min((row + 1) / 2, (col + 1) / 2);vector<int> temp, rec;for(int i = 0; i < circle; i++){temp = one_circle(matrix ,row, col, i);rec.insert(rec.end(), temp.begin(), temp.end());}return rec;}vector<int> one_circle(vector<vector<int>>& matrix, int row, int col, int circle){int i = circle, j = circle;vector<int> rec;rec.push_back(matrix[i][j]);while(j < col - circle - 1){ //向右j ++;rec.push_back(matrix[i][j]);}while(i < row - circle - 1){ //向下i ++;rec.push_back(matrix[i][j]);}while(row - circle * 2 >= 2 && j > circle){ //向左（如果行是1，就不走了）j --;rec.push_back(matrix[i][j]);}while(col - circle * 2 >= 2 && i > circle + 1){ //向上（如果列是1，就不走了）i --;rec.push_back(matrix[i][j]);}return rec;}
};

48. 旋轉(zhuǎn)圖像

LeetCode_link

---

給定一個(gè) n × n 的二維矩陣 matrix 表示一個(gè)圖像。請(qǐng)你將圖像順時(shí)針旋轉(zhuǎn) 90 度。

你必須在 原地 旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要 使用另一個(gè)矩陣來旋轉(zhuǎn)圖像。

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

輸入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
輸出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

---

思路：四角旋轉(zhuǎn)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int row = matrix.size();int circle = ceil((row + 1) / 2);for(int i = 0; i < circle; i ++){turn_one_circle(matrix, row, i);}}void turn_one_circle(vector<vector<int>>& matrix, int row, int circle){int temp;row -= 1;for(int i = 0; i < row - circle * 2; i++){temp = matrix[circle][circle + i];matrix[circle][circle + i] = matrix[row - circle - i][circle];matrix[row - circle - i][circle] = matrix[row - circle][row - circle - i];matrix[row - circle][row - circle - i] = matrix[circle + i][row - circle];matrix[circle + i][row - circle] = temp;}}
};

也可以先水平旋轉(zhuǎn)，再主對(duì)角線旋轉(zhuǎn)

73. 矩陣置零

LeetCode_link

---

給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0 ，則將其所在行和列的所有元素都設(shè)為 0 。請(qǐng)使用 原地 算法。

示例 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]]

提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

---

思路：使用標(biāo)記數(shù)組，一個(gè)記錄行，一個(gè)記錄列

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<int> row(m);vector<int> col(n);for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(matrix[i][j] == 0){row[i] = 1;col[j] = 1;}}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(row[i] == 1 || col[j] == 1){matrix[i][j] = 0;}}}}
};

289. 生命游戲

LeetCode_link

---

根據(jù) 百度百科 ， 生命游戲 ，簡(jiǎn)稱為 生命 ，是英國(guó)數(shù)學(xué)家約翰·何頓·康威在 1970 年發(fā)明的細(xì)胞自動(dòng)機(jī)。

給定一個(gè)包含 m × n 個(gè)格子的面板，每一個(gè)格子都可以看成是一個(gè)細(xì)胞。每個(gè)細(xì)胞都具有一個(gè)初始狀態(tài)： 1 即為 活細(xì)胞 （live），或 0 即為 死細(xì)胞 （dead）。每個(gè)細(xì)胞與其八個(gè)相鄰位置（水平，垂直，對(duì)角線）的細(xì)胞都遵循以下四條生存定律：

1. 如果活細(xì)胞周圍八個(gè)位置的活細(xì)胞數(shù)少于兩個(gè)，則該位置活細(xì)胞死亡；
2. 如果活細(xì)胞周圍八個(gè)位置有兩個(gè)或三個(gè)活細(xì)胞，則該位置活細(xì)胞仍然存活；
3. 如果活細(xì)胞周圍八個(gè)位置有超過三個(gè)活細(xì)胞，則該位置活細(xì)胞死亡；
4. 如果死細(xì)胞周圍正好有三個(gè)活細(xì)胞，則該位置死細(xì)胞復(fù)活；

下一個(gè)狀態(tài)是通過將上述規(guī)則同時(shí)應(yīng)用于當(dāng)前狀態(tài)下的每個(gè)細(xì)胞所形成的，其中細(xì)胞的出生和死亡是同時(shí)發(fā)生的。給你 m x n 網(wǎng)格面板 board 的當(dāng)前狀態(tài)，返回下一個(gè)狀態(tài)。

示例 1：

輸入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
輸出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

輸入：board = [[1,1],[1,0]]
輸出：[[1,1],[1,1]]

提示：
m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 為 0 或 1

---

思路：使用額外的數(shù)組

class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int m = board.size(), n = board[0].size();int rec[m][n];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int live = live_cell(board, i, j);if(board[i][j] == 1){if(live < 2)    rec[i][j] = 0;if(live == 2 || live == 3)  rec[i][j] = 1;if(live > 3)    rec[i][j] = 0;}else{if(live == 3){rec[i][j] = 1;}else{rec[i][j] = 0;}}}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){board[i][j] = rec[i][j];}}}int live_cell(vector<vector<int>> board, int now_i, int now_j){int m = board.size(), n = board[0].size();int row[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int col[8] = {-1, 0, 1, -1, 1, -1, 0, 1};int count = 0;for(int k = 0; k < 8; k++){if(now_i + row[k] >= 0 && now_i + row[k] < m && now_j + col[k] >= 0 && now_j + col[k] < n){if(board[now_i + row[k]][now_j + col[k]] == 1){count ++;}}}return count;}
};

思路：不使用額外的數(shù)組，但是使用額外的標(biāo)記，-1本死但活，2本活但死

class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int m = board.size(), n = board[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int live = live_cell(board, i, j);if(board[i][j] == 1){if(live < 2)    board[i][j] = 2;if(live == 2 || live == 3)  board[i][j] = 1;if(live > 3)    board[i][j] = 2;}else{if(live == 3){board[i][j] = -1;}else{board[i][j] = 0;}}}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == -1)   board[i][j] = 1;if(board[i][j] == 2)   board[i][j] = 0;}}}int live_cell(vector<vector<int>> board, int now_i, int now_j){int m = board.size(), n = board[0].size();int row[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int col[8] = {-1, 0, 1, -1, 1, -1, 0, 1};int count = 0;for(int k = 0; k < 8; k++){if(now_i + row[k] >= 0 && now_i + row[k] < m && now_j + col[k] >= 0 && now_j + col[k] < n){if(board[now_i + row[k]][now_j + col[k]] >= 1){count ++;}}}return count;}
};