📑 题目：36. 有效的数独

🚀 本题 LeetCode 传送门

题目大意

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

解题思路

  • 给出一个数独的棋盘，要求判断这个棋盘当前是否满足数独的要求：即行列是否都只包含 1-9，每个九宫格里面是否也只包含 1-9 。
  • 注意这题和第 37 题是不同的，这一题是判断当前棋盘状态是否满足数独的要求，而第 37 题是要求求解数独。本题中的棋盘有些是无解的，但是棋盘状态是满足题意的。

代码

  1. package leetcode
  3. import "strconv"
  5. // 解法一 暴力遍历，时间复杂度 O(n^3)
  6. func isValidSudoku(board [][]byte) bool {
  7.  // 判断行 row
  8.  for i := 0; i < 9; i++ {
  9.   tmp := [10]int{}
  10.   for j := 0; j < 9; j++ {
  11.    cellVal := board[i][j : j+1]
  12.    if string(cellVal) != "." {
  13.     index, _ := strconv.Atoi(string(cellVal))
  14.     if index > 9 || index < 1 {
  15.      return false
  16.     }
  17.     if tmp[index] == 1 {
  18.      return false
  19.     }
  20.     tmp[index] = 1
  21.    }
  22.   }
  23.  }
  24.  // 判断列 column
  25.  for i := 0; i < 9; i++ {
  26.   tmp := [10]int{}
  27.   for j := 0; j < 9; j++ {
  28.    cellVal := board[j][i]
  29.    if string(cellVal) != "." {
  30.     index, _ := strconv.Atoi(string(cellVal))
  31.     if index > 9 || index < 1 {
  32.      return false
  33.     }
  34.     if tmp[index] == 1 {
  35.      return false
  36.     }
  37.     tmp[index] = 1
  38.    }
  39.   }
  40.  }
  41.  // 判断 9宫格 3X3 cell
  42.  for i := 0; i < 3; i++ {
  43.   for j := 0; j < 3; j++ {
  44.    tmp := [10]int{}
  45.    for ii := i * 3; ii < i*3+3; ii++ {
  46.     for jj := j * 3; jj < j*3+3; jj++ {
  47.      cellVal := board[ii][jj]
  48.      if string(cellVal) != "." {
  49.       index, _ := strconv.Atoi(string(cellVal))
  50.       if tmp[index] == 1 {
  51.        return false
  52.       }
  53.       tmp[index] = 1
  54.      }
  55.     }
  56.    }
  57.   }
  58.  }
  59.  return true
  60. }
  62. // 解法二 添加缓存，时间复杂度 O(n^2)
  63. func isValidSudoku1(board [][]byte) bool {
  64.  rowbuf, colbuf, boxbuf := make([][]bool, 9), make([][]bool, 9), make([][]bool, 9)
  65.  for i := 0; i < 9; i++ {
  66.   rowbuf[i] = make([]bool, 9)
  67.   colbuf[i] = make([]bool, 9)
  68.   boxbuf[i] = make([]bool, 9)
  69.  }
  70.  // 遍历一次，添加缓存
  71.  for r := 0; r < 9; r++ {
  72.   for c := 0; c < 9; c++ {
  73.    if board[r][c] != '.' {
  74.     num := board[r][c] - '0' - byte(1)
  75.     if rowbuf[r][num] || colbuf[c][num] || boxbuf[r/3*3+c/3][num] {
  76.      return false
  77.     }
  78.     rowbuf[r][num] = true
  79.     colbuf[c][num] = true
  80.     boxbuf[r/3*3+c/3][num] = true // r,c 转换到box方格中
  81.    }
  82.   }
  83.  }
  84.  return true
  85. }