Leetcode刷题详解—— 有效的数独

1. 题目链接:36. 有效的数独

2. 题目描述:

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 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)或者 '.'

3. 解法:

3.1 算法思路:

创建三个数组标记行、列以及3*3小方格中是否会出现1~9之间的数字即可

  1. 遍历数独板的每一行和每一列。
  2. 如果当前位置不是空位(即数字),则将该数字转换为整数形式。
  3. 检查该数字是否已经在对应的行、列或子网格中出现过。如果已经出现过,则返回false,表示数独无效。
  4. 如果该数字没有在对应的行、列或子网格中出现过,则标记该数字已经出现过。
  5. 如果所有数字都没有重复出现,则返回true,表示数独有效。

请添加图片描述

3.2 C++算法代码:

class Solution {bool row[9][10]; // 用于记录每一行的数字是否出现过bool col[9][10]; // 用于记录每一列的数字是否出现过bool grid[3][3][10]; // 用于记录每一个3x3的子网格中的数字是否出现过
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i=0;i<9;i++) { // 遍历每一行for(int j=0;j<9;j++) { // 遍历每一列if(board[i][j]!='.') { // 如果当前位置不是空位int num=board[i][j]-'0'; // 将字符转换为数字if(row[i][num] || col[j][num] || grid[i/3][j/3][num]) // 如果该数字已经在对应的行、列或子网格中出现过return false; // 返回false,表示数独无效row[i][num]=col[j][num]=grid[i/3][j/3][num]=true; // 标记该数字已经出现过}}}return true; // 如果所有数字都没有重复出现,则返回true,表示数独有效}
};

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

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

相关文章

U-Mail邮件中继,让海外邮件沟通更顺畅

在海外&#xff0c;电子邮件是人们主要的通信工具&#xff0c;尤其是商务往来沟通&#xff0c;企业邮箱是标配。这主要是因为西方国家互联网发展较早&#xff0c;在互联网早期&#xff0c;电子邮件技术较为成熟&#xff0c;大家都用电子邮件交流&#xff0c;于是这成了一种潮流…

Jenkins简介及Docker Compose部署

Jenkins是一个开源的自动化服务器&#xff0c;用于自动化构建、测试和部署软件项目。它提供了丰富的插件生态系统&#xff0c;支持各种编程语言和工具&#xff0c;使得软件开发流程更加高效和可靠。在本文中&#xff0c;我们将介绍Jenkins的基本概念&#xff0c;并展示如何使用…

2023年第十六届山东省职业院校技能大赛中职组“网络安全”赛项规程

第十六届山东省职业院校技能大赛 中职组“网络安全”赛项规程 一、赛项名称 赛项名称&#xff1a;网络安全 英文名称&#xff1a;Cyber Security 赛项组别&#xff1a;中职组 专业大类&#xff1a;电子与信息大类 二、竞赛目的 网络空间已经成为陆、海、空、天之后的第…

C/C++满足条件的数累加 2021年9月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

目录 C/C满足条件的数累加 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C满足条件的数累加 2021年9月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 现有n个整数&#xff0c;将其中个位数…

linux安装并配置git连接github

git安装 sudo apt-get install git git信息配置 git config --global uer.name "yourname" git config --global user.email "youremail" 其中&#xff0c;yourname是你在github上配置的用户名&#xff0c;youremail是你在github上设置的邮箱 查看git…

吃透 Spring 系列—MVC部分

目录 ◆ SpringMVC简介 - SpringMVC概述 - SpringMVC快速入门 - Controller中访问容器中的Bean - SpringMVC关键组件浅析 ◆ SpringMVC的请求处理 - 请求映射路径的配置 - 请求数据的接收 - Javaweb常用对象获取 - 请求静态资源 - 注解驱动 标签 ◆ SpringMV…

STL简介+浅浅了解string——“C++”

各位CSDN的uu们好呀&#xff0c;终于到小雅兰的STL的学习了&#xff0c;下面&#xff0c;让我们进入CSTL的世界吧&#xff01;&#xff01;&#xff01; 1. 什么是STL 2. STL的版本 3. STL的六大组件 4. STL的重要性 5. 如何学习STL 6.STL的缺陷 7.为什么要学习string类 …

AIGC专栏8——EasyPhoto 视频领域拓展-让AIGC肖像动起来

AIGC专栏8——EasyPhoto 视频领域初拓展-让AIGC肖像动起来 学习前言源码下载地址技术原理储备Video Inference 功能说明 & 效果展示1、Text2Video功能说明a、实现原理简介b、文到视频UI介绍c、结果展示 2、Image2Video功能说明a、实现原理简介i、单图模式ii、首尾图模式 b、…

