题目大意：
有效的数独
判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 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 和字符 ‘.’ 。
- 给定数独永远是 9×9 形式的。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=36
解题思路分析：
本题难度并不大，我们分别查看每一行，每一列以及每一个3乘3的小格子中是否存在相同的数字即可。
实现代码：
public boolean isValidSudoku(char[][] board) {
// 循环每一行
for(int r=0;r<9;r++){
// 记录当前行存在的数字
boolean[] has=new boolean[9];
// 循环当前行每一个数字
for(int c=0;c<9;c++){
char ch = board[r][c];
if(ch=='.') continue; // 如果不是数字，跳过
// 如果出现相同数字，直接返回false
if(has[ch-'1']) return false;
// 将当前数字标记为存在
has[ch-'1']=true;
}
}
// 循环每一列
for(int c=0;c<9;c++){
boolean[] has=new boolean[9];
for(int r=0;r<9;r++){
char ch = board[r][c];
if(ch=='.') continue;
if(has[ch-'1']) return false;
has[ch-'1']=true;
}
}
// 循环每一小格子
for(int r=0;r<=2;r++){
for(int c=0;c<=2;c++){
boolean[] has=new boolean[9];
// 循环小格子里每一点
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
char ch = board[r*3+i][c*3+j];
if(ch=='.') continue;
if(has[ch-'1']) return false;
has[ch-'1']=true;
}
}
}
}
return true;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Sudoku.
Memory Usage: 41.2 MB, less than 97.10% of Java online submissions for Valid Sudoku.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-36-valid-sudoku-解题思路分析/