Leetcode 矩阵问题

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];}}}
};