Leetcode -36- Valid sudoku

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Please determine if a 9×9 sudoku is valid. You only need to verify that the numbers you have entered are valid according to the following rules.

The numbers 1-9 can appear only once in each line. The numbers 1-9 May appear only once in each column. The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line. (Please refer to the sample figure) Numbers have been filled in the space of the Sudoku part, and the blank space is represented by ‘.’.

Note:

A valid sudoku (partially filled) is not necessarily solvable. You only need to verify that the entered numbers are valid according to the above rules.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] [". ", "9", "eight", ""," ", ""," ", "6", ""], [" 8", ""," ", ""," 6 ", ""," ", ""," 3 "], [" 4 ", ""," ", "eight", ""," 3 ", ""," ", "1"] [" 7 ", ". ", ""," ", "2", ""," ", ""," 6 "], [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"] [".",".","."," 8","."," 7","9"]] output: trueCopy the code

Example 2:

Input: board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] [". ", "9", "eight", ""," ", ""," ", "6", ""], [" 8", ""," ", ""," 6 ", ""," ", ""," 3 "], [" 4 ", ""," ", "eight", ""," 3 ", ""," ", "1"] [" 7 ", ". ", ""," ", "2", ""," ", ""," 6 "], [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"] [". ", ". ", ""," ", "eight", ""," ", "7", "9"]] output: false interpretation: in addition to the first line of the first number changed from 5 to 8, other Numbers are the same as the sample 1 box. But since there are two eights in the 3x3 in the upper left corner, this sudoku is invalid.Copy the code

Idea 1: Violence

• Scan row, column and matrix blocks separately

public boolean isValidSudoku(char[][] board) {
    / / column search first
    for (int i = 0; i < board.length; i++) {
        Set<Character> set = new HashSet<>();
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == '. ') continue;
            if (set.contains(board[i][j])) {
                return false; } set.add(board[i][j]); }}/ / search
    for (int i = 0; i < board.length; i++) {
        Set<Character> set = new HashSet<>();
        for (int j = 0; j < board.length; j++) {
            if (board[j][i] == '. ') continue;
            if (set.contains(board[j][i])) {
                return false; } set.add(board[j][i]); }}//
    int[][] dirs = new int[] [] {{1.0}, {0.1}, {0, -1}, {-1.0}, {1.1}, {1, -1}, {-1.1}, {-1, -1}};
    for (int i = 1; i <= 7; i += 3) {
        for (int j = 1; j <= 7; j += 3) {
            Set<Character> set = new HashSet<>();
            if(board[i][j] ! ='. ') {
                set.add(board[i][j]);
            }
            for (int[] dir : dirs) {
                if (board[i + dir[0]][j + dir[1= =]]'. ') continue;
                if (set.contains(board[i + dir[0]][j + dir[1]]) {return false;
                }
                set.add(board[i + dir[0]][j + dir[1]]); }}}return true;
}
Copy the code

• Time complexity O(3)99) = O(1)
• Space complexity O(1)