Leetcode36--->Valid Sudoku(判断给定的数独是否有效)
2024-10-21 14:29:24
题目:给定一个数独,某些部分已经被填上了数字,其余空的地方用‘.’表示;判断给定的数独是否有效;
数独规则: 每一行不能有重复的数字;每一列不能有重复的数字;将数独框划分为三行三列,没9个小方格不能有重复;
解题思路:
该题目不要判断整个数独是否有解,只需要判断当前给出的数独是否有效。因此只需要判断行和列是否有效,判断每个块是否有效。而判断一行中是否有重复的数字,最好的数据结构莫过于Set结构了。
使用rowSet,colSet两个Set结构来分别保存当前遍历的行和列,(i, j)表示行,则(j, i)就表示列。因此可以在判断第一行是否有效的同时,顺便判断第一列是否有效;块单独做检查;
代码如下:
public class Solution {
public boolean isValidSudoku(char[][] board) {
if(board == null || board.length < 9 || board[0].length < 9)
return false;
Set<Character> rowset = new HashSet<Character>();
Set<Character> colset = new HashSet<Character>(); for(int i = 0; i < 9; i++)
{
rowset.clear();
colset.clear();
for(int j = 0; j < 9; j ++)
{
if(i % 3 == 0 && j % 3 == 0) // 检查块是否有效
{
if(!checkBlock(board, i, j))
return false;
}
if(board[i][j] != '.') // 检查行是否有效
{
if(rowset.contains(board[i][j]))
return false;
rowset.add(board[i][j]);
}
if(board[j][i] != '.') // 检查列是否有效
{
if(colset.contains(board[j][i]))
return false;
colset.add(board[j][i]);
}
}
}
return true; }
public boolean checkBlock(char[][] board, int row, int col) // 检查块是否有效
{
Set<Character> blockSet = new HashSet<Character>();
for(int i = row; i < row + 3; i++)
{
for(int j = col; j < col + 3; j++)
{
if(board[i][j] != '.')
{
if(blockSet.contains(board[i][j]))
return false;
blockSet.add(board[i][j]);
}
}
}
return true;
}
}
最新文章
- spi 10方式编写
- OpenStack部署工具总结
- python迭代器,生成器,装饰器,context模块
- c++代码美化
- SSH+Oracle10G抛Disabling contextual LOB creation as createClob() m
- LightOj1137 - Expanding Rods(二分+数学)
- Windows 上如何安装Sqlite(转载)
- 实现输出h264直播流的rtmp服务器 flash直播服务器【转】
- [HeadFirst-JSPServlet学习笔记][第一章:前言与概述]
- MySQL学习笔记(4) - 创建数据库
- linux ftp安装和配置
- lucene原理及源码解析--核心类
- mui开发app之html5+,5+Runtime,5+sdk,native.js
- 【干货】基于Owin WebApi 使用OAuth2进行客户端授权服务
- python re模块与正则表达式
- html网页练习豆瓣网
- javascript模块化编程-详解立即执行函数表达式IIFE
- Python基础【day03】:文件操作(七)
- Unity5中新的Shader体系简析
- UVALive 5059 C - Playing With Stones 博弈论Sg函数