LeetCode【0036】有效的数独

本文目录

  • 1 中文题目
  • 2 求解方法:python内置函数set
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

请根据以下规则判断一个 9 x 9 的数独是否有效。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(见下方的参考示例图)

注意

  • 一个有效的数独(部分已被填充)不一定是可解的。
  • 只需要根据以上规则,验证已经填入的数字是否有效即可。
  • 空白格用 ‘.’ 表示。

示例:

在这里插入图片描述

对于上面的数独,其输入格式如下:
输入:board = 
[["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
输入:board = 
[["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 存在, 因此这个数独是无效的。

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字(1-9)或者 ‘.

2 求解方法:python内置函数set

2.1 方法思路

方法核心

  • 使用三组集合分别记录每行、每列和每个3x3方块中已出现的数字
  • 一次遍历完成所有验证
  • 使用数学公式计算粗实线分割出来的3x3方块的索引

实现步骤

(1)初始化数据结构:

  • 创建9个集合用于存储每行的数字
  • 创建9个集合用于存储每列的数字
  • 创建9个集合用于存储每个3x3方块的数字

(2)遍历数独板:

  • 双层循环遍历9x9的数独板
  • 对于每个位置,获取当前数字
  • 跳过空格(用’.'表示)
  • 计算当前位置所在的3x3方块的索引
  • 检查数字是否重复出现
  • 将不重复的数字添加到对应集合中

(3)验证过程:

  • 检查当前数字是否已在当前行出现
  • 检查当前数字是否已在当前列出现
  • 检查当前数字是否已在当前3x3方块出现
  • 如果出现重复,立即返回False
  • 如果遍历完成没有重复,返回True

方法示例

输入数独板示例(部分):
[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],...
]详细执行过程:1. 初始化:rows = [set(), set(), set(), ...] (9个空集合)cols = [set(), set(), set(), ...] (9个空集合)boxes = [set(), set(), set(), ...] (9个空集合)2. 处理第一个位置 (0,0)- 数字为 "5"- box_index = (0 // 3) * 3 + (0 // 3) = 0- 检查 rows[0], cols[0], boxes[0] 都不包含 "5"-"5" 添加到这三个集合中3. 处理第二个位置 (0,1)- 数字为 "3"- box_index = (0 // 3) * 3 + (1 // 3) = 0- 检查集合,添加数字4. 继续处理每个位置...示例中3x3方块索引的计算:
- 位置(0,0): (0//3)*3 + 0//3 = 0
- 位置(0,4): (0//3)*3 + 4//3 = 1
- 位置(4,4): (4//3)*3 + 4//3 = 4

2.2 Python代码

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:# 初始化用于存储每行、每列和每个3x3方块中数字出现情况的集合rows = [set() for _ in range(9)]cols = [set() for _ in range(9)]boxes = [set() for _ in range(9)]# 遍历整个数独板for i in range(9):for j in range(9):# 获取当前位置的数字num = board[i][j]# 如果是空格,继续下一个位置if num == '.':continue# 计算当前位置所在的3x3方块的索引# box_index = (行号 // 3) * 3 + (列号 // 3)box_index = (i // 3) * 3 + j // 3# 检查当前数字是否已经在对应的行、列或3x3方块中出现过if (num in rows[i] or num in cols[j] or num in boxes[box_index]):return False# 将当前数字添加到对应的集合中rows[i].add(num)cols[j].add(num)boxes[box_index].add(num)# 遍历完成且没有发现重复,返回Truereturn True

2.3 复杂度分析

  • 时间复杂度:O(1)
    • 固定大小的9x9网格
    • 遍历一次数独数组
    • 每次检查和添加操作都是O(1)
    • 总操作次数是常数
  • 空间复杂度:O(1)
    • 使用固定大小的集合
    • 9个集合用于行
    • 9个集合用于列
    • 9个集合用于3x3方块

3 题目总结

题目难度:中等
数据结构:二维数组
应用算法:Python内置函数set

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470372.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32 GPIO 配置

GPIO 八种工作模式 STM32的GPIO八种模式明解STM32—GPIO理论基础知识篇之八种工作模式stm32cubemx hal学习记录:GPIO输入输出[STM32G4系列] GPIO筆記 - CubeMX GPIO整理與應用 模拟量输入输出 ADC 【STM32】HAL库 STM32CubeMX教程九—ADC[通俗易懂] DAC STM32C…

Xcode 16 使用 pod 命令报错解决方案

原文请点击这个跳转 一、问题现象: 有人会遇到 Xcode 升级到 16 后,新建应用然后使用 pod init 命令会报错如下: Stack Ruby : ruby 3.3.5 (2024-09-03 revision ef084cc8f4) [x86_64-darwin23]RubyGems : 3.5.22Host : macOS 15.0 (24A335…

使用 Flask 和 ONLYOFFICE 实现文档在线编辑功能

提示:CSDN 博主测评ONLYOFFICE 文章目录 引言技术栈环境准备安装 ONLYOFFICE 文档服务器获取 API 密钥安装 Flask 和 Requests 创建 Flask 应用项目结构编写 app.py创建模板 templates/index.html 运行应用功能详解文档上传生成编辑器 URL显示编辑器回调处理 安全性…

机器学习——损失函数、代价函数、KL散度

🌺历史文章列表🌺 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…

vxe-table 3.10+ 进阶高级用法(一),根据业务需求自定义实现筛选功能

vxe-table 是vue中非常强大的表格的,公司项目中复杂的渲染都是用 vxe-table 的,对于用的排序。筛选之类的都能支持,而且也能任意扩展,非常强大。 默认筛选功能 筛选的普通用法就是给对应的列指定参数: filters&#…

推荐一款好用的postman替代工具2024

Apifox 是国内团队自主研发的 API 文档、API 调试、API Mock、API 自动化测试一体化协作平台,是非常好的一款 postman 替代工具。 它通过一套系统、一份数据,解决多个系统之间的数据同步问题。只要定义好接口文档,接口调试、数据 Mock、接口…

MTSET可溶于DMSO、DMF、THF等有机溶剂,并在水中有轻微的溶解性,91774-25-3

一、基本信息 中文名称:[2-(三甲基铵)乙基]甲硫基磺酸溴;MTSET巯基反应染料 英文名称:MTSET;[2-(Trimethylammonium)ethyl]methanethiosulfonate Bromide CAS号:91774-25-3 分子式:C6H16BrNO2S2 分子量…

如何为电子课程创造创意

为电子课程创造一个想法,首先要深刻理解是什么让知识对学习者既相关又吸引人。第一步是专注于可以分解为可教部分的特定技能或专业领域。通常,人们从他们熟悉的东西开始,但真正的挑战在于将这些知识转化为一种可访问且引人入胜的学习体验。这…

安全生产管理的重要性:现状、痛点与改进之路

当前,安全生产管理已经成为企业管理中的关键环节,但现实中仍然存在诸多痛点。近年来,随着工业化和现代化的快速推进,企业在追求效益的同时,忽视安全管理的现象屡见不鲜。据统计,安全事故的发生频率仍然较高…

深度学习之 LSTM

1.1 LSTM的产生原因 ​ RNN在处理长期依赖(时间序列上距离较远的节点)时会遇到巨大的困难,因为计算距离较远的节点之间的联系时会涉及雅可比矩阵的多次相乘,会造成梯度消失或者梯度膨胀的现象。为了解决该问题,研究人…

机器学习基础02_特征工程

目录 一、概念 二、API 三、DictVectorize字典列表特征提取 四、CountVectorize文本特征提取 五、TF-IDF文本1特征词的重要程度特征提取 六、无量纲化预处理 1、MinMaxScaler 归一化 2、StandardScaler 标准化 七、特征降维 1、特征选择 VarianceThreshold 底方差…

Linux第四讲:Git gdb

Linux第四讲:Git && gdb 1.版本控制器Git1.1理解版本控制1.2理解协作开发1.3Git的历史1.4Git的操作1.4.1仓库创建解释、仓库克隆操作1.4.2本地文件操作三板斧1.4.3文件推送详细问题 2.调试器 -- gdb/cgdb使用2.1调试的本质是什么2.2watch命令2.3set var命令…

react的创建与书写

一:创建项目 超全面详细一条龙教程!从零搭建React项目全家桶(上篇) - 知乎 1.创建一个文件夹,shift鼠标右键选择在此处打开powershell 2.为了加速npm下载速度,先把npm设置为淘宝镜像地址。 npm config s…

黄色校正电容102j100

1. 普通电容主要用于交流回路中的信号耦合或滤波。它们通常没有极性,容量较小,通常在几百皮法拉范围内。普通电容在电路中用于信号耦合或直流电路的电源滤波,而电解电容一般用于直流电路,容量较大,从几微法到数千微法…

DApp开发:定制化解决方案与源码部署的一站式指南

去中心化应用(DApp)随着区块链技术的发展,成为众多行业探索与创新的重要方向。无论是金融、供应链、游戏,还是社交和艺术市场,DApp都为传统业务模式带来了全新可能。然而,开发一款DApp并非易事,…

单元测试、集成测试、系统测试有什么区别

🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 单元测试、集成测试、系统测试有什么区别 1、粒度不同 集成测试bai粒度居中,单元测试粒度最小,系统du测试粒度最大。 2、测试方式不同…

学Linux的第八天

目录 管理进程 概念 程序、进程、线程 进程分类 查看进程 ps命令 unix 风格 bsd风格 GNU风格 top命令 格式 统计信息区 进程信息区:显示了每个进程的运行状态 kill命令 作用 格式 管理进程 概念 程序、进程、线程 程序: 二进制文件&…

Xshell,Shell的相关介绍与Linux中的权限问题

目录 XShell的介绍 Shell的运行原理 Linux当中的权限问题 Linux权限的概念 Linux权限管理 文件访问者的分类(人) 文件类型和访问权限(事物属性) 文件权限值的表示方法 文件访问权限的相关设置方法 如何改变文件的访问权…

RS®SZM 倍频器

_XLT_ R&SSZM 倍频器 R&SSZM 系列倍频器在 50 GHz 至 170 GHz 的频率范围内具有简便的操作性和精确的输出电平。它们可用于多种应用,例如在汽车领域使用测距雷达,在天文学中使用精密望远镜,在雷达干涉测量中用于分析地球表面。 特…

Unity3D学习FPS游戏(11)敌人AI巡逻(NavMesh)

前言:前面两篇博客已经实现了简单的敌人,但是呢,这样很无趣。因为敌人只会站在原地被攻击,所以本篇我们将实现敌人AI巡逻,让敌人动起来。 敌人AI巡逻 场景丰富一下导航网格NavMesh构建导航网格导航网格优化玩家被当作…