首页 > 代码库 > leetcode第35题--Valid Sudoku

leetcode第35题--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.小时候玩过这些游戏,要是给定元素解九宫格就比较负责了。这题只是要我们判断是否符合。

思路是这样的,就是判断来一个数的时候,它所在的行和列还有子九宫是否有和它重复的,如果有就判断输出非法,否则一直进行到最后。都没有非法元素,那就输出true。

开辟三个9*9的bool,分别代表行row,列col,和子九宫subSudo,来一个数,例如5那么就在相应的row的5-1里面记录true,在col的5-1个里面记录true,在相应子九宫里面记录true。当然在记录true之前要判断是否为false,如果已经是true了就说明之前已经填入过了,那就重复了,输出非法。

关于子九宫的表示,我看了个说用i - i % 3 + j / 3,好复杂,其实自己推一下,用3*(i/3) + (j/3)就很好理解,话一个3*3的,相应的0到8,然后和i/3,j/3的关系一目了然。

如果是用java,那么三个9*9的bool是默认初始为false的,可以不用再初始化,如果用的是c++,那么注意了,需要对三个boo数组进行初始化,可以用两个for到9来初始化,也可以使用memset。

class Solution {public:    bool isValidSudoku(vector<vector<char> > &board)     {        bool row[9][9], col[9][9], subSudo[9][9];        memset(row, false, sizeof(row));        memset(col, false, sizeof(col));        memset(subSudo, false, sizeof(subSudo));        for (int i = 0; i < 9; ++i)            for (int j = 0; j < 9; ++j)            {                if (board[i][j] == ‘.‘)                    continue;                int c = board[i][j] - ‘1‘; // 注意了是 减一 因为下标是从0开始的                if (row[i][c] || col[j][c] || subSudo[3*(i/3) + (j/3)][c])                    return false;                row[i][c] = col[j][c] = subSudo[3*(i/3) + (j/3)][c] = true;            }        return true;    }};

 

leetcode第35题--Valid Sudoku