X

LEETCODE 36. Valid Sudoku 解题思路分析

题目大意:

有效的数独

判断一个 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-36-valid-sudoku-解题思路分析/
Categories: leetcode
kwantong: