问题描述
https://leetcode.com/problems/valid-sudoku/
解决思路
遍历对每一行判断；遍历对每一列判断；遍历对每3*3的小方块内部遍历
问题解惑
- row < (i / 3) * 3 + 3是什么意思？ 更具i从0~9，(i / 3) * 3 + 3的结果依次是：3-3-3-6-6-6-9-9-9。这将i=0~3的时候，row限制在前三个小方框内；i=4~6的时候，限制在后一个的三个小方框内;i=7~9的时候，限制在最后三个小方框内。j同理。结果就是，双层for循环共同作用，将i和j限制在每一个3*3的小方框内。
代码
class Solution {
public boolean isValidSudoku(char[][] board) {
//corner case
if(board.length < 9 || board == null) return false;
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
//only numbers filled in the blank need to be validated
if(board[i][j] == '.') continue;
if(!valid(board, i ,j)) return false;
}
}
return true;
}
public boolean valid(char[][] board, int i, int j){
//to verify every row
for(int row = 0; row < (i / 3) * 3 + 3; row++){
//comes to i itself, end this loop
if(row == i) continue;
//another same number occurs in the same row
if(board[row][j] == board[i][j]) return false;
}
//to verify every colloum
for(int col = 0; col < (j / 3) * 3 + 3; col++){
//comes to j itself, end this loop
if(col == j) continue;
//another same number occurs in the same colloum
if(board[i][col] == board[i][j]) return false;
}
//to verify the 3*3 cubes
for(int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++){
for(int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++ ){
//comes to (i,j) itself, end this loop
if(row == i && col == j) continue;
//anther same number occurs in the same 3*3 cube
if(board[row][col] == board[i][j]) return false;
}
}
return true;
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
