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;}
};

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

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

相关文章

如何在VMware ESXI中创建Linux虚拟机并实现异地SSH远程访问

目录 ⛳️推荐 前言 1. 在VMware ESXI中创建Ubuntu虚拟机 2. Ubuntu开启SSH远程服务 3. 安装Cpolar工具 4. 使用SSH客户端远程访问Ubuntu 5. 固定TCP公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不…

21.1 基于Netty实现聊天

21.1 基于Netty实现聊天 一. 章节概述二. `Netty`介绍三. 阻塞与非阻塞1. 阻塞与非阻塞简介2. BIO同步阻塞3. NIO同步非阻塞4. AIO异步非阻塞IO5. 异步阻塞IO(用的极少)6. 总结四. Netty三种线程模型1. 单线程模型2. 多线程模型3. 主从线程模型五. 构建Netty服务器************…

MySQL索引失效的场景

创建一个名为test_db的数据库&#xff0c;并在其中创建一个名为test_table的表。该表包含多个字段&#xff0c;并在某些字段上创建索引。 CREATE DATABASE IF NOT EXISTS test_db;USE test_db;CREATE TABLE IF NOT EXISTS test_table (id INT PRIMARY KEY AUTO_INCREMENT,name…

Microsoft Visual C++ Redistributable的作用主要体现以及可以删除吗?

这些是Microsoft Visual C的不同版本的Redistributable&#xff08;可再发行组件包&#xff09;安装包&#xff0c;用于在用户的计算机上安装或更新必要的运行时库&#xff0c;以便运行使用这些版本的Visual C开发的应用程序。具体来说&#xff1a; Microsoft Visual C 2012 R…

在uniapp中使用swicth组件传递额外的参数方法

switch 开关选择器。 传多个参数时可以这样传参 <switch :checked"scope.row.status" change"event>switchChangeStatus(event, scope.row)" />

Linux之数字证书

新书速览|Ubuntu Linux运维从零开始学_ubuntu linux运维从零开始学 pdf 下载-CSDN博客 《Ubuntu Linux运维从零开始学&#xff08;Linux技术丛书&#xff09;》(肖志健)【摘要 书评 试读】- 京东图书 (jd.com) 随着网络环境的恶化&#xff0c;人们已经逐渐抛弃网络上面的明文…

【C++ 面试 - 面向对象】每日 3 题(六)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…

【RabbitMQ】高级特性

本文将介绍一些RabbitMQ的重要特性。 官方文档&#xff1a;Protocol Extensions | RabbitMQ 本文是使用的Spring整合RabbitMQ环境。 生产者发送确认(publish confirm) 当消息发送给消息队列&#xff0c;如何确保消息队列一定收到消息呢&#xff0c;RabbitMQ通过 事务机制 和 …

Java巅峰之路---进阶篇---面向对象(二)

Java巅峰之路---进阶篇---面向对象&#xff08;二&#xff09; 多态介绍多态调用成员的特点多态的优势、弊端以及解决方案综合练习 包和final包的介绍使用其他类的规则&#xff08;导包&#xff09;final关键字final的用途常量 权限修饰符和代码块权限修饰符的介绍四个权限修饰…

为什么需要文献综述模板和创建文献综述技巧

为什么需要文献综述模板&#xff1f; 文献综述模板可以作为特定主题的指南。如果您的时间有限&#xff0c;无法进行更多研究&#xff0c;文献综述大纲示例可以为您提供帮助&#xff0c;因为它可以为您提供您打算研究的内容的概述。 甚至各个领域的专业人士也依赖文学评论来了解…

Openstack 与 Ceph集群搭建(上): 规划与准备

文章目录 一、写在前面1. 网络架构2. 节点规划3. 软件版本4. 避坑指南 二、基础配置1. host配置2. 修改hostname名称3. 确保root账号能登录系统4. 配置NTP5. 配置免密登录 一、写在前面 近期将进行三节点的Openstack、Ceph集群混合部署&#xff0c;本人将详细记录该过程。在此…

Linux系统编程(14)UDP全双工通信和TCP半双工通信

一、UDP全双工通信 UDP通信基础&#xff1a; recvfrom函数 recvfrom 是一个用于接收数据的函数&#xff0c;&#xff0c;但 recvfrom 不仅接收数据&#xff0c;还可以获取发送数据的地址信息。 ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags, struct sock…

融资管理系统项目

系列文章目录 第一章 基础知识、数据类型学习 第二章 万年历项目 第三章 代码逻辑训练习题 第四章 方法、数组学习 第五章 图书管理系统项目 第六章 面向对象编程&#xff1a;封装、继承、多态学习 第七章 封装继承多态习题 第八章 常用类、包装类、异常处理机制学习 第九章 集…

指针的学习和理解

初级 1、指针的概念 在64位操作系统中&#xff0c;不管什么类型的指针都占8个字节 int a1; int* p&a;//p就是一个整型的指针&#xff0c;保存了a的地址2、指针和变量 int* p&a;* p100; // 等价于a100p //p&a*有两种定义&#xff1a; 定义的时候&#xff08;前…

IP报文详解

IP的作用 上一篇文章提到TCP的可靠传输机制&#xff0c;那么TCP有把数据从主机A到主机B的能力吗&#xff1f;答案是没有。而IP有这个能力&#xff0c;IP能够将数据从主机A跨网络传输到主机B的能力。那么一定能传输成功吗&#xff1f;答案肯定是否定的&#xff0c;会因为各种原…

使用 Python构建 Windows 进程管理器应用程序

在这篇博客中&#xff0c;我们将探讨如何使用 wxPython 构建一个简单的 Windows 进程管理器应用程序。这个应用程序允许用户列出当前系统上的所有进程&#xff0c;选择和终止进程&#xff0c;并将特定进程保存到文件中以供将来加载。 C:\pythoncode\new\manageprocess.py 全部…

普元EOS-数据实体运行时动态增加property

1 前言 在Java开发读取数据的时候&#xff0c;一般都采用ORM方式将数据表的字段映射到实体对象中。 数据表中有一个字段&#xff0c;实体对象就有一个字段。 但很多时候&#xff0c;我们在读取的数据和显示的数据不同&#xff0c;比如&#xff0c;读取的是部门id&#xff0c…

探索数据结构:图(一)之邻接矩阵与邻接表

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty’s blog 1. 图的定义 **图&#xff08;Graph&#xff09;**是数学和计算机科学中…

这周末,除非外面下钞票,否则谁也拦不住我玩《黑神话悟空》(附:两款可以玩转悟空的显卡推荐)

主播说联播 | 从“十分之三”到“悟空”,国潮有何出圈密码? 《黑神话:悟空》里的中国古建取景地,在这里! 这周末,除非外面下钞票,否则谁也拦不住我玩《黑神话悟空》(附:两款可以玩转悟空的显卡推荐) 原创 IPBrain平台君 集成电路大数据平台 2024年08月22日 17:28 …

gif图片怎么压缩大小?深度测评7款动图压缩工具(内含教程)

gif图片在社交媒体和网络上非常流行&#xff0c;深受大家喜爱&#xff0c;因为它可以呈现生动的动画效果。gif动图之所以受到欢迎&#xff0c;主要因为其出色的压缩算法&#xff0c;能有效存储多个帧&#xff0c;从而实现流畅的动画。 然而&#xff0c;大多数社交媒体平台对gi…