LeetCode刷题实战36： 有效的数独
LeetCode刷题实战36： 有效的数独
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 有效的数独，我们先来看题面：
https://leetcode-cn.com/problems/valid-sudoku/
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
题意
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
样例
题解
这题主要是考察HashSet，不可保存重复元素。我们可以用3HashSet，分别保存第i行、第i列和第i个3x3的九宫格中的元素，每处理一个元素，若不为空，将正在处理的当前元素，添加到所属的行、列以及3x3的九宫格中，若添加失败，表明所属的行、列或者3x3九宫格中有重复元素，返回false；若全部扫描完，返回true。
class Solution {
public boolean isValidSudoku(char[][] board) {
//最外层循环，每次循环并非只是处理第i行，而是处理第i行、第i列以及第i个3x3的九宫格
for(int i = 0; i < 9; i++){
HashSet<Character> line = new HashSet<>();
HashSet<Character> col = new HashSet<>();
HashSet<Character> cube = new HashSet<>();
for(int j = 0; j < 9; j++){
if('.' != board[i][j] && !line.add(board[i][j]))
return false;
if('.' != board[j][i] && !col.add(board[j][i]))
return false;
int m = i/3*3+j/3;
int n = i%3*3+j%3;
if('.' != board[m][n] && !cube.add(board[m][n]))
return false;
}
}
return true;
}
}如果你还有其他更好的解法，欢迎在评论区给出你的答案！
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
上期推文：
腾讯云开发者
