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)时。自定义序列化器方法可以帮助你在序列化和反序列化过程中执行特定的逻辑,比如格式化日期、计算字段值、或者…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
