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

LeetCode 36. 有效的数独

LeetCode 36. 有效的数独

难度:middle\color{orange}{middle}middle


题目描述

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

  1. 数字 1−91-919 在每一行只能出现一次。
  2. 数字 1−91-919 在每一列只能出现一次。
  3. 数字 1−91-919 在每一个以粗实线分隔的 3x33x33x3 宫内只能出现一次。(请参考示例图)

注意:

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

示例 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==9board.length == 9board.length==9
  • board[i].length==9board[i].length == 9board[i].length==9
  • board[i][j]board[i][j]board[i][j] 是一位数字(1−91-919)或者 ′.′'.'.

算法

(暴力枚举)

  • 判断每一行是否存在相同的数字。
  • 判断每一列是否存在相同的数字。
  • 判断每一个单独的小方格是否存在相同的数字。

复杂度分析

  • 时间复杂度O(1)O(1)O(1),数独共有 81 个单元格,只需要对每个单元格遍历即可。

  • 空间复杂度 : O(1)O(1)O(1),只需要一个判重数组即可。

C++ 代码

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {bool st[9];//判断行for (int i = 0; i < 9; i ++) {memset(st, 0, sizeof st);for (int j = 0; j < 9; j ++) {if (board[i][j] != '.') {int t = board[i][j] - '1';if (st[t]) return false;st[t] = true;}}}//判断列for (int i = 0; i < 9; i ++) {memset(st, 0, sizeof st);for (int j = 0; j < 9; j ++) {if (board[j][i] != '.') {int t = board[j][i] - '1';if (st[t]) return false;st[t] = true;}}}//判断小方格for (int i = 0; i < 9; i += 3) {for (int j = 0; j < 9; j += 3) {memset(st, 0, sizeof st);for (int x = 0; x < 3; x ++) {for (int y = 0; y < 3; y ++) {if (board[i + x][j + y] != '.') {int t = board[i + x][j + y] - '1';if (st[t]) return false;st[t] = true;}}}}}return true;}
};

相关文章:

LeetCode 36. 有效的数独

LeetCode 36. 有效的数独 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 请你判断一个 9x99 x 99x9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1−91-91−9 在每一行只能出现一次。数字 1−91-91−9 在每一列…...

2023-02-22 cascades-columbia-核心处理记录

摘要: columbia是哥伦比亚对于cascades的一个改进, 并且paper写的也相对详尽. 虽然cacades的实现有很多,比较出名的就是greenplum的gporca, 不过columbia也有其显著的优点. 本文通过对columbia的分析展开对cascades优化器思想的探讨. 参考: 2023-02-10 哥伦比亚cascades-xu-…...

华为分布式存储(FusionStorage)

Server SAN SAN&#xff1a;存储区域网络 IP SAN&#xff1a;以太网交换机和普通网线连接的存储&#xff0c;交换机之间做堆叠FC SAN&#xff1a;FC&#xff08;光纤&#xff09;交换机和光纤连接的存储&#xff0c;交换机之间做级联Server SAN&#xff1a;可以使用以太网交换机…...

说说 React 中 fiber、DOM、ReactElement、实例对象之间的引用关系

原生组件 fiber 原生组件 fiber&#xff0c;指的就是 type 为 “span”、“div” 的 fiber。 1.fiber.stateNode 指向真实 DOM 节点&#xff1b;2.node["__reactFiber$" randomKey] 指向对应 fiber&#xff0c;使用随机数是防止和业务代码的属性名冲突&#xff0c;…...

LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)

文章目录 LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)refnotedemoLaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式) ref markdown中公式编辑教程 在 Microsoft Word 中使用 LaTeX 输入数学公式【比较全,介绍了支持的语法和不支持的语法】 用wo…...

S5P6818_系统篇(2)源码编译及烧录

源码获取 源码获取和操作流程 1.下载liunux下的系统制作脚本&#xff0c;可以烧录系统和构建镜像 git clone https://github.com/friendlyarm/sd-fuse_s5p6818.git 如果出现git错误可使用如下方法&#xff1a; git config --global http.sslverify false 2.阅读该工具rea…...

LDPC码的编译码原理简述

关于fpga调用ldpc IP core的相关参数问题可以看我的另一篇文章 LDPC码由Gallager在1962年提出&#xff0c;全称为 Low Density Parity-check Codes 低密度奇偶校验码 它的译码性能可以逼近Shannon信道容量限&#xff0c;广富盛名的Turbo码也被证明是LDPC码的一个特例。并且LDPC…...

网络安全——数链路层据安全协议

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 目录 前言 一.数据链路层安全协议简介 1.数据链路安全性 二.局域网数据链路层协议 1.…...

spring的启动过程(一) :IOC容器的启动过程

