首页 / 算法 / leetcode算法题-有效的数独
leetcode算法题-有效的数独
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode算法题-有效的数独,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4600字,纯文字阅读大概需要7分钟。
内容图文
![leetcode算法题-有效的数独](/upload/InfoBanner/zyjiaocheng/613/f91b554c99ba42f980b342a6cd9f7937.jpg)
题目
本题为leetcode探索初级算法中数组章节的一题
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
1.数字 1-9 在每一行只能出现一次。
2.数字 1-9 在每一列只能出现一次。
3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字,空白格用 '.' 表示。
示例 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.一个有效的数独(部分已被填充)不一定是可解的。
2.只需要根据以上规则,验证已经填入的数字是否有效即可。
3.给定数独序列只包含数字 1-9 和字符 '.' 。
4.给定数独永远是 9x9 形式的。
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
我的解法
class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
Set set = new HashSet();
for (int j = 0; j < 9; j++) {
if(board[i][j] != '.' && set.contains(board[i][j])){
return false;
}
set.add(board[i][j]);
}
}
for (int i = 0; i < 9; i++) {
Set set = new HashSet();
for (int j = 0; j < 9; j++) {
if(board[j][i] != '.' && set.contains(board[j][i])){
return false;
}
set.add(board[j][i]);
}
}
return check9(board, 1, 1) && check9(board, 1, 4) && check9(board, 1, 7)
&& check9(board, 4, 1) && check9(board, 4, 4) && check9(board, 4, 7)
&& check9(board, 7, 1) && check9(board, 7, 4) && check9(board, 7, 7);
}
private static boolean check9(char[][] board, int center1, int center2) {
Set set = new HashSet();
if (board[center1 - 1][center2 - 1] != '.' && set.contains(board[center1 - 1][center2 - 1])) {
return false;
}
set.add(board[center1 - 1][center2 - 1]);
if (board[center1 - 1][center2] != '.' && set.contains(board[center1 - 1][center2])) {
return false;
}
set.add(board[center1 - 1][center2]);
if (board[center1 - 1][center2 + 1] != '.' && set.contains(board[center1 - 1][center2 + 1])) {
return false;
}
set.add(board[center1 - 1][center2 + 1]);
if (board[center1][center2 - 1] != '.' && set.contains(board[center1][center2 - 1])) {
return false;
}
set.add(board[center1][center2 - 1]);
if (board[center1][center2] != '.' && set.contains(board[center1][center2])) {
return false;
}
set.add(board[center1][center2]);
if (board[center1][center2 + 1] != '.' && set.contains(board[center1][center2 + 1])) {
return false;
}
set.add(board[center1][center2 + 1]);
if (board[center1 + 1][center2 - 1] != '.' && set.contains(board[center1 + 1][center2 - 1])) {
return false;
}
set.add(board[center1 + 1][center2 - 1]);
if (board[center1 + 1][center2] != '.' && set.contains(board[center1+1][center2])) {
return false;
}
set.add(board[center1 + 1][center2]);
if (board[center1 + 1][center2 + 1] != '.' && set.contains(board[center1 + 1][center2 + 1])) {
return false;
}
return true;
}
}
比较蠢的解法。代码比较臃肿。
官方解法
class Solution {
public boolean isValidSudoku(char[][] board) {
// init data
HashMap<Integer, Integer> [] rows = new HashMap[9];
HashMap<Integer, Integer> [] columns = new HashMap[9];
HashMap<Integer, Integer> [] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<Integer, Integer>();
columns[i] = new HashMap<Integer, Integer>();
boxes[i] = new HashMap<Integer, Integer>();
}
// validate a board
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num != '.') {
int n = (int)num;
int box_index = (i / 3 ) * 3 + j / 3;
// keep the current cell value
rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);
// check if this value has been already seen before
if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
return false;
}
}
}
return true;
}
}
时间复杂度:O(1)O(1),因为我们只对 81 个单元格进行了一次迭代。
空间复杂度:O(1)O(1)。
内容总结
以上是互联网集市为您收集整理的leetcode算法题-有效的数独全部内容,希望文章能够帮你解决leetcode算法题-有效的数独所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。