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);
                    }
                    else
                        return 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];
            }
        }
    }
};