Leetcode[36]: Действительный судоку

Цитата дня

Я тот, кто должен умереть, когда мне придет время умереть, поэтому позвольте мне жить так, как я хочу.

Определите, действительна ли доска 9 x 9 судоку. Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:

1. Каждая строка должна содержать цифры 1-9 без повторения.
2. Каждый столбец должен содержать цифры 1-9 без повторения.
3. Каждый из девяти подблоков 3 x 3 сетки должен содержать цифры 1-9 без повторения.

Примечание.

• Доска судоку (частично заполненная) может быть действительной, но не обязательно решаемой.
• Только заполненные ячейки должны быть проверены в соответствии с указанными правилами.

Решение

Мы можем разбить это на 3 задачи

1. Проверка строк (каждая строка должна содержать значения от 0 до 9 только один раз)
2. Проверить столбцы (каждый столбец должен содержать значения от 0 до 9 только один раз)
3. Проверка полей 3x3 (Каждая ячейка 3x3 должна содержать значения от 0 до 9 только один раз )

Поскольку мы знаем, что каждый элемент на доске будет либо (.), что означает пустое место, либо любой цифровой символ среди «0–9».

Поэтому, если мы встречаем «.», нам все равно, и если мы встречаем цифровой символ, мы проверяем, встречались ли мы с ним раньше или нет.

Мы можем использовать HashSet для проверки посещенного цифрового символа, но мы можем использовать логический массив размером 10, потому что мы знаем, что каждый цифровой символ будет «0–9».

Теперь нам нужно извлечь индекс из символа цифры, здесь мы используем некоторый трюк, чтобы получить его.

Мы знаем, что в формате ASCII цифры идут последовательно.

Поэтому, если мы попытаемся вычесть значение ASCII, мы получим соответствующую цифру.

Теперь давайте посмотрим код -

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        int rowSize = 9;
        int colSize = 9;
        
        // validate rows
        for(int i=0;i<rowSize;i++) {
            
            if(!isValidRow(board, i, colSize))
                return false;
        }
        
        // validate cols
        for(int i=0;i<colSize;i++) {
            
            if(!isValidCol(board, i, rowSize))
                return false;
        }
        
        // validate boxes
        for(int i=0;i<9;i+=3) {
            for(int j=0;j<9;j+=3) {
                // i and j are the starting index of the box
                if(!isValidBox(board, i, j)) 
                    return false;
            }
        }
        
        return true;
    }
    
    public boolean isValidRow(char[][] board, int row, int colSize) {
        
        boolean[] visited = new boolean[colSize+1];
        
        for(int i=0;i<colSize;i++) {
            
            if(board[row][i] == '.') continue;
            
            int ind = board[row][i]-'0';
            
            if(visited[ind]) return false;
            
            visited[ind] = true;
        }
        
        return true;
    }
    
    public boolean isValidCol(char[][] board, int col, int rowSize) {
        
        boolean[] visited = new boolean[rowSize+1];
        
        for(int i=0;i<rowSize;i++) {
            
            if(board[i][col] == '.') continue;
            
            int ind = board[i][col]-'0';
            
            if(visited[ind]) return false;
            
            visited[ind] = true;
        }
        
        return true;
    }
    
    public boolean isValidBox(char[][] board, int row, int col) {
        
        boolean[] visited = new boolean[10]; // 0 - 9
        
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                
                if(board[row+i][col+j] == '.') continue;
                
                int ind = board[row+i][col+j]-'0';
                
                if(visited[ind]) return false;
                
                visited[ind] = true;
            }
        }
        
        return true;
    }
}

Краткое содержание

Во всем коде мне кажется важным только одно — использование логического массива для проверки ранее посещенных символов. (Только моя точка зрения).

Спасибо ВСЕМ (от очень замкнутого мальчика)