每日一题:有效的数独

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

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

位运算

由于数独是9x9的方格,这里总共需要判断9行、9列、9个3x3方格中的数是否有重复。

创建三个位掩码数组:rowcolblock,每个数组有 9 个元素,用于跟踪每个行、列和块中出现的数字。

以例子中第一行为例,初始状态row[0] = 0,二进制表示为0b0000000000。

当遍历board[i,j]时,需要对row[i],col[j],block[i/3*3 + j/3]进行更新。

注意这里的block[i/3*3 + j/3],为什么是下标是i/3*3 + j/3

首先注意这里的除法都是整除向下取整,因此下标0,1,2经过除法后为0,下标3,4,5经过除法后为1,按照上图对3x3网格进行分块:

  • [012,012] -> 块0
  • [012,345] -> 块1
  • [012,678] -> 块2
  • [345,012] -> 块3
  • ......

回到例子中,第一步遍历board[0][0] = 5,那么代码执行row[0] = 0b0000000000 | (1 << 5),即0b0000010000。

对81个方格重复这个位运算的过程。

在这个遍历的过程中进行判断,如果计算之前这位就是1了,说明在这一行/列/块中已经出现过对应数字,直接返回无效。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] row = new int[9];
        int[] col = new int[9];
        int[] block = new int[9];
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                int num = board[i][j] - '0';
                int block_num = i / 3 * 3 + j / 3;
                if(((row[i] >> num) & 1) == 1 || ((col[j] >> num) & 1) == 1|| ((block[block_num] >> num) & 1) == 1){
                    return false;
                }
                row[i] = row[i] | (1 << num);
                col[j] = col[j] | (1 << num);
                block[block_num] = block[block_num] | (1 << num);
            }
        }
        return true;
    }
}

 算法概述:

  1. 创建三个位掩码数组:rowcolblock,每个数组有 9 个元素,用于跟踪每个行、列和块中出现的数字。
  2. 遍历棋盘,对于每个非空单元格:
    • 计算单元格所在的块号 block_num
    • 如果数字在当前行、列或块中已经出现(即位掩码数组中相应位为 1),则返回 false。
    • 否则,将数字标记为在当前行、列和块中出现,即在相应位掩码数组中设置相应位为 1。
  3. 如果遍历完棋盘,返回 true。

除去位运算方式,还可以通过二维数组,哈希表对遍历结果进行存储,本质上都是遍历一次网格,记录是否出现重复元素,只有存储方式上的差别。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

教你构建一个优秀的SD Prompt

构建一个优秀的Prompt 在使用Stable Diffusion AI时,构建一个有效的提示(Prompt)是至关重要的第一步。这个过程涉及到创造性的尝试和对AI行为的理解。这里我会对如何构建一个好的Prompt进行一个总结。 什么是一个好的提示词 构建有效的提示是使用Stable Diffusion AI或其…

职场商务英语口语柯桥外语培训之“手机欠费”用英文怎么说?

大家天天玩手机&#xff0c; 肯定会碰到 “欠费”“没电”“关机” 这些情况&#xff0c; 那么问题来了&#xff0c; 你知道用英语怎么说&#xff1f; 一起来和小编来学习下吧 今天&#xff0c;一起来学习一下吧。 ● 手机欠费 英语怎么说&#xff1f; ● 肯定有同学要…

二手车商的套路

https://www.dongchedi.com/article/7126394624675578405 https://www.dongchedi.com/article/7126394624675578405 现在&#xff0c;有越来越多的人去了解二手车&#xff0c;二手车相对于新车来说&#xff0c;更加的亲民划算。很多新车需要四五十万&#xff0c;而二手车有可…

信息素养与终身学习解锁题目搜索之道的新引擎【文末送书】

文章目录 信息素养&#xff1a;搜索前的准备终身学习&#xff1a;搜索后的深化新引擎的构建与运行 搜索之道&#xff1a;信息素养与终身学习的新引擎【文末送书】 随着互联网的快速发展和信息技术的日益成熟&#xff0c;搜索已经成为获取知识和信息的主要途径之一。然而&#x…

浙大恩特客户资源管理系统 RegulatePriceAction SQL注入漏洞复现

0x01 产品简介 浙大恩特客户资源管理系统是一款针对企业客户资源管理的软件产品。该系统旨在帮助企业高效地管理和利用客户资源,提升销售和市场营销的效果。 0x02 漏洞概述 浙大恩特客户资源管理系统 RegulatePriceAction接口存在 SQL 注入漏洞,攻击者可通过输入恶意 SQL …

47 转置卷积【李沐动手学深度学习v2课程笔记】

1. 转置卷积 卷积层和汇聚层通常会减少下采样输入图像的空间维度&#xff08;高和宽&#xff09;&#xff0c;卷积通常来说不会增大输入的高和宽&#xff0c;要么保持高和宽不变&#xff0c;要么会将高宽减半&#xff0c;很少会有卷积将高宽变大的。可以通过 padding 来增加高…

layui复选框勾选取消勾选事件监听

监听事件放置位置&#xff1a; form.on(checkbox(equipInputClick), function(data){var a data.elem.checked;var val data.value;if(a true){}else{}});html部分 <input lay-filter"equipInputClick" type"checkbox" lay-skin"primary&quo…

