有效的数独

要求

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字,空白格用 '.' 表示。

示例

输入:board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出:true

解答Ⅰ

设置rowcolbox三个二维数组,它们第一个元素分别代表第i行,第j列,第j/3+(i/3)*3块;为什么?前三块单纯由列数j决定,因为i0、1、2[i/3]还是0,所以0、1、2列第0块,3、4、5列第1块,6、7、8列第2块;下面的就需要由ij配合控制了,在原来[i/3]基础上乘3j/3+(i/3)*3;解决完第一个元素,对于第二个就是留给数字1-9,申请的是[9][9],最后再减掉1就行了,或者直接减掉字符'1'。这样row[i][curNum]就能表示第i行数字curNum是否出现过,1则返回错误,0则标记,以此类推。

class Solution {
  public Boolean isValidSudoku(char[][] board) {
    int[][] row = new int[9][9];
    int[][] col = new int[9][9];
    int[][] box = new int[9][9];
    for (int i = 0 ;i<9 ; i++){
      for (int j = 0 ;j < 9 ;j++){
        if(board[i][j]=='.'){
          continue;
        }
        int curNum = board[i][j] - '0' -1;
        if(row[i][curNum]==1) return false;
        if(col[j][curNum]==1) return false;
        if (box[j/3 + (i/3) * 3][curNum]==1) return false;
        row[i][curNum]=1;
        col[j][curNum]=1;
        box[j/3 + (i/3) * 3][curNum]=1;
      }
    }
    return true;
  }
}

矩阵置零

要求

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解答Ⅰ

时间复杂度:O(mn),空间复杂度:O(m+n)

class Solution {
  public void setZeroes(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[] row = new int[m];
    int[] col = new int[n];
    for (int i = 0 ; i<m;i++){
      for (int j=0;j<n;j++){
        if(matrix[i][j]==0){
          row[i]=col[j]=1;
        }
      }
    }
    for (int i = 0 ; i<m;i++){
      for (int j=0;j<n;j++){
        if(row[i]==1 || col[j]==1){
          matrix[i][j]=0;
        }
      }
    }
  }
}

解答Ⅱ

时间复杂度:O(mn),空间复杂度:O(1)
对于首行首列的各元素使用标记位,出现0则标记true;对于内层的元素,如果出现0则将其所对应的首行和首列的那两个元素赋为0,最巧妙的地方我认为就在于这里,用m*n的循环判断比方说如果首行元素[0][j]出现0,而首列元素[i][0]没有0,那么首行元素出现0的那一列全部置0,也就是[i][j]==0;解决完内层,对于第一行和第一列,则只用判断开始设置的两个标记位,只要是true,那一行或列全部置0;为什么程序要这样编排?为什么不在设完标记位之后,顺手将第一行第一列全部置0?因为如果首先就确定了首行首列的0,会和后续平移得来的“控制位0”混淆。

class Solution {
  public void setZeroes(int[][] matrix) {
    int row = matrix.length;
    int col = matrix[0].length;
    Boolean row0_flag = false;
    Boolean col0_flag = false;
    // 第一行是否有零
    for (int j = 0; j < col; j++) {
      if (matrix[0][j] == 0) {
        row0_flag = true;
        break;
      }
    }
    // 第一列是否有零
    for (int i = 0; i < row; i++) {
      if (matrix[i][0] == 0) {
        col0_flag = true;
        break;
      }
    }
    // 把第一行第一列作为标志位
    for (int i = 1; i < row; i++) {
      for (int j = 1; j < col; j++) {
        if (matrix[i][j] == 0) {
          matrix[i][0] = matrix[0][j] = 0;
        }
      }
    }
    // 置0
    for (int i = 1; i < row; i++) {
      for (int j = 1; j < col; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }
    if (row0_flag) {
      for (int j = 0; j < col; j++) {
        matrix[0][j] = 0;
      }
    }
    if (col0_flag) {
      for (int i = 0; i < row; i++) {
        matrix[i][0] = 0;
      }
    }
  }
}

解答Ⅲ

改进使用单标记变量col0_flag;这样,第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新,我们需要从最后一行开始,倒序地处理矩阵元素。

class Solution {
  public void setZeroes(int[][] matrix) {
    Boolean col0_flag = false;
    int row = matrix.length;
    int col = matrix[0].length;
    for (int i = 0; i < row; i++) {
      if (matrix[i][0] == 0) col0_flag = true;
      for (int j = 1; j < col; j++) {
        if (matrix[i][j] == 0) {
          matrix[i][0] = matrix[0][j] = 0;
        }
      }
    }
    for (int i = row - 1; i >= 0; i--) {
      for (int j = col - 1; j >= 1; j--) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
      if (col0_flag) matrix[i][0] = 0;
    }
  }
}