本文共 4809 字，大约阅读时间需要 16 分钟。

Determine if a Sudoku is valid, according to: .

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

题意大意和注意事项是：提供一个数独，证明是否有效。有效的含义：已被填充的部分不存在对应行、列、九宫格有重复的数字。未填充的部分在本题用符号点 ‘.’ 来代替。另外，此题不需要考虑是否有解，你只需要注意有没有重复就行了。需要另外注意的是，如图中所示，九宫格只需要看九个粗线九宫格。

显然，暴力求解。第一想法是一行一行一列一列一块一块判断。为减少步骤，则沿着对角线以第 i 行第 i 列所在一行一列来判断，

每当 i 是3的倍数时，即可顺便判断三块九宫格。由于数独要考虑到重复性，故采用了哈希表。代码如下：

public class Solution {
       public boolean isValidSudoku(char[][] board) {        for(int i = 0; i < 9; i++) {            Set
   
     rowSet = new HashSet
    
      ();            Set
     
       colSet = new HashSet
      
        ();            Set
       
         boxSet = new HashSet
        
          (); for(int j = 0; j < 9; j++) { char c = board[i][j]; if((i + 1) % 3 == 0 && (j + 1) % 3 == 0) { for(int k = 0; k < 3; k++) { for(int l = 0; l < 3; l++) { char temp = board[i - k][j - l]; if(temp != '.') { if(!boxSet.contains(temp)) boxSet.add(temp); else return false; } } } boxSet.clear(); } if(c != '.') { if(!rowSet.contains(c)) rowSet.add(c); else return false; } c = board[j][i]; if(c != '.') { if(!colSet.contains(c)) colSet.add(c); else return false; } } rowSet.clear();; colSet.clear(); } return true; } }
        
       
      
     
    
   

上述代码运行后时间较长，达到了11ms，这是因为哈希表的操作相对耗时。以下是针对上述代码的性能优化分析： 1. 利用 boolean 数组 new 出来后默认是 false 以及数组下标可与数独数字对应的特点，用 boolean 数组来替代哈希表。一旦出现了1~9就将对应位置设为 true，再次出现，显然对应位置为 true，证明重复，return false。 2. 上述代码为了整洁使用了 c 来做中间变量，但是实际上是多绕了一个弯，因为由于数组是直接从内存读取，读取数组是不耗费时间的。 3. 一开始将代码改为数组时，由于每次大循环后都要重新将数组内的值设为 false。一开始使用 Arrays.fill() 来设为 false，然而可以想象这个函数内部实际上也进行了一次循环。所以干脆直接 new。 4. i 和 j 对3取模那里复杂了，没必要加1。

通过上述几个做法分析改进后，运行时间一下子到了4ms。参考代码如下：

public class Solution {
       public boolean isValidSudoku(char[][] board) {        for(int i = 0; i < 9; i++) {            boolean [] rowContains = new boolean[9];            boolean [] colContains = new boolean[9];            boolean [] boxContains = new boolean[9];            for(int j = 0; j < 9; j++) {                if(i % 3 == 2 && j % 3 == 2) {                    for(int k = 0; k < 3; k++) {                        for(int l = 0; l < 3; l++) {                            char temp = board[i - k][j - l];                            if(temp != '.') {                                if(!boxContains[temp - '1']) boxContains[temp - '1'] = true;                                else return false;                            }                        }                    }                    boxContains = new boolean[9];                }                if(board[i][j] != '.') {                    if(!rowContains[board[i][j] - '1']) rowContains[board[i][j] - '1'] = true;                    else return false;                }                if(board[j][i] != '.') {                    if(!colContains[board[j][i] - '1']) colContains[board[j][i] - '1'] = true;                    else return false;                }            }        }        return true;    }}

继续观察上述代码，可以发现还能优化： 1. 在上述对九宫格的判断中，实际上可以在对行判断中进行，多 new 出来两个boolean 数组共三个数组用于判断每三行的九宫格。 2. 可以发现，在取数组值时每次减 ‘1’ 其实是重复计算，太影响效率了，所以我们可以将减 ‘1’ 的值用变量保存起来。节省时间。

经过这一次优化，时间降到了3ms，beats 89%。第三次优化的代码如下：

public class Solution {
       public boolean isValidSudoku(char[][] board) {        boolean [] boxContains0 = new boolean[9];        boolean [] boxContains1 = new boolean[9];        boolean [] boxContains2 = new boolean[9];        for(int i = 0; i < 9; i++) {            boolean [] rowContains = new boolean[9];            boolean [] colContains = new boolean[9];            for(int j = 0; j < 9; j++) {                int loc = board[i][j] - '1';                if(board[i][j] != '.') {                    int temp = j / 3;                    if(temp == 0) {                        if(!boxContains0[loc]) boxContains0[loc] = true;                        else return false;                    } else if(temp == 1) {                        if(!boxContains1[loc]) boxContains1[loc] = true;                        else return false;                    } else if(temp == 2) {                        if(!boxContains2[loc]) boxContains2[loc] = true;                        else return false;                    }                    if(!rowContains[loc]) rowContains[loc] = true;                    else return false;                }                loc = board[j][i] - '1';                if(board[j][i] != '.') {                    if(!colContains[loc]) colContains[loc] = true;                    else return false;                }            }            if(i % 3 == 2) {                boxContains0 = new boolean[9];                boxContains1 = new boolean[9];                boxContains2 = new boolean[9];            }        }        return true;    }}

如果有其他性能优化方法，欢迎评论指出。

转载地址：http://tnjgj.baihongyu.com/