[leetcode] day95 effective Sudoku & matrix zeroing

subject 1

36. Effective Sudoku 【 secondary 】

Answer key

If you follow the rule 、 Column 、3*3 If the matrix tries one by one , Huge workload … So how can we reduce the complexity ？ This is the key consideration of this problem

Sure Use a hash table to record each row 、 In every column and every little nine palace , The number of times each number appears . It only needs Traverse Sudoku once , Update the count in the hash table during traversal , And judge whether the conditions for effective Sudoku are met .

class Solution {
    
    public boolean isValidSudoku(char[][] board) {
    
        int rows[][]=new int[9][9];// That's ok 
        int columns[][]=new int[9][9];// Column 
        int three[][][]=new int[3][3][9];// Xiaojiugong grid 

        for(int i=0;i<9;i++){
    
            for(int j=0;j<9;j++){
    
                if(board[i][j]!='.'){
    
                    int index=board[i][j]-'0'-1;// Character to number 
                    rows[i][index]++;
                    columns[index][j]++;
                    three[i/3][j/3][index]++;// Notice how to represent the hash table of the small Jiugong lattice 
                    if(rows[i][index]>1||columns[index][j]>1||three[i/3][j/3][index]>1)
                        return false;
                }
            }
        }
        return true;
    }
}

Time complexity ：$O(1)$, Sudoku size is fixed , So the complexity is O(1)

Spatial complexity ：$O(1)$, Due to the fixed size of Sudoku , Therefore, the hash table size is also fixed , The complexity is O(1)

subject 2

73. Matrix zeroing 【 secondary 】

Answer key

Use two arrays row[] and column[] Mark which row and which column have 0

class Solution {
    
    public void setZeroes(int[][] matrix) {
    
        int m=matrix.length,n=matrix[0].length;
        boolean[] row=new boolean[m];
        boolean[] column=new boolean[n];
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                // Element is 0, Mark lines 
                if(matrix[i][j]==0){
    
                    row[i]=true;
                    column[j]=true;
                }
            }
        }
        // According to the mark , Zero row and column 
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                if(row[i]==true||column[j]==true)
                    matrix[i][j]=0;
            }
        }
    }
}

Time complexity ：$O(mn)$

Spatial complexity ：$O(m+n)$