36. 有效的数独【 力扣(LeetCode) 】
一、题目描述
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
- 一个有效的数独(部分已被填充)不一定是可解的。
- 只需要根据以上规则,验证已经填入的数字是否有效即可。
- 空白格用 ‘.’ 表示。
二、测试用例
示例 1:

输入: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
示例 2:
输入: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)或者 '.'
三、解题思路
- 基本思路:
一力破万法,检查是否满足数独的三个条件就可以了。 - 具体思路:一次遍历就可以检查三个条件,就是需要一些技巧。
- 行唯一:判断每一行中出现的数字是否唯一 【正常遍历】
- 列唯一:判断每一列中出现的数字是否唯一 【行列交换】
- 九宫格唯一:判断每一个九宫格中出现的数字是否唯一 【特殊映射】
四、参考代码
时间复杂度: O ( 1 ) \Omicron(1) O(1)【数独是固定大小的,所以都是常数级复杂度】
空间复杂度: O ( 1 ) \Omicron(1) O(1)【数独是固定大小的,所以都是常数级复杂度】
class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {int n = board.size(), m = board[0].size();for (int i = 0; i < n; i++) {vector<vector<bool>> num(3, vector<bool>(m, false));for (int j = 0; j < m; j++) { // 行唯一if (board[i][j] != '.') {if (num[0][board[i][j] - '1']) {return false;} else {num[0][board[i][j] - '1'] = true;}}if (board[j][i] != '.') { // 列唯一if (num[1][board[j][i] - '1']) {return false;} else {num[1][board[j][i] - '1'] = true;}}int r = i / 3 * 3 + j / 3, c = (i % 3) * 3 + j % 3;if (board[r][c] != '.') { // 九宫格唯一if (num[2][board[r][c] - '1']) {return false;} else {num[2][board[r][c] - '1'] = true;}}}}return true;}
};
相关文章:
36. 有效的数独【 力扣(LeetCode) 】
一、题目描述 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图…...
机器学习中的没有免费午餐定理
嘿,各位机器学习的爱好者们!今天,让我们一起深入探讨机器学习中那个神秘而又重要的概念——没有免费午餐定理。 一、定理引入:探索算法森林的钥匙 在广阔无垠的机器学习领域中,免费午餐定理就如同一把神奇的钥匙&…...
高级java每日一道面试题-2024年8月21日-框架篇[Spring篇]-使用IOC容器应该注意哪些?
如果有遗漏,评论区告诉我进行补充 面试官: 使用IOC容器应该注意哪些? 我回答: 1. 理解IOC的基本概念 控制反转:在传统的编程模式中,程序会主动控制依赖关系的创建和管理。而在IoC容器中,这种控制权被反转给了容器本身。程序员只需要声明…...
LLM训练推理相关概念
1. 有监督微调(Supervised Fine-Tuning)与指令微调(Instruction Fine-Tuning)对模型参数的影响 **有监督微调(Supervised Fine-Tuning, SFT)和指令微调(Instruction Fine-Tuning, Instruct-Tun…...
IP in IP 协议
IP in IP 是一种多重IP协议,即:客户机可以发送一个IP协议内部在嵌套一个IP协议到某个特定的主机上,在由具体的主机作为路由进行转发的协议。 例如: IP in IP帧协议结构为,第一层为发送到IP in IP 路由主机的报文&…...
DAY2: HTTP请求报文和响应报文是怎样的,有哪些常见的字段?| HTTP有哪些请求方式?| GET请求和POST请求的区别
目录 HTTP请求报文和响应报文是怎样的,有哪些常见的字段? 请求报文 响应报文 HTTP有哪些请求方式? GET请求和POST请求的区别 HTTP请求报文和响应报文是怎样的,有哪些常见的字段? HTTP报文分为请求报文和响应报文…...
线性代数:每日一题1/特征值与相似对角化
设A, B 为二阶矩阵,且 AB BA , 则“A有两个不相等的特征值”是“B可对角化"的() A. 充分必要条件 B. 充分不必要条件 C.必要不充分条件 D.既不充分也不必要条件 知识点: 特征向量与特征值的关系 相似矩阵的定义和性质 n阶…...
Android UI:PopupWindow:API
文章目录 类操作 对PopupWindow的操作 创建PopupWindow对象的操作添加并显示PopupWindow的操作移除PopupWindow的操作更新PopupWindow的操作显示内容的相关操作 布局的相关操作进入退出动画的相关操作 Transition设置进入动画的相关操作Transition设置退出动画的相关操作XML设置…...
什么是DevUI?
DevUI是面向企业中后台产品的开源前端解决方案,其设计价值观基于"高效、开放、可信、乐趣"四种自然与人文相结合的理念,旨在为设计师、前端开发者提供标准的设计体系,并满足各类落地场景,是一款企业级开箱即用的产品。 …...
DAY53
作业: 运行1个服务器和2个客户端 实现效果: 服务器和2个客户端互相聊天,服务器和客户端都需要使用select模型去实现 服务器要监视2个客户端是否连接,2个客户端是否发来消息以及服务器自己的标准输入流 客户端要监视服务器是否发来…...
python中len是什么
Python len() 方法返回字符串长度。 len()方法语法: len( str ) 返回值: 返回字符串长度。 以下实例展示了len()的使用方法: #!/usr/bin/python str "this is string example....wow!!!"; print "字符串长度: ", len…...
推荐一个开源的kafka可视化客户端GUI工具(Kafka King)
大佬的博客地址: https://blog.ysboke.cn/posts/tools/kafka-king Github地址: https://github.com/Bronya0/Kafka-King Kafka-King功能清单 查看集群节点列表(完成)支持PLAINTEXT、SASL PLAINTEXT用户名密码认证(完…...
day 10 贪心算法
455. 分发饼干 饼干从大的开始利用,优先满足胃口大的; class Solution { public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int res0;int indexs.size()-1;for…...
网络安全审计技术原理与应用
网络安全审计概述 概念 定义:对网络信息系统的安全相关活动信息进行获取、记录、存储、分析和利用的工作 作用:建立“事后”安全保障措施,保存网络安全事件及行为信息,为网络安全事件分析提供线索及证据,以便发现潜在网络安全威胁行为,开展网络安全风险分析及管理 常…...
计算机网络之TCP序号,确认序号和报文传输时间
开篇提示 本篇适合于了解基础知识,进行扩展提高的使用,附带考研习题以及解析。 TCP序号和确认序号的区别 TCP首部中有序号和确认序号,他们都是4个字节(4B),且在数据传输中有很重要的意义,那么两…...
HTML优化方法
HTML编码规范 代码格式化与缩进 1.缩进规则 推荐使用空格缩进而不是Tab,因为不同环境下空格的效果更加一致。常见缩进量为2个或4个空格 2.标签对齐 在嵌套的HTML结构中,子标签应当缩进,以清晰地展示层级关系。 3.属性的排列 …...
Codeforces Round 961 D. Cases 【SOS DP、思维】
D. Cases 题意 有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串,问最少选取多少种字母为每个单词的结尾,使得每个单词长度不超过 k k k 思路 首先注意到最后一个字母一定要选择,接下来我们给出一个断言:如果一个…...
VirtualBox上的Oracle Linux虚拟机安装Docker全流程
1.安装docker依赖 yum install -y yum-utils device-mapper-persistent-data lvm2 2.安装docker仓库 yum-config-manager --add-repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo 生成docker的yum源配置到在 /etc/yum.repos.d/docker-ce.repo 3.安装D…...
LNMP安装部署
目录 一、Nginx安装部署 1.安装包下载 2.下载相关依赖工具 3. 创建运行用户 4.编译安装 5.优化路径 6.将nginx添加至系统服务 7.文件赋权 二、MySQL部署安装 1.解压 2.安装相关工具 3.创建运行用户 4.编译安装 5.修改配置文件 6.更改mysql安装目录和配置文件的属…...
django之自定义序列化器用法
在Django中,自定义序列化器方法通常用于处理复杂的数据转换逻辑,特别是在使用Django REST framework(DRF)时。自定义序列化器方法可以帮助你在序列化和反序列化过程中执行特定的逻辑,比如格式化日期、计算字段值、或者…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
