LeetCode: Valid Sudoku 解题报告-白红宇

LeetCode: Valid Sudoku 解题报告

阅读量：5168 次

发布时间：2019-06-13

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

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

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

A partially filled sudoku which is valid.

Note:

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

SOLUTION:

使用HashSet 行列，9块分别检查。

1 public class Solution { 2     public boolean isValidSudoku(char[][] board) { 3         if (board == null || board.length != 9 || 4             board[0].length != 9) { 5             return false; 6         } 7          8         HashSet
      
        set = new HashSet
       
        (); 9         10         // check the rows.11         for (int i = 0; i < 9; i++) {12             // clear the set at every row.13             set.clear();14             for (int j = 0; j < 9; j++) {15                 if (!isValidChar(board[i][j], set)) {16                     return false;17                 }18             }19         }20         21         // check the columns.22         for (int i = 0; i < 9; i++) {23             // clear the set at every column.24             set.clear();25             for (int j = 0; j < 9; j++) {26                 if (!isValidChar(board[j][i], set)) {27                     return false;28                 }29             }30         }31         32         // check the blocks.33         for (int i = 0; i < 9; i+=3) {34             for (int j = 0; j < 9; j+=3) {35                 // clear the set at every block.36                 set.clear();37                 for (int k = 0; k < 9; k++) {38                     if (!isValidChar(board[i + k / 3][j + k % 3], set)) {39                         return false;40                     }    41                 }42             }43         }44         45         return true;46     }47     48     public boolean isValidChar(char c, HashSet
        
          set) {49         if (c == '.') {50             return true;51         }52         53         if (c < '0' || c > '9') {54             return false;55         }56         57         // Check if the character exit in the hashset.58         if (set.contains(c)) {59             return false;60         }61         62         set.add(c);63         64         return true;65     }66 }

View Code

2013.1.13 redo:

1 public class Solution { 2     public boolean isValidSudoku(char[][] board) { 3         // 2:03 4         if (board == null || board.length == 0 || board[0].length == 0) { 5             return false; 6         } 7          8         int rows = board.length; 9         int cols = board[0].length;10         11         // exam the rows.12         for (int i = 0; i < rows; i++) {13             HashSet
      
        set = new HashSet
       
        ();14             for (int j = 0; j < cols; j++) {15                 char c = board[i][j];16                 if (c != '.') {17                     if (set.contains(c)) {18                         return false;19                     }20                     set.add(c);21                 }22             }23         }24         25         // exam the cols.26         for (int i = 0; i < cols; i++) {27             HashSet
        
          set = new HashSet
         
          ();28             for (int j = 0; j < rows; j++) {29                 // bug 1: should use board[j][i]30                 char c = board[j][i];31                 if (c != '.') {32                     if (set.contains(c)) {33                         return false;34                     }35                     set.add(c);36                 }37             }38         }39         40         // examp the square.41         for (int i = 0; i < rows; i += 3) {42             for (int j = 0; j < cols; j += 3) {43                 HashSet
          
            set = new HashSet
           
            ();44 for (int k = 0; k < 9; k++) {45 char c = board[i + k / 3][j + k % 3];46 if (c == '.') {47 continue;48 }49 50 if (set.contains(c)) {51 return false;52 }53 set.add(c);54 }55 }56 }57 58 return true;59 }60 }