30天刷题挑战（二十九）

题目来源: 面试经典 150 题

36. 有效的数独

思路

使用数组记录每一行，每一列和每一个九宫格中，每个数字出现的次数。遍历数独矩阵一次，过程中更新数字计数，判断是否满足条件。

代码

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
  const rows = Array(9).fill(0).map(() => Array(9).fill(0))
  const columns = Array(9).fill(0).map(() => Array(9).fill(0))
  const subboxes = Array(3).fill(0).map(() => Array(3).fill(0).map(() => Array(9).fill(0)))

  for (let i = 0; i < 9 ; i++) {
    for (let j = 0; j < 9 ; j++) {
      const c = board[i][j]
     
      if (c !== '.') {
        const index = c.charCodeAt() - '0'.charCodeAt() - 1

        rows[i][index]++
        columns[j][index]++
        subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++

         if (
           rows[i][index] > 1 || 
           columns[j][index] > 1 ||
           subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1
          ) {
           return false
         }
      }
    }
  }

  return true
};

73. 矩阵置零

思路

模拟法，遍历矩阵标记每一行和每一列是否有零出现，再遍历数组将对应的矩阵项目置零。

代码

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  
  const m = matrix.length
  const n = matrix[0].length
  const row = Array(m).fill(false)
  const col = Array(n).fill(false)
  
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        row[i] = col[j] = true
      }
    }
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (row[i] || col[j]) {
        matrix[i][j] = 0
      }
    }
  }
};

本文完，感谢阅读。