【LeetCode】Day95-有效的数独＆矩阵置零

题目1

36. 有效的数独【中等】

题解

如果按照规则行、列、3*3矩阵挨个试的话，工作量巨大…所以怎么才能降低复杂度呢？是这道题要重点考虑的问题

可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，并判断是否满足有效的数独的条件即可。

class Solution {
    
    public boolean isValidSudoku(char[][] board) {
    
        int rows[][]=new int[9][9];//行
        int columns[][]=new int[9][9];//列
        int three[][][]=new int[3][3][9];//小九宫格

        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;//字符转换为数字
                    rows[i][index]++;
                    columns[index][j]++;
                    three[i/3][j/3][index]++;//注意怎么表示小九宫格的哈希表
                    if(rows[i][index]>1||columns[index][j]>1||three[i/3][j/3][index]>1)
                        return false;
                }
            }
        }
        return true;
    }
}

时间复杂度：$O(1)$，数独大小是固定的，因此复杂度为O(1)

空间复杂度：$O(1)$，由于数独大小固定，因此哈希表大小也固定，复杂度为O(1)

题目2

73. 矩阵置零【中等】

题解

使用两个数组row[]和column[]标记哪行哪列有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++){
    
                //元素为0,行列打标记
                if(matrix[i][j]==0){
    
                    row[i]=true;
                    column[j]=true;
                }
            }
        }
        //根据标记,行列赋零
        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;
            }
        }
    }
}

时间复杂度：$O(mn)$

空间复杂度：$O(m+n)$