Leetcode-36. 有效的数独

36. 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 '.' 表示。

简单的想法就是按行，列，块三次遍历数组，确保有效。进一步可以一次迭代就可以，每次迭代时记录下行，列，块的已经看到的元素，（可以使用set记录）。然后遍历的时候如果看到之前的记录中有当前的数，就无效。需要注意的时，假设顺序为从左到右，从上到下，那么

• 第i行第j列的数就位于第(i/3)*3+j/3块，
• 第i块第j个数的行和列就分别为((i/3)*3+j/3, (i%3)*3+j%3)。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<set<char>> row(9);
        vector<set<char>> col(9);
        // 方块
        for (int i = 0; i < 9; ++i) {
            set<char> num;
            for (int j = 0; j < 9; ++j) {
                if (board[x][y] != '.') {
                    // i是第几个块，j是块内第几个数， x是第几行，y是第几列
                    int x = (i / 3) * 3 + j / 3;
                    int y = (i % 3) * 3 + j % 3;
                    if (row[x].find(board[x][y]) == row[x].end()) {
                        row[x].insert(board[x][y]);
                    } else {
                        return false;
                    }
                    if (col[y].find(board[x][y]) == col[y].end()) {
                        col[y].insert(board[x][y]);
                    } else {
                        return false;
                    }
                    if (num.find(board[x][y]) == num.end()) {
                        num.insert(board[x][y]);
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

这里面比较大的时间损耗在于set的查找，可以用一个二维数组来代替，比如创建一个二维数组row，第i行，第j列表示数独内第i行存不存在j+1这个数。这样会比较快。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][9] = {0};
        int col[9][9] = {0};
        int num[9][9] = {0};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                // i是第几行，j是第几列
                if (board[i][j] != '.') {
                    int cur_num = board[i][j] - '1';
                    if (row[i][cur_num]) {
                        return false;
                    }
                    if (col[j][cur_num]) {
                        return false;
                    }
                    int block = (i / 3) * 3 + j / 3;
                    if (num[block][cur_num]) {
                        return false;
                    }
                    row[i][cur_num] = 1;
                    col[j][cur_num] = 1;
                    num[block][cur_num] = 1;
                }
            }
        }
        return true;
    }
};

但在Leetcode上测试好像也没快多少_{_}。