本文主要是介绍[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）每一行都必须在1-9的范围内，且只出现一次。
（2）每一列都必须在1-9的范围内，且只出现一次。
（3）数字1-9在每个子宫格中只出现一次。
数独宫格可以部分填充，其中空单元格都充满了字符'.'。
例如：
部分填充的有效数独
【分析】
细节分析题
（1）检查行
（2）检查列
（3）检查9个子宫格
【代码】
/*********************************
* 日期：2014-01-20
* 作者：SJF0115
* 题号: Valid Sudoku
* 来源：http://oj.leetcode.com/problems/valid-sudoku/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;class Solution {
public:bool isValidSudoku(vector<vector<char> > &board) {int i,j,k;//判断1-9是否已用bool used[9];for(i = 0;i < 9;i++){//检查行memset(used,false,9);for(j = 0;j < 9;j++){//不符合规则if(!check(board[i][j],used)){return false;}//if}//for//检查列memset(used,false,9);for(j = 0;j < 9;j++){//不符合规则if(!check(board[j][i],used)){return false;}//if}//for}//for//检查9个子宫格for(k = 0;k < 3;k++){memset(used,false,9);for(i = k*3;i < 3*k + 3;i++){for(j = 0;j < 3;j++){//不符合规则if(!check(board[i][j],used)){return false;}//if}//for}//formemset(used,false,9);for(i = k*3;i < 3*k + 3;i++){for(j = 3;j < 6;j++){//不符合规则if(!check(board[i][j],used)){return false;}//if}//for}//formemset(used,false,9);for(i = k*3;i < 3*k + 3;i++){for(j = 6;j < 9;j++){//不符合规则if(!check(board[i][j],used)){return false;}//if}//for}//for}//forreturn true;}
private:bool check(char c,bool used[9]){if(c == '.'){return true;}//字符c 已用if(used[c - '1']){return false;}//字符c 未用else{used[c - '1'] = true;return true;}}
};
int main() {Solution solution;bool result;vector<vector<char>> board;char value[9] = {'5','3','.','.','7','.','.','.','.'};vector<char> subBoard(value,value + 9);board.push_back(subBoard);value = {'6','.','.','1','9','5','.','.','.'};vector<char> subBoard1(value,value + 9);board.push_back(subBoard1);value = {'.','9','8','.','.','.','.','6','.'};vector<char> subBoard2(value,value + 9);board.push_back(subBoard2);value = {'8','.','.','.','6','.','.','.','3'};vector<char> subBoard3(value,value + 9);board.push_back(subBoard3);value = {'4','.','.','8','.','3','.','.','1'};vector<char> subBoard4(value,value + 9);board.push_back(subBoard4);value = {'7','.','.','.','2','.','.','.','6'};vector<char> subBoard5(value,value + 9);board.push_back(subBoard5);value = {'.','6','.','.','.','.','2','8','.'};vector<char> subBoard6(value,value + 9);board.push_back(subBoard6);value = {'.','.','.','4','1','9','.','.','5'};vector<char> subBoard7(value,value + 9);board.push_back(subBoard7);value = {'.','.','.','.','8','.','.','7','9'};vector<char> subBoard8(value,value + 9);board.push_back(subBoard8);result = solution.isValidSudoku(board);cout<<result<<endl;return 0;
}【代码2】
class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {bool used[9];for (int i = 0; i < 9; ++i) {fill(used, used + 9, false);// 检查行for (int j = 0; j < 9; ++j){if (!check(board[i][j], used)){return false;}//if}//forfill(used, used + 9, false);// 检查列for (int j = 0; j < 9; ++j) {if (!check(board[j][i], used)){return false;}//if}//for}//for// 检查 9 个子格子for (int r = 0; r < 3; ++r) {for (int c = 0; c < 3; ++c) {fill(used, used + 9, false);for (int i = r * 3; i < r * 3 + 3; ++i){for (int j = c * 3; j < c * 3 + 3; ++j){if (!check(board[i][j], used)){return false;}}//for}//for}//for}//forreturn true;}bool check(char ch, bool used[9]) {if (ch == '.') return true;if (used[ch - '1']) return false;used[ch - '1'] = true;return true;}
};这篇关于[LeetCode]36.Valid Sudoku的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
