36. Valid Sudoku

题目

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

题目大意

给定一个二维数组代表数独,判断是否满足数独的定义,数独需要满足的规则有每一行1-9不能重复,每一列1-9不能重复,每一个块(一共3*3=9块)1-9不能重复. 点代表未知的任意数,

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int len = board.size();
        int used1[9][9]={0},used2[9][9]={0},used3[9][9]={0};
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<len;j++)
            {
                if(board[i][j]!='.')
                {
                    int num = board[i][j]-'0'- 1; //当前遍历到的数字.
                    int k = i / 3 * 3 + j / 3; //当前属于的区块,这里除3再乘3和原来不相等,因为除三只保留整数位.
                    if(used1[i][num]||used2[j][num]||used3[k][num])
                    {
                        return false;
                    }
                    used1[i][num]=1;
                    used2[j][num]=1;
                    used3[k][num]=1;    
                }
            }
        }
        return true;
    }
};

解答

使用哈希表,used1 表示判断每行,used2表示判断没列,used3表示判断每个块.

从上到下,从左到右,对每一个数进行遍历,i,j,k 分别代表当前遍历到的块走到了哪一个行,列,块.

有了就在对应的used标记为1,若有重复标记的1 .直接return false.