-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathValidSudoku.java
More file actions
160 lines (154 loc) · 6.02 KB
/
Copy pathValidSudoku.java
File metadata and controls
160 lines (154 loc) · 6.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/**
* <p>请你判断一个 <code>9 x 9</code> 的数独是否有效。只需要<strong> 根据以下规则</strong> ，验证已经填入的数字是否有效即可。</p>
*
* <ol>
* <li>数字 <code>1-9</code> 在每一行只能出现一次。</li>
* <li>数字 <code>1-9</code> 在每一列只能出现一次。</li>
* <li>数字 <code>1-9</code> 在每一个以粗实线分隔的 <code>3x3</code> 宫内只能出现一次。（请参考示例图）</li>
* </ol>
*
* <p> </p>
*
* <p><strong>注意：</strong></p>
*
* <ul>
* <li>一个有效的数独（部分已被填充）不一定是可解的。</li>
* <li>只需要根据以上规则，验证已经填入的数字是否有效即可。</li>
* <li>空白格用 <code>'.'</code> 表示。</li>
* </ul>
*
* <p> </p>
*
* <p><strong>示例 1：</strong></p>
* <img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714svg.png" style="height:250px; width:250px" />
* <pre>
* <strong>输入：</strong>board =
* [["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"]]
* <strong>输出：</strong>true
* </pre>
*
* <p><strong>示例 2：</strong></p>
*
* <pre>
* <strong>输入：</strong>board =
* [["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"]]
* <strong>输出：</strong>false
* <strong>解释：</strong>除了第一行的第一个数字从<strong> 5</strong> 改为 <strong>8 </strong>以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。</pre>
*
* <p> </p>
*
* <p><strong>提示：</strong></p>
*
* <ul>
* <li><code>board.length == 9</code></li>
* <li><code>board[i].length == 9</code></li>
* <li><code>board[i][j]</code> 是一位数字（<code>1-9</code>）或者 <code>'.'</code></li>
* </ul>
* <div><div>Related Topics</div><div><li>数组</li><li>哈希表</li><li>矩阵</li></div></div><br><div><li>👍 728</li><li>👎 0</li></div>
*/
package leetcode7;
public class ValidSudoku {
public static void main(String[] args) {
new ValidSudoku().new Solution().isValidSudoku(new char[][]{
{'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'}
});
}
class Solution {
public boolean isValidSudoku(char[][] board) {
int len = 9;
boolean[][] column = new boolean[len][len];
boolean[][] row = new boolean[len][len];
boolean[][] boxed = new boolean[len][len];
for (int x = 0; x < len; x++) {
for (int y = 0; y < len; y++) {
if (board[x][y] == '.') {
continue;
}
int val = board[x][y] - '1';
int boxIndex = x / 3 * 3 + y / 3;
if (column[y][val] || row[x][val] || boxed[boxIndex][val]) {
return false;
}
row[x][val] = true;
column[y][val] = true;
boxed[boxIndex][val] = true;
}
}
return true;
}
}
/**
* 冗长的解法,空间复杂度 O(n)
* 暂不研究
*/
class Solution2 {
public boolean isValidSudoku(char[][] board) {
int length = 9;
for (int i = 0; i < length; i++) {
boolean[] memo = new boolean[length];
for (int j = 0; j < length; j++) {
if (board[i][j] == '.') {
continue;
}
if (memo[board[i][j] - '1']) {
return false;
}
memo[board[i][j] - '1'] = true;
}
}
for (int j = 0; j < length; j++) {
boolean[] memo = new boolean[length];
for (int i = 0; i < length; i++) {
if (board[i][j] == '.') {
continue;
}
if (memo[board[i][j] - '1']) {
return false;
}
memo[board[i][j] - '1'] = true;
}
}
for (int i = 0; i < length; i += 3) {
for (int j = 0; j < length; j += 3) {
boolean[] memo = new boolean[length];
for (int x = i; x < i + 3; x++) {
for (int y = j; y < j + 3; y++) {
if (board[x][y] == '.') {
continue;
}
if (memo[board[x][y] - '1']) {
return false;
}
memo[board[x][y] - '1'] = true;
}
}
}
}
return true;
}
}
}