346cea4f879c3bd5069efc98bde718db
(难度Medium)Problem 36. Valid Sudoku(判断合法数独)

链接

https://leetcode.com/problems/valid-sudoku/

难度等级

Medium

题干

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

题意

给一个9*9的数独,判断该数独是否合法。

其中数字只有1-9,合法的数独要求每行每列以及每个3*3的井字格内没有重复的元素。

样例

Example 1:

Input:
[
  ["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"]
]
Output: true


Example 2:

Input:
[
  ["8","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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

题解

这道题没什么解法或者方法,就是按照题意实现功能,学名叫模拟。

那么怎么模拟呢?

首先我们要把读入的数据解析一下,传入的是一个char的二维数组,为了方便后续的操作,我们把它们全部转成int。char转int其实很方便,我们只需要用ch - ‘0’就好了。在C++当中,字符相减会自动转化成ASCII码的差值。

转成int之后呢?很简单,我们只需要按照题意判断每行每列以及每个单元格当中是否有重复的元素就行了。

怎么判断是否有重复元素呢?我们可以利用一个hashtable来解决。

top Created with Sketch.