当前位置: 首页 > news >正文

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)或者 '.'

三、解题思路

  1. 基本思路:
      一力破万法,检查是否满足数独的三个条件就可以了。
  2. 具体思路:一次遍历就可以检查三个条件,就是需要一些技巧。
    • 行唯一:判断每一行中出现的数字是否唯一 【正常遍历】
    • 列唯一:判断每一列中出现的数字是否唯一 【行列交换】
    • 九宫格唯一:判断每一个九宫格中出现的数字是否唯一 【特殊映射】

四、参考代码

时间复杂度: 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 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考示例图…...

机器学习中的没有免费午餐定理

嘿&#xff0c;各位机器学习的爱好者们&#xff01;今天&#xff0c;让我们一起深入探讨机器学习中那个神秘而又重要的概念——没有免费午餐定理。 一、定理引入&#xff1a;探索算法森林的钥匙 在广阔无垠的机器学习领域中&#xff0c;免费午餐定理就如同一把神奇的钥匙&…...

高级java每日一道面试题-2024年8月21日-框架篇[Spring篇]-使用IOC容器应该注意哪些?

如果有遗漏,评论区告诉我进行补充 面试官: 使用IOC容器应该注意哪些? 我回答: 1. 理解IOC的基本概念 控制反转&#xff1a;在传统的编程模式中&#xff0c;程序会主动控制依赖关系的创建和管理。而在IoC容器中&#xff0c;这种控制权被反转给了容器本身。程序员只需要声明…...

LLM训练推理相关概念

1. 有监督微调&#xff08;Supervised Fine-Tuning&#xff09;与指令微调&#xff08;Instruction Fine-Tuning&#xff09;对模型参数的影响 **有监督微调&#xff08;Supervised Fine-Tuning, SFT&#xff09;和指令微调&#xff08;Instruction Fine-Tuning, Instruct-Tun…...

IP in IP 协议

IP in IP 是一种多重IP协议&#xff0c;即&#xff1a;客户机可以发送一个IP协议内部在嵌套一个IP协议到某个特定的主机上&#xff0c;在由具体的主机作为路由进行转发的协议。 例如&#xff1a; IP in IP帧协议结构为&#xff0c;第一层为发送到IP in IP 路由主机的报文&…...

DAY2: HTTP请求报文和响应报文是怎样的,有哪些常见的字段?| HTTP有哪些请求方式?| GET请求和POST请求的区别

目录 HTTP请求报文和响应报文是怎样的&#xff0c;有哪些常见的字段&#xff1f; 请求报文 响应报文 HTTP有哪些请求方式&#xff1f; GET请求和POST请求的区别 HTTP请求报文和响应报文是怎样的&#xff0c;有哪些常见的字段&#xff1f; HTTP报文分为请求报文和响应报文…...

线性代数:每日一题1/特征值与相似对角化

设A, B 为二阶矩阵&#xff0c;且 AB BA , 则“A有两个不相等的特征值”是“B可对角化"的&#xff08;&#xff09; A. 充分必要条件 B. 充分不必要条件 C.必要不充分条件 D.既不充分也不必要条件 知识点&#xff1a; 特征向量与特征值的关系 相似矩阵的定义和性质 n阶…...

Android UI:PopupWindow:API

文章目录 类操作 对PopupWindow的操作 创建PopupWindow对象的操作添加并显示PopupWindow的操作移除PopupWindow的操作更新PopupWindow的操作显示内容的相关操作 布局的相关操作进入退出动画的相关操作 Transition设置进入动画的相关操作Transition设置退出动画的相关操作XML设置…...

什么是DevUI?

DevUI是面向企业中后台产品的开源前端解决方案&#xff0c;其设计价值观基于"高效、开放、可信、乐趣"四种自然与人文相结合的理念&#xff0c;旨在为设计师、前端开发者提供标准的设计体系&#xff0c;并满足各类落地场景&#xff0c;是一款企业级开箱即用的产品。 …...

DAY53

作业&#xff1a; 运行1个服务器和2个客户端 实现效果&#xff1a; 服务器和2个客户端互相聊天&#xff0c;服务器和客户端都需要使用select模型去实现 服务器要监视2个客户端是否连接&#xff0c;2个客户端是否发来消息以及服务器自己的标准输入流 客户端要监视服务器是否发来…...

python中len是什么

Python len() 方法返回字符串长度。 len()方法语法&#xff1a; len( str ) 返回值&#xff1a; 返回字符串长度。 以下实例展示了len()的使用方法&#xff1a; #!/usr/bin/python str "this is string example....wow!!!"; print "字符串长度: ", len…...

推荐一个开源的kafka可视化客户端GUI工具(Kafka King)

大佬的博客地址&#xff1a; https://blog.ysboke.cn/posts/tools/kafka-king Github地址&#xff1a; https://github.com/Bronya0/Kafka-King Kafka-King功能清单 查看集群节点列表&#xff08;完成&#xff09;支持PLAINTEXT、SASL PLAINTEXT用户名密码认证&#xff08;完…...

day 10 贪心算法

455. 分发饼干 饼干从大的开始利用&#xff0c;优先满足胃口大的&#xff1b; 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序号,确认序号和报文传输时间

开篇提示 本篇适合于了解基础知识&#xff0c;进行扩展提高的使用&#xff0c;附带考研习题以及解析。 TCP序号和确认序号的区别 TCP首部中有序号和确认序号&#xff0c;他们都是4个字节&#xff08;4B&#xff09;&#xff0c;且在数据传输中有很重要的意义&#xff0c;那么两…...

HTML优化方法

HTML编码规范 代码格式化与缩进 1.缩进规则 ​ 推荐使用空格缩进而不是Tab&#xff0c;因为不同环境下空格的效果更加一致。常见缩进量为2个或4个空格 2.标签对齐 ​ 在嵌套的HTML结构中&#xff0c;子标签应当缩进&#xff0c;以清晰地展示层级关系。 3.属性的排列 ​ …...

Codeforces Round 961 D. Cases 【SOS DP、思维】

D. Cases 题意 有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串&#xff0c;问最少选取多少种字母为每个单词的结尾&#xff0c;使得每个单词长度不超过 k k k 思路 首先注意到最后一个字母一定要选择&#xff0c;接下来我们给出一个断言&#xff1a;如果一个…...

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中&#xff0c;自定义序列化器方法通常用于处理复杂的数据转换逻辑&#xff0c;特别是在使用Django REST framework&#xff08;DRF&#xff09;时。自定义序列化器方法可以帮助你在序列化和反序列化过程中执行特定的逻辑&#xff0c;比如格式化日期、计算字段值、或者…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...