当前位置: 首页 > 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;比如格式化日期、计算字段值、或者…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...