Leetcode 23.合并K个升序链表

心路历程&#xff1a; 第一反应是直接暴力求解出来&#xff0c;因为题中也没有关于复杂度的要求。写完发现竟然也通过了&#xff0c;后来发现这道题本来考察的是分治算法&#xff0c;不过能解决问题就行吧。 从评论区看到了一句话很有意思&#xff1a;链表的题能暴力做出来的…

Vue 移动端(H5)项目怎么实现页面缓存(即列表页面进入详情返回后列表页面缓存且还原页面滚动条位置)keep-alive简单使用

一、需求 产品要求&#xff1a;Vue移动端项目进入列表页&#xff0c;列表页需要刷新&#xff0c;而从详情页返回列表页&#xff0c;列表页则需要缓存并且还原页面滚动条位置 二、实现思路 1、使用Vue中的keep-alive组件&#xff0c;keep-alive提供了路由缓存功能 2、因为我项…

优先级队列

优先级队列的基本使用 模拟实现上面的接口函数&#xff0c;优先级队列不是队列&#xff0c;而是类似一个堆一样的东西&#xff0c;我们先来试试它的接口函数是怎么个样子的。 需要包含的头文件是queue。 #include<iostream> #include<queue> using namespace std;…

2024/4/5—力扣—字符串相乘

代码实现&#xff1a; 方法一&#xff1a;常规解法——超出整数表示范围 long long char_to_num(char *str) {long long num 0;for (int i 0; i < strlen(str); i) {num num * 10 (str[i] - 0);}return num; }char* multiply(char *num1, char *num2) {long long a cha…

拥抱智能,IT运维将有哪些变化?

Gartner数据显示&#xff0c;2023年AIOps在中国市场渗透率只达到目标受众的5%-20%。这一数据意味着仍有大量企业还未进行AIOps建设&#xff0c;未来AIOps市场前景广阔。目前&#xff0c;已经开始应用AIOps的企业&#xff0c;智能运维水平普遍还处于辅助智能化运维阶段&#xff…

linux-docker安装nginx

1.拉取镜像&#xff1a; docker pull nginx2.创建挂在路径&#xff1a; mkdir -p /usr/local/nginx/conf mkdir -p /usr/local/nginx/logs mkdir -p /usr/local/nginx/www mkdir -p /usr/local/nginx/conf.d 3.启动镜像:为了拿到位置文件&#xff0c;先启动下 docker run -…

Linux_应用篇(03) 文件 I/O 加强

经过上一章内容的学习&#xff0c;相信各位读者对 Linux 系统应用编程中的基础文件 I/O 操作有了一定的认识和理解了&#xff0c;能够独立完成一些简单地文件 I/O 编程问题&#xff0c; 如果你的工作中仅仅只是涉及到一些简单文件读写操作相关的问题&#xff0c;其实上一章的知…

spring框架构成

spring框架构成 模块 spring中集成了多个模块&#xff0c;包含有核心容器、数据访问、web、AOP等模块 核心容器包含有Spring Core、Spring Beans、Spring Context和EL模块 Spring Core spring的核心&#xff0c;提供Spring框架的基本功能。主要组件是BeanFactory&#xff0c;工…

实战攻防 | 记一次项目上的任意文件下载

1、开局 开局一个弱口令&#xff0c;正常来讲我们一般是弱口令或者sql&#xff0c;或者未授权 那么这次运气比较好&#xff0c;直接弱口令进去了 直接访问看看有没有功能点&#xff0c;正常做测试我们一定要先找功能点 发现一个文件上传点&#xff0c;不过老规矩&#xff0c;还…

实用运维工具(转载)

1、查看进程占用带宽情况-Nethogs Nethogs 是一个终端下的网络流量监控工具可以直观的显示每个进程占用的带宽。 下载&#xff1a;http://sourceforge.net/projects/nethogs/files/nethogs/0.8/nethogs-0.8.0.tar.gz/download [rootlocalhost ~]#yum -y install libpcap-deve…

Jenkins 命令无法后台运行,使用BUILD_ID=dontKillMe解决

例子&#xff1a; jenkins如果在shell里使用nohup发现还是不能后台运行&#xff0c;直接挂掉。 那么可以在jenkins命令里加上BUILD_IDdontKillMe解决 nohup python main.py >server.out 2>&1 &它的作用是在后台运行名为main.py的Python脚本&#xff0c;并将标准…

使用自己的数据基于SWIFT微调Qwen-Audio-Chat模型

目录 使用自己的数据训练参数设置自己的数据准备语音转写任务语音分类任务 开始训练不同训练方法mpddpmp ddpdeepspeed 训练实例训练详情Qwen-Audio-Chat模型 模型数据实例官方可用的数据由内部函数处理为指定格式 训练好的模型测试 使用自己的数据 官方参考文档&#xff1a;…

昇腾Ascend之npu-smi工具在Atlas 200I DK A2的简单使用

一、参考资料 npu-smi工具 二、测试环境 设备型号&#xff1a;Atlas 200 DK(Model: 3000) Operating System Version: Ubuntu 22.04 LTS CPU Type: 4核TAISHANV200M处理器 AI CPU number: 1 control CPU number: 3 RAM: 4GB miscroSD: 128GBrootdavinci-mini:~# npu-smi i…