react 组件进阶

目标&#xff1a;1.能够使用props接收数据 2.能够实现父子组建之间的通讯 3.能够实现兄弟组建之间的通讯 4.能够给组建添加props校验 5.能够说出生命周期常用的钩子函数 6.能够知道高阶组件的作用 一&#xff0c;组件通讯介绍 组件是独立且封闭的单元&#xff0c;默认情况下&a…

【PyQt】(自制类)处理鼠标点击逻辑

写了个自认为还算不错的类&#xff0c;用于简化mousePressEvent、mouseMoveEvent和mouseReleaseEvent中的鼠标信息。 功能有以下几点&#xff1a; 鼠标当前状态&#xff0c;包括鼠标左/中/右键和单击/双击/抬起鼠标防抖(仅超出一定程度时才判断鼠标发生了移动)&#xff0c;灵…

mysql主从复制-使用心得

文章目录 前言环境配置主库从库 STATEMENTbinloggtidlog-errorDistSQL总结 前言 mysql 主从复制使用感受&#xff0c;遇到一些问题的整理&#xff0c;也总结了一些排查问题技巧。 环境 mysql5.7 配置 附&#xff1a;千万级数据快速插入配置可以参考&#xff1a;mysql千万数…

112. 路径总和

描述 : 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 叶子节点 是指没…

Ubuntu 创建并发布 Django 项目

Ubuntu 创建并发布 Django 项目 升级操作系统和软件 sudo apt updatesudo apt -y dist-upgrade 安装 python3-pip sudo apt -y install python3-pip安装 django pip install -i https://pypi.tuna.tsinghua.edu.cn/simple djangosudo apt -y install python3-django创建 dj…

RT-Thread:嵌入式实时操作系统的设计与应用

RT-Thread&#xff08;Real-Time Thread&#xff09;是一个开源的嵌入式实时操作系统&#xff0c;其设计和应用在嵌入式领域具有重要意义。本文将从RT-Thread的设计理念、核心特性&#xff0c;以及在嵌入式系统中的应用等方面进行探讨&#xff0c;对其进行全面的介绍。 首先&a…

2023/11/12总结

踩坑记录&#xff1a; org.springframework.jdbc.BadSqlGrammarException: ### Error querying database. Cause: java.sql.SQLSyntaxErrorException: Expression #1 of SELECT list is not in GROUP BY clause and contains nonaggregated column elm.flavors.id which is …

【FAQ】Gradle开发问题汇总

1. buildSrc依赖Spring Denpendency时报错 来自预编译脚本的插件请求不能包含版本号。请从有问题的请求中删除该版本&#xff0c;并确保包含所请求插件io.spring.dependency-management的模块是一个实现依赖项 解决方案 https://www.5axxw.com/questions/content/uqw0grhttps:/…

生成式AI - Knowledge Graph Prompting:一种基于大模型的多文档问答方法

大型语言模型&#xff08;LLM&#xff09;已经彻底改变了自然语言处理&#xff08;NLP&#xff09;任务。它们改变了我们与文本数据交互和处理的方式。这些强大的AI模型&#xff0c;如OpenAI的GPT-4&#xff0c;改变了理解、生成人类类似文本的方式&#xff0c;导致各种行业出现…

Spring基础——初探

Spring是一个开源的Java应用程序开发框架&#xff0c;它提供了一个综合的编程和配置模型&#xff0c;用于构建现代化的企业级应用程序。Spring的目标是简化Java开发&#xff0c;并提供了许多功能和特性&#xff0c;以提供开发效率、降低开发复杂性。 特别 主要功能 IoC容器 …

SpringBootWeb案例——Tlias智能学习辅助系统(3)——登录校验

前一节已经实现了部门管理、员工管理的基本功能。但并没有登录&#xff0c;就直接访问到了Tlias智能学习辅助系统的后台&#xff0c;这节来实现登录认证。 目录 登录功能登录校验(重点)会话技术会话跟踪方案一 Cookie&#xff08;客户端会话跟踪技术&#xff09;会话跟踪方案二…

ROS基础知识复习

【置顶】感谢参考&#xff1a;https://zhuanlan.zhihu.com/p/662074088 0.背景 工作一年多没有做 ROS 相关的开发了&#xff0c;最近找工作想做回这一块来&#xff0c;根据参考内容&#xff0c;抽时间给这边的基础知识敲一遍复习一下 1.环境检查 打开了之前的笔记本&#x…