当前位置:网站首页>leetcode 36. 有效的数独(模拟题)
leetcode 36. 有效的数独(模拟题)
2022-08-09 08:18:00 【_刘小雨】
作者简介:C/C++ 、Golang 领域耕耘者,创作者
个人主页:作者主页
活动地址:CSDN21天学习挑战赛
题目来源: 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 存在, 因此这个数独是无效的。
🧡 算法分析
此题方法是模拟题
直接模拟就行了
代码实现
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'; // 因为只开了0-8的数组空间,这里映射一下
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[x + i][y + j] != '.')
{
int t= board[i + x][j + y] - '1';
if(st[t]) return false;
st[t] = true;
}
}
return true;
}
};
执行结果:
时间复杂度分析
略
如果觉得对你有帮助的话:
点赞,你的认可是我创作的动力!
🧡 收藏,你的青睐是我努力的方向!
️ 评论,你的意见是我进步的财富!
边栏推荐
- Matlab, and nonlinear equations solving linear equations
- bs4的使用基础学习
- Operations in the database (syntax)
- Three handshakes, four waves
- Introduction to Network Layer Protocols
- A watch - article HongMeng development practical experience
- 引导过程与服务控制
- OpenHarmony轻智能产品开发直播笔记
- 三层交换机原理及配置
- + 6000 words, help you understand the Internet architecture evolution.
猜你喜欢
【redis】使用redis实现简单的分布式锁,秒杀并发场景可用
mysql事务(详解)
3D精彩案例,清软英泰建成综合轻量化显示平台!
The Martian - Simple Math Problems
VMware virtual machine cannot be connected to the Internet after forced shutdown
SOLIDWORKS 2022新功能直播揭秘!速来围观!
NAT地址转换的原理与配置
requests之模拟登录学习
路由配置转发及实验
Notes on OpenHarmony Open Source Meeting (Nanjing Station)
随机推荐
P1064 金明的预算方案
VLAN的原理及配置
动态设置img标签图片失效问题
P1064 Jin Ming's Budget Plan
[MySQL]mysql: Solve the problem of [Err] 1093 - You can't specify target table 'table name' for update in FROM clause
6000 字+,帮你搞懂互联网架构演变历程!
897. 增加订单搜索树
Shell编程之循环语句与函数
浅谈Endpoint
.net(一)WebService创建
EMQ X 消息服务器学习记录——为后面的毕设做准备
网络层协议介绍
Notes on OpenHarmony Open Source Meeting (Nanjing Station)
3D软件开发工具HOOPS全套产品开发介绍 | HOOPS Visualize、HOOPS Publish
pragma comment的使用(转载)重新排版
Three handshakes, four waves
jdbctemplate connects to sql server, the data found in the code is inconsistent with the database, how to solve it?
安全的Md5加密:两次加密(加盐)
磁盘管理与挂载
File Handling (IO)