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)时。自定义序列化器方法可以帮助你在序列化和反序列化过程中执行特定的逻辑,比如格式化日期、计算字段值、或者…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