一、web容器的加载 首先我们要先知道一个web项目的启动过程。 将Web项目部署到Tomcat中的方法之一&#xff0c;是部署没有封装到WAR文件中的Web项目。要使用这一方法部署未打包的webapp目录&#xff0c;只要把我们的项目&#xff08;编译好的发布项目&#xff0c;非开发项目&am…...

这次,我的CentOS又ping不通www.baidu.com了(gateway配置)

当我们保证了宿主机与虚拟机的ip地址在同一网段&#xff0c;并且我们使用虚拟机ping宿主机&#xff0c;与宿主机ping虚拟机都可以互相ping通的情况下虚拟机却ping不通外网了&#xff0c;由于涉及到了跨越网络访问&#xff0c;所以我们应该把问题聚焦在网关的配置上&#xff01;…...

启智社区“我为开源狂”第六期活动小白教程之基础活跃榜

一、写在前面 春天来啦~启智社区第六期活动也来啦&#xff01; 有奖金的哦~~ 基础活跃榜奖金根据用户活跃程度进行100-300元的激励。 挑战升级榜需要用户完成相应任务&#xff0c;达标者可获得300-1000元的激励。 邀请助力榜根据用户邀请情况进行积分累加&#xff0c;按实际达…...

华为OD机试 - 区块链文件转储系统(Python)【2023-Q1 新题】

华为OD机试300题大纲 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,通过率才会高。 华为 OD 清单查看地址:blog.csdn.net/hihell/category_12199275.html 华为OD详细说明:https://dream.blog.csdn.net/article/details/128980730 区块链文件转储系…...

【字节面试】Fail-fast知识点相关知识点

字节面试&#xff0c;问到的一个小知识点&#xff0c;这里做一下总结&#xff0c;其实小编之前有一篇文章&#xff0c;已经对此有过涉及&#xff0c;不过这里知识专项针对于问题&#xff0c;把这个知识点拎出来说一下。 1.问题 什么是Fail-fast机制&#xff1f; Hashmap是否拥…...

git应用笔记(三)

在新增虚拟机linux的基础上&#xff0c;做git的下载与提交 1、初始化自己的用户名和邮箱。 git config --global user.name “输入你的用户名” git config --global user.email “输入你的邮箱” 2、将本地公钥及配置如图1复制粘贴到虚拟机当前用户.ssh\目录下 4929a0205f43…...

有序表的应用:设计一个增、删、查数据的时间复杂度均为O(logN)的结构

1、题目描述 设计一个结构包含如下三个方法&#xff1a; void add(int index, int num); //把num加入到index位置 int get(int index); //取出index位置的值&#xff08;是自然序的index位置&#xff0c;非排序后&#xff09; void remove(int index); //把index位置上的值删…...

离线环境拷贝迁移 conda envs 环境(蛮力方法,3行命令)

前言 最近要使用 GPU 服务器做实验&#xff0c;可惜的是&#xff0c;有网络连接的服务器显卡旧&#xff0c;算力不够&#xff1b;显卡较新的机器没有联网。于是有需求将旧机器上配置好的 conda 环境迁移至新机器。网上给的默认方法生成 yaml 文件迁移等 需要联网&#xff0c;只…...

【数据结构与算法】字符串1:反转字符串I 反转字符串II 反转字符串里的单词 剑指offer(替换空格、左旋转字符串)

今日任务 344.反转字符串541.反转字符串II剑指Offer 05.替换空格151.反转字符串里的单词剑指Offer58-II.左旋转字符串 1.Leetcode344.反转字符串 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/reverse-string &#…...

深入浅出C++ ——容器适配器

文章目录一、容器适配器二、deque类简介1. deque的原理2. deque迭代器3. deque的优点和缺陷4. 为什么选择deque作为stack和queue的底层默认容器一、容器适配器 适配器的概念 适配器是STL六大核心组件之一&#xff0c;它是一种设计模式&#xff0c;该种模式是将一个类的接口转换…...

电脑常用知识与工作常用工具

什么是电脑快捷键&#xff1f; 所谓快捷键就是使用键盘上某一个或某几个键的组合完成一条功能命令&#xff0c;从而达到提高操作速度的目的。 键盘布局 主键盘区&#xff0c;数字辅助键盘区、F键功能键盘区、控制键区&#xff0c;对于多功能键盘还增添了快捷键区 一、常用快捷…...

JS的事件循环

文章目录写在前面1.浏览器的进程模型1.1 何为进程1.2 何为线程1.3 浏览器有哪些线程和进程2.渲染主线程是如何工作的任务队列的优先级面试题如何理解JS异步JS中的计时器能做到精确计时吗&#xff1f;为什么&#xff1f;写在前面 此处的文字为自己的理解 1.浏览器的进程模型 1.…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

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

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

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...