LeetCode:36. Valid Sudoku,数独是否有效

时间:2022-09-16 15:52:55

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 '.'.

LeetCode:36. Valid Sudoku,数独是否有效

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,数独是否有效的更多相关文章

  1. leetcode 37&period; Sudoku Solver 36&period; Valid Sudoku 数独问题

    三星机试也考了类似的题目,只不过是要针对给出的数独修改其中三个错误数字,总过10个测试用例只过了3个与世界500强无缘了 36. Valid Sudoku Determine if a Sudoku ...

  2. leetCode 36&period;Valid Sudoku&lpar;有效的数独&rpar; 解题思路和方法

    Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku bo ...

  3. LeetCode 36 Valid Sudoku

    Problem: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board ...

  4. 蜗牛慢慢爬 LeetCode 36&period;Valid Sudoku &lbrack;Difficulty&colon; Medium&rsqb;

    题目 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could ...

  5. Java &lbrack;leetcode 36&rsqb;Valid Sudoku

    题目描述: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board cou ...

  6. &lbrack;LeetCode&rsqb; 36&period; Valid Sudoku 验证数独

    Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to th ...

  7. &lbrack;leetcode&rsqb;36&period; Valid Sudoku验证数独

    Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to th ...

  8. LeetCode 36 Valid Sudoku(合法的数独)

    题目链接: https://leetcode.com/problems/valid-sudoku/?tab=Description   给出一个二维数组,数组大小为数独的大小,即9*9  其中,未填入 ...

  9. LeetCode 36&period; Valid Sudoku &lpar;Medium&rpar;

    题目 Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according ...

随机推荐

  1. XMLPuLL解析

    1 package com.bawei.day14_xmlpull; 2 3 import java.io.IOException; 4 import java.io.InputStream; 5 i ...

  2. 如何 查看 WebLogic Server的版本号&lbrack;转&rsqb;

    如何 查看 WebLogic Server的版本号[转] WebLogic Server 10gR3为例: 1.查看$BEA_HOME/registry.xml         => <c ...

  3. bppm与AD域集成

    1. 使用admin登录BMC ProactiveNet Operations Console,点击选项-> 集成编辑 2. 勾选LDAP集成方式,配置相关信息,点击应用 3. 查看配置文件%B ...

  4. webdriver

    导入模块: from selenium import webdriver from selenium.common.exceptions import NoSuchElementException 选 ...

  5. Python 第十三节 文件操作

    A 1.首先文件读写操作有以下几种模式:   a\a+  w\w+ r\r+   a模式:追加_写入模式,写入指针默认在开头,如果文件存在将在开头追加写入,如果文件不存在将创建文件再写入. a+模式: ...

  6. sql复杂案例

    工作中往往会遇到非常棘手的数据查询,运营人员不知道你的数据库表是如何设计的,也不知道你的数据库记录了啥数据,他只知道自己需要看什么数据,甚至有些数据根本就不存在. 单表查询的难度: 一张数据库的表ta ...

  7. final修饰的地址不能被修改

    package final0; /* * 顾客 */public class Customer { // 属性 String name; int age; // 父类object的方法 public ...

  8. POJ 1061 - 青蛙的约会 - &lbrack;exgcd求解一元线性同余方程&rsqb;

    先上干货: 定理1: 如果d = gcd(a,b),则必能找到正的或负的整数k和l,使ax + by = d. (参考exgcd:http://www.cnblogs.com/dilthey/p/68 ...

  9. SWIFT中数字格式

    SWIFT中格式化数字比较常用的应该就是以下几种格式了. var formatter = NSNumberFormatter() //formatter.numberStyle = NSNumberF ...

  10. 根据二进制和十进制转换规则转换成游戏&lbrack;xyytit&rsqb;

    摘要: 二進位是由十進位轉換而成,它的數字都由1.0組成的.我們研究發現由十進位轉換而成的二進位的數字可以不只局限在於1~127,它的數可以更加深加廣,並且可以利用二進位的規則轉換成遊戲.我們利用2n ...