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

LeetCode【0036】有效的数独

本文目录

  • 1 中文题目
  • 2 求解方法:python内置函数set
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

请根据以下规则判断一个 9 x 9 的数独是否有效。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(见下方的参考示例图)

注意

  • 一个有效的数独(部分已被填充)不一定是可解的。
  • 只需要根据以上规则,验证已经填入的数字是否有效即可。
  • 空白格用 ‘.’ 表示。

示例:

在这里插入图片描述

对于上面的数独,其输入格式如下:
输入: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
输入: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)或者 ‘.

2 求解方法:python内置函数set

2.1 方法思路

方法核心

  • 使用三组集合分别记录每行、每列和每个3x3方块中已出现的数字
  • 一次遍历完成所有验证
  • 使用数学公式计算粗实线分割出来的3x3方块的索引

实现步骤

(1)初始化数据结构:

  • 创建9个集合用于存储每行的数字
  • 创建9个集合用于存储每列的数字
  • 创建9个集合用于存储每个3x3方块的数字

(2)遍历数独板:

  • 双层循环遍历9x9的数独板
  • 对于每个位置,获取当前数字
  • 跳过空格(用’.'表示)
  • 计算当前位置所在的3x3方块的索引
  • 检查数字是否重复出现
  • 将不重复的数字添加到对应集合中

(3)验证过程:

  • 检查当前数字是否已在当前行出现
  • 检查当前数字是否已在当前列出现
  • 检查当前数字是否已在当前3x3方块出现
  • 如果出现重复,立即返回False
  • 如果遍历完成没有重复,返回True

方法示例

输入数独板示例(部分):
[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],...
]详细执行过程:1. 初始化:rows = [set(), set(), set(), ...] (9个空集合)cols = [set(), set(), set(), ...] (9个空集合)boxes = [set(), set(), set(), ...] (9个空集合)2. 处理第一个位置 (0,0)- 数字为 "5"- box_index = (0 // 3) * 3 + (0 // 3) = 0- 检查 rows[0], cols[0], boxes[0] 都不包含 "5"-"5" 添加到这三个集合中3. 处理第二个位置 (0,1)- 数字为 "3"- box_index = (0 // 3) * 3 + (1 // 3) = 0- 检查集合,添加数字4. 继续处理每个位置...示例中3x3方块索引的计算:
- 位置(0,0): (0//3)*3 + 0//3 = 0
- 位置(0,4): (0//3)*3 + 4//3 = 1
- 位置(4,4): (4//3)*3 + 4//3 = 4

2.2 Python代码

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:# 初始化用于存储每行、每列和每个3x3方块中数字出现情况的集合rows = [set() for _ in range(9)]cols = [set() for _ in range(9)]boxes = [set() for _ in range(9)]# 遍历整个数独板for i in range(9):for j in range(9):# 获取当前位置的数字num = board[i][j]# 如果是空格,继续下一个位置if num == '.':continue# 计算当前位置所在的3x3方块的索引# box_index = (行号 // 3) * 3 + (列号 // 3)box_index = (i // 3) * 3 + j // 3# 检查当前数字是否已经在对应的行、列或3x3方块中出现过if (num in rows[i] or num in cols[j] or num in boxes[box_index]):return False# 将当前数字添加到对应的集合中rows[i].add(num)cols[j].add(num)boxes[box_index].add(num)# 遍历完成且没有发现重复,返回Truereturn True

2.3 复杂度分析

  • 时间复杂度:O(1)
    • 固定大小的9x9网格
    • 遍历一次数独数组
    • 每次检查和添加操作都是O(1)
    • 总操作次数是常数
  • 空间复杂度:O(1)
    • 使用固定大小的集合
    • 9个集合用于行
    • 9个集合用于列
    • 9个集合用于3x3方块

3 题目总结

题目难度:中等
数据结构:二维数组
应用算法:Python内置函数set

相关文章:

LeetCode【0036】有效的数独

本文目录 1 中文题目2 求解方法:python内置函数set2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 请根据以下规则判断一个 9 x 9 的数独是否有效。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线…...

Typecho登陆与评论添加Geetest极验证,支持PJAX主题(如Handsome)

Typecho登陆与评论添加Geetest极验证,支持PJAX主题(如Handsome) 起因 最近垃圾评论比较多,为了防止一些机器人,我给博客添加了一些评论过滤机制,并为评论添加了验证码。 原本使用的插件是noisky/typecho…...

前端入门一之ES6--面向对象、够着函数和原型、继承、ES5新增方法、函数进阶、严格模式、高阶函数、闭包

前言 JS是前端三件套之一,也是核心,本人将会更新JS基础、JS对象、DOM、BOM、ES6等知识点,这篇是ES6;这篇文章是本人大一学习前端的笔记;欢迎点赞 收藏 关注,本人将会持续更新。 文章目录 JS高级 ES61、面向对象1.1…...

脑机接口、嵌入式 AI 、工业级 MR、空间视频和下一代 XR 浏览器丨RTE2024 空间计算和新硬件专场回顾

这一轮硬件创新由 AI 引爆,或许最大受益者仍是 AI,因为只有硬件才能为 AI 直接获取最真实世界的数据。 在人工智能与硬件融合的新时代,实时互动技术正迎来前所未有的创新浪潮。从嵌入式系统到混合现实,从空间视频到脑机接口&…...

RoseTTAFold MSA_emb类解读

MSA_emb 类的作用是对多序列对齐(MSA)数据进行嵌入编码,同时添加位置编码和查询编码(调用PositionalEncoding 和 QueryEncoding)以便为序列特征建模类。 源代码: class MSA_emb(nn.Module):def __init__(self, d_model=64, d_msa=21, p_drop=0.1, max_len=5000):super(…...

2411C++,C++26反射示例

参考 namespace __impl {template<auto... vals>struct replicator_type {template<typename F>constexpr void operator>>(F body) const {(body.template operator()<vals>(), ...);}};template<auto... vals>replicator_type<vals...>…...

Ubuntu上搭建Flink Standalone集群

Ubuntu上搭建Flink Standalone集群 本文部分内容转自如下链接。 环境说明 ubuntu 22.06 先执行apt-get update更新环境 第1步 安装JDK 通过apt自动拉取 openjdk8 apt-get install openjdk-8-jdk执行java -version&#xff0c;如果能显示Java版本号&#xff0c;表示安装并…...

C语言 精选真题2

题目要求&#xff1a;将形参s所指向的字符串转换为整数并且返回 知识点&#xff1a; 将字符1转化为整数1 int fun(char *s) {int flag1,n0; if(*s-) //先根据第一个符号来判断是正负&#xff1b;然后读取第二位{flag-1;s; }else if(*s){s;}while(*s>0&&…...

Netty篇(WebSocket)

目录 一、简介 二、特点 三、websock应用场景 四、websocket案例 1. 服务端 2. 处理器 3. 页面端处理 五、参考文献 一、简介 没有其他技术能够像WebSocket一样提供真正的双向通信&#xff0c;许多web开发者仍然是依赖于ajax的长轮询来 实现。&#xff08;注&#xff…...

云原生-docker安装与基础操作

一、云原生 Docker 介绍 Docker 在云原生中的优势 二、docker的安装 三、docker的基础命令 1. docker pull&#xff08;拉取镜像&#xff09; 2. docker images&#xff08;查看本地镜像&#xff09; 3. docker run&#xff08;创建并启动容器&#xff09; 4. docker ps…...

MySQL数据库:SQL语言入门 【上】(学习笔记)

SQL&#xff08;Structured Query Language&#xff09;是结构化查询语言的简称&#xff0c;它是一种数据库查询和程序设计语言&#xff0c;同时也是目前使用最广泛的关系型数据库操作语言。&#xff08;95%适用于所有关系型数据库&#xff09; 【 SQL是关系型数据库通用的操作…...

重学 Android 自定义 View 系列(六):环形进度条

目标 自定义一个环形进度条&#xff0c;可以自定义其最大值、当前进度、背景色、进度色&#xff0c;宽度等信息。 最终效果如下&#xff08;GIF展示纯色有点问题&#xff09;&#xff1a; 1. 结构分析 背景圆环&#xff1a;表示进度条的背景。进度圆环&#xff1a;表示当前…...

nodejs 020: React语法规则 props和state

props和state 在 React 中&#xff0c;props 和 state 是管理数据流的两种核心机制。理解它们之间的区别和用途是构建 React 应用程序的基础。 一、props 和 state的区别 特性propsstate定义方式由父组件传递给子组件的数据组件内部管理的本地数据是否可修改不可变&#xff…...

STM32问题集

这里写目录标题 一、烧录1、 Can not connect to target!【ST-LINK烧录】 一、烧录 1、 Can not connect to target!【ST-LINK烧录】 烧录突然 If the target is in low power mode, please enable “Debug in Low Power mode” option from Target->settings menu 然后就&…...

SwiftUI(十二)- 容器组件 布局与结构的基石

引言 在用户界面开发中&#xff0c;布局是设计一个应用程序的视觉层次和交互体验的核心之一。无论是设计简单的按钮排布&#xff0c;还是复杂的多层次页面&#xff0c;合理的布局和结构可以极大地提升用户体验。而容器组件&#xff0c;作为将多个视图整合、组织、排列的工具&a…...

想租用显卡训练自己的网络?AutoDL保姆级使用教程(PyCharm版)

各位小伙伴们大家好~ 不知道各位同学在科研过程中是否有这样的苦恼 电脑无显卡。难不成我要用CPU跑实验吗&#xff1f;救救我吧电脑显卡算力太低。训练过程慢慢慢慢慢&#xff0c;等半天都出不来结果电脑显卡显存不够&#xff0c;batchsize稍微高一点点&#xff0c;就要爆显存…...

LeetCode【0039】组合总和

本文目录 1 中文题目2 求解方法&#xff1a;回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 给定一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#…...

AscendC从入门到精通系列(一)初步感知AscendC

1 什么是AscendC Ascend C是CANN针对算子开发场景推出的编程语言&#xff0c;原生支持C和C标准规范&#xff0c;兼具开发效率和运行性能。基于Ascend C编写的算子程序&#xff0c;通过编译器编译和运行时调度&#xff0c;运行在昇腾AI处理器上。使用Ascend C&#xff0c;开发者…...

PostgreSQL中的COPY命令:高效数据导入与导出

在PostgreSQL数据库中&#xff0c;数据导入和导出是日常工作中常见的操作。传统的插入&#xff08;INSERT&#xff09;方法虽然可以实现数据的导入&#xff0c;但在处理大量数据时效率较低。而COPY命令则提供了一个快速、高效的方式来完成这一任务。COPY命令不仅可以用于将数据…...

【HAL库】STM32F105VCTx多通道ADC+DMA方式的【STM32CubeMX】配置及代码实现

相关代码编写 配置好后点击生成代码&#xff0c;在生成代码的adc.c文件中的初始化函数MX_ADC1_Init中添加如下代码&#xff1a; HAL_ADCEx_Calibration_Start(&hadc1); /* 校准ADC */HAL_ADC_Start_DMA(&hadc1,(uint32_t*)ADC_Value,ADC_DMA_…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...