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

Leetcode 有效的数独

在这里插入图片描述

这段代码解决的是 验证一个数独是否有效 的问题,其算法思想是基于 规则校验和状态记录。具体思想如下:


算法思想

  1. 核心目标:

    • 检查每个数字在 同一行同一列同一个 3x3 子格 中是否重复。
  2. 状态记录:

    • 使用 3 个布尔二维数组分别记录:
      • 每行数字的出现情况 rows[i][num]
      • 每列数字的出现情况 cols[j][num]
      • 每个 3x3 子格数字的出现情况 boxes[boxIndex][num]
    • 通过这些状态数组,可以快速检查某个数字是否在对应位置已存在。
  3. 遍历与验证:

    • 遍历整个 9x9 的数独表格,对于每一个非空格的数字:
      • 计算数字对应的行、列和 3x3 子格索引。
      • 检查当前数字是否在对应行、列或 3x3 子格中已存在。
      • 如果存在,直接返回 false,表示数独无效。
      • 如果不存在,将该数字标记为已出现,更新状态数组。
    • 如果遍历完成未发现冲突,返回 true,表示数独有效。

算法步骤

1. 初始化数据结构

  • 定义三个布尔二维数组:rows[9][9], cols[9][9], boxes[9][9]
    • rows[i][num]: 记录第 i 行中数字 num+1 是否已经出现。
    • cols[j][num]: 记录第 j 列中数字 num+1 是否已经出现。
    • boxes[boxIndex][num]: 记录第 boxIndex 个 3x3 子格中数字 num+1 是否已经出现。

2. 遍历整个数独表格

  • 对于每个位置 (i, j)
    • 如果是空格('.'),直接跳过。
    • 将字符数字转换为整数索引 num,如字符 '5' 转换为整数 4(因为数组索引从 0 开始)。
    • 计算数字所属的 3x3 子格索引:boxIndex = (i / 3) * 3 + j / 3
      • 行和列分别除以 3 取整可以确定当前数字在哪一块 3x3 子格中。

3. 检查并标记状态

  • 检查状态数组:
    • 如果 rows[i][num] == true,说明第 i 行已经出现过数字 num+1
    • 如果 cols[j][num] == true,说明第 j 列已经出现过数字 num+1
    • 如果 boxes[boxIndex][num] == true,说明该 3x3 子格已经出现过数字 num+1
  • 如果任何一项为 true,直接返回 false
  • 否则,更新状态数组,将当前数字标记为已出现。

4. 返回结果

  • 如果遍历完成,未发现任何冲突,则返回 true,表示数独有效。

关键点说明

1. 如何定位到 3x3 子格?

  • 整个数独分为 9 个 3x3 子格:
    子格索引:
    0  1  2
    3  4  5
    6  7  8
    
  • 每个数字的位置 (i, j) 通过公式 (i / 3) * 3 + j / 3 定位到对应的子格索引。

2. 字符数字如何转换为数组索引?

  • 数独中数字以字符形式存储,例如 '5'
  • 将其转为整数索引:num = board[i][j] - '1'
    • '1' 转换为索引 0'9' 转换为索引 8

3. 为什么需要状态数组?

  • 状态数组是为了快速记录和检查数字的存在性。
  • 使用布尔值记录 truefalse,可以节省时间复杂度,相较于遍历行、列和子格的直接检查更加高效。

时间和空间复杂度分析

  1. 时间复杂度:

    • 遍历整个 9x9 表格,时间复杂度为 (O(9 \times 9) = O(81)),即常数级复杂度。
  2. 空间复杂度:

    • 使用了 3 个 9x9 的布尔数组,总空间为 (3 \times 9 \times 9 = O(243)),即常数级复杂度。

总结

  • 通过 遍历整个数独表格使用状态数组记录数字的出现情况,有效避免了重复检查,算法逻辑清晰且高效。
  • 算法充分利用了布尔数组在快速状态查询和标记上的优势,实现了对数独规则的校验。
