【Valid Sudoku】cpp
题目：
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
代码：
class Solution {
public:
bool isValidSudoku(std::vector<std::vector<char> > &board)
{
int len = board.size();
if (len != ) return false;
bool row_check[];
bool col_check[];
bool subBox_check[];
for (int row = ; row < len; ++row)
{
std::fill(row_check, row_check+, false);
std::fill(col_check, col_check+, false);
std::fill(subBox_check, subBox_check+, false);
for (int col = ; col < len; ++col)
{
if (!Solution::if_valid(board, row, col, row_check)){
return false;
}
if (!Solution::if_valid(board, col, row, col_check)){
return false;
}
if (!Solution::if_valid(board, *(row/)+col/, *(row%)+col%, subBox_check)){
return false;
}
}
}
return true;
}
static bool if_valid(std::vector<std::vector<char> > &board, int x, int y, bool (&some_check)[])
{
if (board[x][y]=='.'){
return true;
}
else{
if (some_check[board[x][y]-'']){
return false;
}
else{
some_check[board[x][y]-''] = true;
return true;
}
}
return false;
}
};
Tips：
1. 整体逻辑按照数独的要求走：
a. 判断同一行
b. 判断同一列
c. 判断所在的sub box
2. 判断时主要利用的数据结构是类似HashSet，由于三类判断条件类似，因此单独提出来一段代码。
3. 一点儿技巧：这里时间复杂度没有什么可说的就是O(n²)；可以做些文章的地方就是代码复杂度，如何遍历一次for..for...就判断完成全部的逻辑。
a. 这里的核心就在于数独是对称的矩阵，行列对称；因此，行列坐标互换就可以走一次for...for...就完成1.a和1.b的判断逻辑。
b. 这里还需要注意的是，for..for..中走完一列，则需要判断一个sub box是否valid；因此，需要将某一列的坐标映射到某个sub box上。搞清楚这一点就可以推理处坐标变换的公式。
4. 在离线测试的时候，处理c++的 vector 二维字符数组还是非常不熟练，由Python转成cpp刷题确实不太习惯。后面在刷到string的题目时候，再把这cpp这部分强化一下。
==================================================
第二次过这道题，第一次没有AC还是错在了sub matrix小方块的检验上面。
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
for ( int i=; i<board.size(); ++i )
{
// check row
vector<bool> row_used(,false);
for ( int j=; j<board[i].size(); ++j )
{
if ( board[i][j]!='.' )
{
if ( row_used[board[i][j]-''] ) return false;
row_used[board[i][j]-''] = true;
}
}
// check col
vector<bool> col_used(,false);
for ( int j=; j<board.size(); ++j)
{
if ( board[j][i]!='.')
{
if ( col_used[board[j][i]-''] ) return false;
col_used[board[j][i]-''] = true;
}
}
// check sub matrix
vector<bool> subm_used(,false);
for ( int j=; j<board[i].size(); ++j )
{
int row = *(i/) + j/;
int col = *(i%) + j%;
if ( board[row][col]!='.' )
{
if ( subm_used[board[row][col]-''] ) return false;
subm_used[board[row][col]-''] = true;
}
}
}
return true;
}
};
tips：
这个要记住了
row = 3*(i/3) + j/3
col = 3*(i%3) + j%3
最新文章
- Handler(二)
- Mysql查询按照某字段指定顺序排序
- Google java代码风格导入Eclipse
- 走进Vue.js
- Android实例-MediaPlayer播放音乐和视频(XE8+小米2)
- javascript book
- linux下编译eXosip、osip，以及UAC和UAS的例子
- Spring整合Hibernate--声明式事务管理
- Jenkins插件开发
- 关于 AspNet Core 的配置文件 与VS2017 安装
- FortiGate上架前准备
- 自动化运维之Cobbler自动化部署安装操作系统
- Ubuntu16.04下写的Qt程序，调试时没问题，运行时偶现崩溃 （需要在运行时生成core dump文件，QMAKE_CC += -g）
- android AlertDialog.Builder(Context context)换行
- winform打包发布安装包详解..
- iPhone开发秘籍(第2版)--具体书签版
- [转]SSIS数据转换组件_派生列、审核、字符映射转换和条件性拆分转换
- Mysql性能优化四：分库，分区，分表，你们如何做？
- ajax的适用场景
- AngularJS中的http服务的简单用法