首页 > 代码库 > Leetcode: Valid Sudoku

Leetcode: Valid Sudoku

2024-07-03 22:22:19   218人阅读

犯了很多细节上的错误，比如忽视了“-”的存在，正是因为有“-”的存在，所以不能用if (rows.size() == i)来判断rows里面是否已经存某一行，如果不存在再row = new ArrayList<Character>(); row.add(board[i][j]);rows.add(row);来添加新的一行。所以只能一开头就不辞辛苦地建一个ArrayList<ArrayList<Character>> rows，再循环九次向里面添加9个空的ArrayList<Character> row

 1 public class Solution {
 2     public boolean isValidSudoku(char[][] board) {
 3         ArrayList<ArrayList<Character>> rows = new ArrayList<ArrayList<Character>>();
 4         ArrayList<ArrayList<Character>> columns = new ArrayList<ArrayList<Character>>();
 5         ArrayList<ArrayList<Character>> boxes = new ArrayList<ArrayList<Character>>();
 6         ArrayList<Character> row, column, box;
 7         for (int r=0; r<9; r++){
 8             row = new ArrayList<Character>();
 9             rows.add(row);
10         }
11         for (int c=0; c<9; c++){
12             column = new ArrayList<Character>();
13             columns.add(column);
14         }
15         for (int b=0; b<9; b++){
16             box = new ArrayList<Character>();
17             boxes.add(box);
18         }
19         for (int i=0; i<9; i++){
20             for (int j=0; j<9; j++){
21                 if (board[i][j]>‘9‘ || board[i][j]<‘1‘) continue;
22                 
23                 // check rows
24                 row = rows.get(i);
25                 if (row.contains(board[i][j])) return false;
26                 else row.add(board[i][j]);
27                 
28                 // check columns
29                 column = columns.get(j);
30                 if (column.contains(board[i][j])) return false;
31                 else column.add(board[i][j]);
32                 
33                 // check boxes
34                 int boxnum = getboxnum(i, j);
35                 box = boxes.get(boxnum);
36                 if (box.contains(board[i][j])) return false;
37                 else box.add(board[i][j]);
38             }
39         }
40         return true;
41         
42     }
43     
44     public int getboxnum(int i, int j){
45         int column = 0;
46         int row = 0;
47         if (i>=0 && i<=2) row = 1;
48         if (i>=3 && i<=5) row = 2;
49         if (i>=6 && i<=8) row = 3;
50         if (j>=0 && j<=2) column = 1;
51         if (j>=3 && j<=5) column = 2;
52         if (j>=6 && j<=8) column = 3;
53         return (row-1)*3 + column - 1;
54     }
55     
56 }

看到一个不错的方法：

 1 public class Solution {
 2     public boolean isValidSudoku(char[][] board) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         int N = board.length;
 6         int[] rows = new int[N];
 7         int[] cols = new int[N];
 8         int[] cubes = new int[N];
 9 
10         for(int i=0;i<N;i++)
11             for(int j=0;j<N;j++){
12                 if(board[i][j]!=‘.‘){
13                     int b = (i/3)*3+j/3;
14                     int offset = board[i][j] - ‘1‘;
15 
16                     if(offset>8 || offset<0) return false;
17                     if((rows[i] & (1<<offset))!=0) return false;
18                     if((cols[j] & (1<<offset))!=0) return false;
19                     if((cubes[b] & (1<<offset))!=0) return false;
20 
21                     rows[i] |= 1 << offset;
22                         cols[j] |= 1 << offset;
23                         cubes[b] |= 1 << offset;
24 
25                 }
26             }
27         return true;
28     }
29 }

 


联系
我们