首页 > 编程语言 >python 有效的数独 多种解法

python 有效的数独 多种解法

时间:2024-01-19 10:07:45浏览次数:36  
标签:rows return nums python range num 数独 解法 board

解法一:暴力枚举法

最简单的方法是对于每一行、每一列和每一个 3x3 的九宫格,分别判断其中是否有重复的数字。具体实现如下:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 检查行
        for i in range(9):
            nums = set()
            for j in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in nums:
                    return False
                nums.add(board[i][j])
        
        # 检查列
        for j in range(9):
            nums = set()
            for i in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in nums:
                    return False
                nums.add(board[i][j])
        
        # 检查 3x3 的九宫格
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                nums = set()
                for k in range(3):
                    for l in range(3):
                        if board[i+k][j+l] == '.':
                            continue
                        if board[i+k][j+l] in nums:
                            return False
                        nums.add(board[i+k][j+l])
        
        return True

该算法的时间复杂度为 python 有效的数独 多种解法_数独,即 python 有效的数独 多种解法_九宫格_02,因为数独的大小是固定的。

解法二:使用哈希表

可以使用哈希表来保存每一行、每一列和每一个 3x3 的九宫格中出现的数字。具体实现如下:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{} for i in range(9)]
        cols = [{} for i in range(9)]
        boxes = [{} for i in range(9)]
        
        # 遍历数独
        for i in range(9):
            for j in range(9):
                # 如果当前格子为空,则跳过
                if board[i][j] == '.':
                    continue
                
                num = int(board[i][j])
                box_idx = (i // 3) * 3 + j // 3
                
                # 如果当前数字已在当前行、当前列或者当前九宫格中出现过,则返回 False
                if num in rows[i] or num in cols[j] or num in boxes[box_idx]:
                    return False
                
                # 否则将当前数字加入到对应的哈希表中
                rows[i][num] = rows[i].get(num, 0) + 1
                cols[j][num] = cols[j].get(num, 0) + 1
                boxes[box_idx][num] = boxes[box_idx].get(num, 0) + 1
                
        return True

该算法的时间复杂度为 python 有效的数独 多种解法_数独_03,空间复杂度也为 python 有效的数独 多种解法_数独_03

解法三:使用位运算

由于数独中的数字只有 1 到 9 这九个数字,因此可以使用二进制数来表示某个数字是否出现过。具体实现如下:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        boxes = [0] * 9
        
        # 遍历数独
        for i in range(9):
            for j in range(9):
                # 如果当前格子为空,则跳过
                if board[i][j] == '.':
                    continue
                
                num = int(board[i][j])
                box_idx = (i // 3) * 3 + j // 3
                
                # 如果当前数字已在当前行、当前列或者当前九宫格中出现过,则返回 False
                if rows[i] & (1 << num) or cols[j] & (1 << num) or boxes[box_idx] & (1 << num):
                    return False
                
                # 否则将当前数字加入到对应的位运算中
                rows[i] |= (1 << num)
                cols[j] |= (1 << num)
                boxes[box_idx] |= (1 << num)
                
        return True

该算法的时间复杂度为 python 有效的数独 多种解法_数独_03,空间复杂度为 python 有效的数独 多种解法_List_06

标签:rows,return,nums,python,range,num,数独,解法,board
From: https://blog.51cto.com/lzning/9324681

相关文章

  • Python编程语法零基础入门
    0.开始前了解#号是一行注释"""6个"是多行注释"""#--coding:UTF-8print(u"你好!")#中文加上u转为unicode显示,不然会显示乱码1.基础语法和概念#(1)基本数据结构(整型、浮点型、字符串、布尔型)#格式:name=value没有分号、编译器自动匹配类型int_num=10float_num=......
  • Python实现光学字符识别技术-开源cnOCR
    CnOCR介绍CnOCR是一个用于中文OCR(光学字符识别)的Python3工具包。它支持简体中文、繁体中文(部分模型)、英文和数字的常见字符识别,并支持竖排文字的识别。CnOCR主要针对排版简单的印刷体文字图片,如截图图片、扫描件等。CnOCR的基本原理包括两个步骤:文本检测和文字识别。文本检测用于......
  • Flask企业级后台管理 Python 应用开发框架
    项目介绍一款Python语言基于Flask、Layui、MySQL等框架精心打造的一款模块化、高性能、企业级的敏捷开发框架,本着简化开发、提升开发效率的初衷触发,框架自研了一套个性化的组件,实现了可插拔的组件式开发方式:单图上传、多图上传、下拉选择、开关按钮、单选按钮、多选按钮、图片裁......
  • Python Matplotlib 绘图辅助功能
    ​ 1、添加标题和轴标签使用 plt.title("标题文本") 方法来添加图表标题。使用 plt.xlabel("X轴标签") 和 plt.ylabel("Y轴标签") 方法来添加X轴和Y轴的标签。常用参数如下,函数描述plt.title(label,loc='center',pad=None, fontsize=None,color=None......
  • python ssh连接mysql
    fromsshtunnelimportSSHTunnelForwarderimportpymysqlclassMySqlSSH:def__init__(self):self.server=SSHTunnelForwarder(ssh_address_or_host=('13.229.92.6',22),#sshhostssh_username='lenox......
  • CPLEX通过Python API获取Gap值的方法
    写在前面最近在使用Cplex求解模型,尽管Cplex的PythonAPI会自动输出引擎日志,但在多次求解中一次次看引擎日志找Gap值并做实验记录很麻烦,所以需要找到获取Gap值的方法。然而我在Cplex的官方文档中并没有找到这个方法,然后我就一个个去试这些方法,可算是给我试出来了。解决方法在Cpl......
  • Python - Playwright安装
    前言:Playwright是专门为满足端到端测试的需要而创建的。Playwright支持所有现代渲染引擎,包括Chromium、WebKit(Safari的浏览器引擎)和Firefox。在Windows、Linux和macOS上进行本地测试或在CI上进行测试.与Selenium+driver不同的是,Pw需要使用定制版的浏览器。如果本地......
  • python中的+=
    注意点:就地修改: 使用+=会就地修改可变对象,如列表或字典,而不是创建一个新的对象。这意味着原始对象会被改变。与+运算符的区别:+=与+运算符不同。对于不可变对象(如字符串、元组等),+=通常会创建一个新对象,而不是就地修改。可变对象vs不可变对象:对于可变对象(如列表、字典),+......
  • 波达方向估计(DOA)-Python代码实现MVDR
    https://mp.weixin.qq.com/s/61I1aBTwJ3ykw0uuceLKkQ模拟一个由三根全向天线组成的阵列,然后使用数组来模拟到达阵列的信号。相邻天线之间:1/2波长(也称为“半波长间隔”)。将模拟发射机的信号以一定角度theta到达该阵列。另外在这个接收到的信号中添加噪声。importnumpyasnp......
  • 波达方向估计(DOA)-Python代码实现
    https://mp.weixin.qq.com/s/fMGc8ziglySGKr1fY8Jvkw模拟一个由三根全向天线组成的阵列,然后使用数组来模拟到达阵列的信号。相邻天线之间距离为1/2波长(也称为“半波长间隔”)。将模拟发射机的信号以一定角度theta到达该阵列。另外在这个接收到的信号中添加噪声。importnumpy......