LeetCode:36. Valid Sudoku,数独是否有效 :
**题目: **
LeetCode:36. Valid Sudoku
**描述: **
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.
**分析: **
- 判断一个数独是否有效的判断条件有三个:行、列、子格里都没有重复的1-9数字
思路如下:
1、遍历所有的数组元素,对其中数据进行如下操作:
2、遇到空格也就是“.”时,判断是有效的,并且在定义数组的对应位置上设置其为1,表示已查到该项;
3、首次遇到某数字时,首先设置其在数组中的位置为1,判定有效;
4、当且仅当遇到重复数字时,判定无效。
所以程序应该分为两部分,一部分编写遍历算法,将元素进行三种方式的比对。另一部分用来编写检验是否有效。
5、细节实现
1)遍历算法:
(1)遍历数组元素board[i][j],判断三个条件:
(2)遍历元素对应逻辑九宫格位置:
anRow[j] = board[i][j],
anCloum[i][j] = board[i][j],
anSonSudoKu[j / 3 * 3 + i / 3][j % 3 * 3 + i % 3] = board[i][j]
2) 检验有效(在逻辑九宫格中标识状态位,1位已查询到):
(1)首次遇到某数字时,首先设置其在数组中的位置为1,判定有效
(2)当且仅当遇到重复数字时,判定无效
(3)首次遇到某数字时,首先设置其在数组中的位置为1,判定有效;
**代码: **
bool checkValid(int anArr[], int nVal)
{
// 2) 检验有效:
//(1)首次遇到某数字时,首先设置其在数组中的位置为1,判定有效
//(2)当且仅当遇到重复数字时,判定无效
// (3) 遇到空格也就是“.”时,判断是有效的,并且在定义数组的对应位置上设置其为1,表示已查到该项;
if (nVal < 0) // 判断(3) “.”情况
{
return true;
}
if (1 == anArr[nVal - 1]) // 判断(2) 重复数字情况
{
return false;
}
//(1) 首次遇到某数字
anArr[nVal - 1] = 1;
return true;
}
bool isValidSudoku(const vector<vector<char>>& board)
{
// 1)遍历数组
int anRow[9] = { 0 }; // 用于存储一行的元素比对结果
int anCloum[9] = { 0 }; // 用于存储一列中的元素比对结果
int anSonSudoKu[9] = { 0 }; // 用于存储子格的元素比对
for (int i = 0; i < 9; i++)
{
memset(anRow, 0, sizeof(anRow));
memset(anCloum, 0, sizeof(anCloum));
memset(anSonSudoKu, 0, sizeof(anSonSudoKu));
for (int j = 0; j < 9; j++)
{
if (!checkValid(anRow, board[i][j] - '0') // 检查第i行(0开始计数)
|| checkValid(anCloum, board[j][i] - '0') // 检查第j行(实际为第j列,0开始)
|| checkValid(anSonSudoKu, board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - '0') // 检查 board[i][j] 元素所在 i / 3 * 3 所在行的3个九宫格的三个元素
)
{
return false;
}
}
}
return true;
}
备注:
好记性不如烂笔头!这道题思考了好几天,才发现人和人差距是很大的~
借鉴了tenos大神的解法LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)
LeetCode:36. Valid Sudoku,数独是否有效的更多相关文章
-
leetcode 37. Sudoku Solver 36. Valid Sudoku 数独问题
三星机试也考了类似的题目,只不过是要针对给出的数独修改其中三个错误数字,总过10个测试用例只过了3个与世界500强无缘了 36. Valid Sudoku Determine if a Sudoku ...
-
leetCode 36.Valid Sudoku(有效的数独) 解题思路和方法
Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku bo ...
-
LeetCode 36 Valid Sudoku
Problem: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board ...
-
蜗牛慢慢爬 LeetCode 36.Valid Sudoku [Difficulty: Medium]
题目 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could ...
-
Java [leetcode 36]Valid Sudoku
题目描述: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board cou ...
-
[LeetCode] 36. Valid Sudoku 验证数独
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to th ...
-
[leetcode]36. Valid Sudoku验证数独
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to th ...
-
LeetCode 36 Valid Sudoku(合法的数独)
题目链接: https://leetcode.com/problems/valid-sudoku/?tab=Description 给出一个二维数组,数组大小为数独的大小,即9*9 其中,未填入 ...
-
LeetCode 36. Valid Sudoku (Medium)
题目 Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according ...
随机推荐
-
XMLPuLL解析
1 package com.bawei.day14_xmlpull; 2 3 import java.io.IOException; 4 import java.io.InputStream; 5 i ...
-
如何 查看 WebLogic Server的版本号[转]
如何 查看 WebLogic Server的版本号[转] WebLogic Server 10gR3为例: 1.查看$BEA_HOME/registry.xml => <c ...
-
bppm与AD域集成
1. 使用admin登录BMC ProactiveNet Operations Console,点击选项-> 集成编辑 2. 勾选LDAP集成方式,配置相关信息,点击应用 3. 查看配置文件%B ...
-
webdriver
导入模块: from selenium import webdriver from selenium.common.exceptions import NoSuchElementException 选 ...
-
Python 第十三节 文件操作
A 1.首先文件读写操作有以下几种模式: a\a+ w\w+ r\r+ a模式:追加_写入模式,写入指针默认在开头,如果文件存在将在开头追加写入,如果文件不存在将创建文件再写入. a+模式: ...
-
sql复杂案例
工作中往往会遇到非常棘手的数据查询,运营人员不知道你的数据库表是如何设计的,也不知道你的数据库记录了啥数据,他只知道自己需要看什么数据,甚至有些数据根本就不存在. 单表查询的难度: 一张数据库的表ta ...
-
final修饰的地址不能被修改
package final0; /* * 顾客 */public class Customer { // 属性 String name; int age; // 父类object的方法 public ...
-
POJ 1061 - 青蛙的约会 - [exgcd求解一元线性同余方程]
先上干货: 定理1: 如果d = gcd(a,b),则必能找到正的或负的整数k和l,使ax + by = d. (参考exgcd:http://www.cnblogs.com/dilthey/p/68 ...
-
SWIFT中数字格式
SWIFT中格式化数字比较常用的应该就是以下几种格式了. var formatter = NSNumberFormatter() //formatter.numberStyle = NSNumberF ...
-
根据二进制和十进制转换规则转换成游戏[xyytit]
摘要: 二進位是由十進位轉換而成,它的數字都由1.0組成的.我們研究發現由十進位轉換而成的二進位的數字可以不只局限在於1~127,它的數可以更加深加廣,並且可以利用二進位的規則轉換成遊戲.我們利用2n ...