首页 > 代码库 > 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