数组——有效的数独

题目

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

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

数独.png

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入
[
 ["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

示例 2:

输入
[
  ["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"]
]
输出false

解释: 除了第一行的第一个数字从 **5** 改为 **8** 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符 '.' 。
• 给定数独永远是 9x9 形式的。

解题思路

我的思路：答案(一)
建一个字典，值都是空集合，其中的键有3种类型：
第一种：键是0~8，记录每一行的数据；
第二种：键是9~17，记录每一列的数据；
第三种：这一种比较特殊，在9 * 9的大图里面，总共只有9个 小图，因此，每一个3 * 3是一个单独的集合，这里我用(i // 3, j//3)作为键

然后，就是依次遍历这81个数，分别判断这个元素是否在对应的集合中，如果不存在就添加，如果存在就返回。

结果完成了，但是比较慢。

我觉得主要慢在建这个字典的时候的运算就非常大

最快思路：答案(二)
弄3个列表，每个列表里面有9个集合

遍历这81个数，根据行和列，判断是否属于对应列表中某个索引值的集合中，和我上面的基本思想一样。
这里最关键还用了一种方案，将2个一样的列表，双遍历得到的2个数，组合成唯一不重复的索引值的方法，详见代码。

答案(一)

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        target_dict = {}
        for i in range(9):
            target_dict[i] = set()
            target_dict[i + 10] = set()
        for i in range(3):
            for j in range(3):
                target_dict[(i, j)] = set()
        for l in range(9):
            for k in range(9):
                value = board[l][k]
                if value == '.':
                    continue
                if value in target_dict[l]:
                    return False
                else:
                    target_dict[l].add(value)
                if value in target_dict[k + 10]:
                    return False
                else:
                    target_dict[k + 10].add(value)
                if value in target_dict[(l // 3, k // 3)]:
                    return False
                else:
                    target_dict[(l // 3, k // 3)].add(value)
        
        return True

答案(二)

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row = [set() for i in range(9)]
        vertical = [set() for i in range(9)]
        net = [set() for i in range(9)]
 
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == '.':
                    continue
                if num in row[i]:
                    return False
                if num in vertical[j]:
                    return False
                
                index = i // 3 * 3 + j // 3
                if num in net[index]:
                    return False
                row[i].add(num)
                vertical[j].add(num)
                net[index].add(num)
                
        return True