class Solution {public boolean isValidSudoku(char[][] board) {boolean [][] rows = new boolean[9][9]; //rows[i][num]表示第i行是否出现过numboolean [][] cols = new boolean[9][9]; //cols[j][num]表示第j列是否出现过numboolean [][] boxes = new boolean[9][9]; //boxes[boxindex][num]表示第boxindex个3*3方格中是否出现过numfor(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {//首先跳过空格if(board[i][j] == '.') {continue;}//首先获取boxindexint boxindex = (i / 3) * 3 + (j / 3);//将字符数字转换为索引int num = board[i][j] - '1';if(rows[i][num] || cols[j][num] || boxes[boxindex][num]) {return false;}//然后标记rows[i][num] = true;cols[j][num] = true;boxes[boxindex][num] = true;}}return true;}
}

相关文章:

Leetcode 有效的数独

这段代码解决的是 验证一个数独是否有效 的问题&#xff0c;其算法思想是基于 规则校验和状态记录。具体思想如下&#xff1a; 算法思想 核心目标&#xff1a; 检查每个数字在 同一行、同一列 和 同一个 3x3 子格 中是否重复。 状态记录&#xff1a; 使用 3 个布尔二维数组分别…...

《Java核心技术 卷I》用户界面中首选项API

首选项API 在桌面程序中&#xff0c;通常都会存储用户首选项&#xff0c;如用户最后处理的文件、窗口的最后位置等。 利用Properties类可以很容易的加载和保存程序的配置信息&#xff0c;但有以下缺点&#xff1a; 有些操作系统没有主目录概念&#xff0c;很难为匹配文件找到…...

Android 中的 Zygote 和 Copy-on-Write 机制详解

在 Android 系统中&#xff0c;Zygote 是一个关键的进程&#xff0c;几乎所有的应用进程都是通过它 fork&#xff08;派生&#xff09;出来的。通过 Zygote 启动新进程的方式带来了显著的性能优势&#xff0c;这得益于 fork 操作和 Linux 中的 Copy-on-Write&#xff08;COW&am…...

【人工智能】从零开始用Python实现逻辑回归模型:深入理解逻辑回归的原理与应用

解锁Python编程的无限可能&#xff1a;《奇妙的Python》带你漫游代码世界 《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门&#xff01; 逻辑回归是一种经典的统计学习方法&#xff0c;用于分类问题尤其是二分类问题。它通过学习数据的特征和目标标签之间的…...

推荐一款功能强大的光学识别OCR软件:Readiris Dyslexic

Readiris Dyslexic是一款功能强大的光学识别OCR软件&#xff0c;可以扫描任何纸质文档并将其转换为完全可编辑的数字文件(Word&#xff0c;Excel&#xff0c;PDF)&#xff0c;然后用你喜欢的编辑器进行编辑。该软件提供了一种轻松创建&#xff0c;修改和签名PDF的完整解决方法&…...

Python爬虫----python爬虫基础

一、python爬虫基础-爬虫简介 1、现实生活中实际爬虫有哪些&#xff1f; 2、什么是网络爬虫&#xff1f; 3、什么是通用爬虫和聚焦爬虫&#xff1f; 4、为什么要用python写爬虫程序 5、环境和工具 二、python爬虫基础-http协议和chrome抓包工具 1、什么是http和https协议…...

css-50 Projects in 50 Days(3)

html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>旋转页面</title><link rel"sty…...

另外一种缓冲式图片组件的用法

文章目录 1. 概念介绍2. 使用方法2.1 基本用法2.2 缓冲原理3. 示例代码4. 内容总结我们在上一章回中介绍了"FadeInImage组件"相关的内容,本章回中将介绍CachedNetworkImage组件.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章回中介绍的CachedNetwo…...

字节青训-小C的外卖超时判断、小C的排列询问

目录 一、小C的外卖超时判断 问题描述 测试样例 解题思路&#xff1a; 问题理解 数据结构选择 算法步骤 最终代码&#xff1a; 运行结果&#xff1a; 二、小C的排列询问 问题描述 测试样例 最终代码&#xff1a; 运行结果&#xff1a; ​编辑 一、小C的外卖超时判断…...

PHP 伪静态详解及实现方法

概述 在现代 Web 开发中&#xff0c;URL 的设计对用户体验和搜索引擎优化&#xff08;SEO&#xff09;至关重要。动态 URL 虽然功能强大&#xff0c;但往往显得冗长且不友好。伪静态&#xff08;URL 重写&#xff09;技术通过将动态 URL 转换为静态样式&#xff0c;不仅提高了…...

Spring Boot 简单预览PDF例子

目录 前言 一、引入依赖 二、使用步骤 1.创建 Controller 处理 PDF 生成和预览 2.创建预览页面 总结 前言 使用 Spring Boot 创建一个生成 PDF 并进行预览的项目&#xff0c;你可以按以下步骤进行。我们将使用 Spring Boot、Thymeleaf、iText 等技术来完成这个任务。 一、引入…...

【魔珐有言-注册/登录安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被机器执行自动化程序攻击&#xff0c;存在如下风险&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露&#xff0c;不符合国家等级保护的要求。短信盗刷带来的拒绝服务风险 &#xff0c;造成用户无法登陆、注册&#xff0c;大量收到垃圾短信的…...

LabVIEW 使用 Snippet

在 LabVIEW 中&#xff0c;Snippet&#xff08;代码片段&#xff09; 是一个非常有用的功能&#xff0c;它允许你将 一小段可重用的代码 保存为一个 图形化的代码片段&#xff0c;并能够在不同的 VI 中通过拖放来使用。 什么是 Snippet&#xff1f; Snippet 就是 LabVIEW 中的…...

单片机_day3_GPIO

目录 1. 灯如何才能亮 1.1原理图 1.2 二极管 1.3 换了一个灯和原理图 ​编辑 1.4 三极管 1.4.1 NPN型三极管 1.4.2 PNP型三极管 2. 基本概念 3. 输入 3.1 浮空输入 3.2 上拉输入 3.3 下拉输入 3.4 模拟输入 4. 输出 4.1 推挽输出 4.2 开漏输出 如何让开漏输出…...

Python小游戏24——小恐龙躲避游戏

首先&#xff0c;你需要安装Pygame库。如果你还没有安装&#xff0c;可以通过以下命令安装&#xff1a; 【bash】 pip install pygame 【python】代码 import pygame import random # 初始化Pygame pygame.init() # 设置屏幕尺寸 screen_width 800 screen_height 600 screen …...

Python 的多态笔记

Python的多态实际是通过instance 实现的 class Person:def __init__(self, name,age):self.name nameself.age agedef feed_pet(self,pet):#isinastance(obj,类)-->判断obj,是不是这个类的对象&#xff0c;或者判断obj是不是该类的子类的对象if isinstance(pet, Pet):sel…...

go module使用

go module介绍 go module是go官⽅⾃带的go依赖管理库,在1.13版本正式推荐使⽤ go module可以将某个项⽬(⽂件夹)下的所有依赖整理成⼀个 go.mod ⽂件,⾥⾯写⼊了依赖的版本等 使⽤ go module之后我们可不⽤将代码放置在src下了 使⽤ go module 管理依赖后会在项⽬根⽬录下⽣成…...

c ++零基础可视化——数组

c 零基础可视化 数组 一些知识&#xff1a; 关于给数组赋值&#xff0c;一个函数为memset&#xff0c;其在cplusplus.com中的描述如下&#xff1a; void * memset ( void * ptr, int value, size_t num );Sets the first num bytes of the block of memory pointed by ptr to…...

CVE-2024-2961漏洞的简单学习

简单介绍 PHP利用glibc iconv()中的一个缓冲区溢出漏洞&#xff0c;实现将文件读取提升为任意命令执行漏洞 在php读取文件的时候可以使用 php://filter伪协议利用 iconv 函数, 从而可以利用该漏洞进行 RCE 漏洞的利用场景 PHP的所有标准文件读取操作都受到了影响&#xff1…...

计算机组成原理笔记----基础篇

计算机系统硬件软件 软件 ├── 系统软件 │ ├── 操作系统 │ └── 工具软件 └── 应用软件├── 办公软件├── 媒体软件└── 浏览器软件硬件 ├── 计算机硬件 │ ├── 中央处理器&#xff08;CPU&#xff09; │ ├── 存储设备 │ │ ├── …...

TheadLocal出现的内存泄漏具体泄漏的是什么?弱引用在里面有什么作用?什么情景什么问题?

首先ThreadLocal是什么就不介绍了&#xff01;这篇是讲讲里面的东西。 再简单说一下强引用和弱引用&#xff0c;举个例子&#xff0c;我们平常new出来的对象就是强引用的&#xff0c;在栈中有强引用&#xff0c;所以在gc的时候&#xff0c;堆中的实例对象不会被清除掉。 弱引…...

AI在电商平台中的创新应用:提升销售效率与用户体验的数字化转型

1. 引言 AI技术在电商平台的应用已不仅仅停留在基础的数据分析和自动化推荐上。随着人工智能的迅速发展&#xff0c;越来越多的电商平台开始将AI技术深度融合到用户体验、定价策略、供应链优化、客户服务等核心业务中&#xff0c;从而显著提升运营效率和用户满意度。在这篇文章…...

CTF-RE 从0到N:RC4

RC4加密算法简介 RC4是由Ron Rivest于1987年设计的一种流加密算法。它通过伪随机数生成器生成密钥流&#xff0c;并将该密钥流与明文进行异或运算来完成加密和解密。 RC4的加密流程 RC4主要包含两个阶段&#xff1a; 密钥调度算法 (Key Scheduling Algorithm, KSA)&#xff…...

HbuilderX 插件开发-模板创建

实现思路 使用HbuilderX 打开某个文档时右键点击的时候获取当前打开的文档内容使用 API 替换为自己的模板 示例 package.json {"id": "SL-HbuilderX-Tool","name": "SL-HbuilderX-Tool","description": "快速创建h…...

打造专业问答社区:Windows部署Apache Answer结合cpolar实现公网访问

文章目录 前言1. 本地安装Docker2. 本地部署Apache Answer2.1 设置语言选择简体中文2.2 配置数据库2.3 创建配置文件2.4 填写基本信息 3. 如何使用Apache Answer3.1 后台管理3.2 提问与回答3.3 查看主页回答情况 4. 公网远程访问本地 Apache Answer4.1 内网穿透工具安装4.2 创建…...

YOLO-SLD: An Attention Mechanism-ImprovedYOLO for License Plate Detection

摘要 车辆牌照检测在智能交通系统中发挥着关键作用。检测汽车、卡车和面包车等的牌照对于执法、监控和收费站操作非常有用。如何快速准确地检测牌照对牌照识别至关重要。然而&#xff0c;在现实世界复杂捕捉场景中&#xff0c;光照条件不均匀或牌照拍摄角度的倾斜会发生剧烈变…...

ArcGIS的汉字(亚洲文本)垂直标注

01 需求说明 实现ArcGIS的汉字&#xff08;亚洲文本的垂直标注&#xff09;。 启用 Maplex 标注引擎。 在标注 工具条上单击标注管理器按钮 。 选中要进行标注的图层旁边的复选框。 选择图层下方的标注分类。 单击符号。 选中 CJK 字符方向复选框。 仅当字体有垂直的文本度…...

【面试题】

1.UART 和 IIC 的区别 UART (Universal Asynchronous Receiver-Transmitter) 用途&#xff1a;用于异步串行通信。信号线&#xff1a;通常需要两根线&#xff08;TX 和 RX&#xff09;&#xff0c;有时还需一根地线。通信方式&#xff1a;点对点。数据传输&#xff1a;单向或…...

Leetcode 寻找峰值

为了实现时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)&#xff0c;可以使用二分查找法&#xff1a; 解题思路&#xff1a; 峰值的特性是&#xff1a;当前元素大于左右相邻元素。使用二分法&#xff1a; 如果 nums[mid] > nums[mid 1]&#xff0c;说明峰值在左侧或当前…...

探索大规模语言模型(LLM)在心理健康护理领域中的应用与潜力

概述 心理健康是公共卫生最重要的领域之一。根据美国国家精神卫生研究所&#xff08;NIMH&#xff09;的数据&#xff0c;到 2021 年&#xff0c;22.8% 的美国成年人将患上某种形式的精神疾病。在全球范围内&#xff0c;精神疾病占非致命性疾病负担的 30%&#xff0c;并被世界…...