首页 > 代码库 > Leetcode36--->Valid Sudoku(判断给定的数独是否有效)
Leetcode36--->Valid Sudoku(判断给定的数独是否有效)
题目：给定一个数独，某些部分已经被填上了数字，其余空的地方用‘.’表示；判断给定的数独是否有效；
数独规则： 每一行不能有重复的数字；每一列不能有重复的数字；将数独框划分为三行三列，没9个小方格不能有重复；
解题思路：
该题目不要判断整个数独是否有解，只需要判断当前给出的数独是否有效。因此只需要判断行和列是否有效，判断每个块是否有效。而判断一行中是否有重复的数字，最好的数据结构莫过于Set结构了。
使用rowSet,colSet两个Set结构来分别保存当前遍历的行和列，（i, j）表示行，则（j, i）就表示列。因此可以在判断第一行是否有效的同时，顺便判断第一列是否有效；块单独做检查；
代码如下：
1 public class Solution { 2 public boolean isValidSudoku(char[][] board) { 3 if(board == null || board.length < 9 || board[0].length < 9) 4 return false; 5 Set<Character> rowset = new HashSet<Character>(); 6 Set<Character> colset = new HashSet<Character>(); 7 8 for(int i = 0; i < 9; i++) 9 {10 rowset.clear();11 colset.clear();12 for(int j = 0; j < 9; j ++)13 {14 if(i % 3 == 0 && j % 3 == 0) // 检查块是否有效15 {16 if(!checkBlock(board, i, j))17 return false;18 }19 if(board[i][j] != ‘.‘) // 检查行是否有效20 {21 if(rowset.contains(board[i][j]))22 return false;23 rowset.add(board[i][j]);24 }25 if(board[j][i] != ‘.‘) // 检查列是否有效26 {27 if(colset.contains(board[j][i]))28 return false;29 colset.add(board[j][i]);30 }31 }32 }33 return true;34 35 }36 public boolean checkBlock(char[][] board, int row, int col) // 检查块是否有效37 {38 Set<Character> blockSet = new HashSet<Character>();39 for(int i = row; i < row + 3; i++)40 {41 for(int j = col; j < col + 3; j++)42 {43 if(board[i][j] != ‘.‘)44 {45 if(blockSet.contains(board[i][j]))46 return false;47 blockSet.add(board[i][j]);48 }49 }50 }51 return true;52 }53 }
Leetcode36--->Valid Sudoku(判断给定的数独是否有效)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。