36有效的数独

绝地灬酷狼 2021-06-22 15:38 404阅读 0赞

//判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。  
//  
// 数字 1-9 在每一行只能出现一次。  
// 数字 1-9 在每一列只能出现一次。  
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。  
//  
// 上图是一个部分填充的有效的数独。  
//  
// 数独部分空格内已填入了数字，空白格用 ‘.’ 表示。  
//  
// 示例 1:  
// 输入:  
//\[  
// \[“5”,“3”,".",".",“7”,".",".",".","."\],  
// \[“6”,".",".",“1”,“9”,“5”,".",".","."\],  
// \[".",“9”,“8”,".",".",".",".",“6”,"."\],  
// \[“8”,".",".",".",“6”,".",".",".",“3”\],  
// \[“4”,".",".",“8”,".",“3”,".",".",“1”\],  
// \[“7”,".",".",".",“2”,".",".",".",“6”\],  
// \[".",“6”,".",".",".",".",“2”,“8”,"."\],  
// \[".",".",".",“4”,“1”,“9”,".",".",“5”\],  
// \[".",".",".",".",“8”,".",".",“7”,“9”\]  
//\]  
//输出: true  
//  
// 示例 2:  
// 输入:  
//\[  
// \[“8”,“3”,".",".",“7”,".",".",".","."\],  
// \[“6”,".",".",“1”,“9”,“5”,".",".","."\],  
// \[".",“9”,“8”,".",".",".",".",“6”,"."\],  
// \[“8”,".",".",".",“6”,".",".",".",“3”\],  
// \[“4”,".",".",“8”,".",“3”,".",".",“1”\],  
// \[“7”,".",".",".",“2”,".",".",".",“6”\],  
// \[".",“6”,".",".",".",".",“2”,“8”,"."\],  
// \[".",".",".",“4”,“1”,“9”,".",".",“5”\],  
// \[".",".",".",".",“8”,".",".",“7”,“9”\]  
//\]  
//输出: false  
//解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。  
// 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。  
//  
// 说明:  
//  
// 一个有效的数独（部分已被填充）不一定是可解的。  
// 只需要根据以上规则，验证已经填入的数字是否有效即可。  
// 给定数独序列只包含数字 1-9 和字符 ‘.’ 。  
// 给定数独永远是 9x9 形式的。  
//  
// Related Topics 哈希表

*  思路1：两层循环判断，判断每一个元素是否合法

class Solution { 
    	public boolean isValidSudoku(char[][] board) { 
    		if (board == null || board.length == 0) return false;
    		return solve(board);
    	}
    
    	public boolean solve(char[][] board) { 
    		// board.length为数独的行数，二维数组的长度和一维数组一样，只不过每个元素都是一个数组
    		for (int i = 0; i < board.length; i++) { 
    			for (int j = 0; j < board[0].length; j++) { 
    				if (board[i][j] != '.') {   // 如果没有填入数字（char是基本类型，用==比较）
    					if (!isValid(board, i, j, board[i][j])) { 
    						return false;
    					}
    				}
    			}
    		}
    		return true;
    	}
    
    	//判断当前row-col的元素是否合法
    	private boolean isValid(char[][] board, int row, int col, char c) { 
    		for (int i = 0; i < 9; i++) { 
    			if (board[i][col] != '.' && i != row && board[i][col] == c) return false; // 看看当前行中有没有与c重复的,i != row用来排除本身
    			if (board[row][i] != '.' && i != col && board[row][i] == c) return false; // 看看当前列中有没有与c重复的,i != col用来排除本身
    			if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && (3 * (row / 3) + i / 3) != row && (3 * (col / 3) + i % 3) != col && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
    				return false;
    			//看看当前3*3中有没有与c重复的，(3 * (row / 3) + i / 3) != row && (3 * (col / 3) + i % 3) != col用来排除自身， 3 * (row / 3)
    			// 和3 *(col / 3)可以计算出当前row，col所在的九宫格的左上角的坐标，i/3可以每三个固定行，i%3 列向前遍历
    		}
    		return true;
    	}
    }