36題.有效的數獨

????????此類問題特點是給出行列的多種限定條件，數獨限制每行每列每個小九宮格元素范圍為1-9且不可重復 。解決此類問題最簡單的想法就是使用哈希set，記錄每行，每列，每個小九宮格已經出現的元素。在遍歷矩陣時提前做出是否重復的判斷，若重復一次則直接退出遍歷返回假。

? ? ? ? 作為哈希set的優化可以使用多維數組存儲已經遍歷過的元素的數量，只要對應位置上的計數小于等于一則繼續遍歷，否則直接退出。本質是將遍歷到的元素根據其值大小轉換到一個對應的位置上，例如值為1，則將值為1的所有數據位置固定在0。建立多個多維數組跟蹤行、列、小九宮格的元素重復情況。

Note：對于小九宮格的定位為題是一個常見的套路，因為9乘9矩陣被劃分為3乘3的九宮格，所以可以使用[i? / 3][j / 3]去定位九宮格。

多維數組做法：

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {int colum[9][9], row[9][9], box[3][3][9];memset(colum, 0, sizeof(colum));memset(row, 0, sizeof(row));memset(box, 0, sizeof(box));for(int i = 0; i < 9; ++i){for(int j = 0; j < 9; ++j){char board_ij = board[i][j];if(board_ij != '.'){int tmp = board_ij - '0' - 1;++colum[j][tmp];++row[i][tmp];++box[i / 3][j / 3][tmp];if(colum[j][tmp] > 1 || row[i][tmp] > 1 || box[i / 3][j / 3][tmp] > 1)return false;}}}return true;}
};

哈希set：

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {vector<unordered_set<char>> row(9, unordered_set<char>());vector<unordered_set<char>> colum(9, unordered_set<char>());vector<vector<unordered_set<char>>> box(3, vector<unordered_set<char>>(3, unordered_set<char>()));for(int i = 0; i < 9; ++i){for(int j = 0; j < 9; ++j){char tmp = board[i][j];if(tmp != '.'){if(row[i].count(tmp) == 0 && colum[j].count(tmp) == 0 && box[i / 3][j / 3].count(tmp) == 0){row[i].insert(tmp);colum[j].insert(tmp);box[i / 3][j / 3].insert(tmp);}elsereturn false;}}}return true;}
};

54.螺旋矩陣

? ? ? ? 此類問題在實際場景中使用較多，例如旋轉圖片等。通常為順時針或者逆時針旋轉矩陣，做法很簡單。定義上下左右四個邊界，在模擬的過程中更新邊界即可。即保障先從左到右然后從上到下再者從右到左，最后從下到上。定義u(up) d(down) l(left) r(right)為其上下左右邊界，在模擬的過程中更新邊界即可。

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();int u = 0, d = m - 1, l = 0, r = n - 1;vector<int> res;while (true) {for (int i = l; i <= r; ++i)res.emplace_back(matrix[u][i]);if(++u > d) break;for (int i = u; i <= d; ++i)res.emplace_back(matrix[i][r]);if(--r < l) break;for (int i = r; i >= l; --i)res.emplace_back(matrix[d][i]);if(--d < u) break;for (int i = d; i >= u; --i)res.emplace_back(matrix[i][l]);if(++l > r) break;}return res;}
};

?48.旋轉圖像問題

? ? ? ? 此類問題需求是把一個矩陣旋轉某角度，需要進行坐標轉換即可輕松解決。也可以設計原地旋轉的算法。

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> help(matrix);for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){matrix[j][n - 1 -i] = help[i][j];}}}
};