LeetCode - 36. Valid Sudoku

简介: 36. Valid Sudoku  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个数独,判断这个数独是否合法.

36. Valid Sudoku 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定一个数独,判断这个数独是否合法.

analyse:

略.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-03-02-18.28
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

class Solution
{
public :
    bool isValidSudoku( vector < vector < char >>& board)
    {
        int row = board . size();
        int col = board [ 0 ]. size();
        set < int > se;
        // -------
        for( int i = 0; i < row; ++ i)
        {
            se . clear();
            for( int j = 0; j < col; ++ j)
                if( board [ i ][ j ] != '.')
                {
                    int k = board [ i ][ j ] - '0';
                    if( se . count( k))
                        return false;
                    se . insert( k);
                }
        }
        // -------
        for( int i = 0; i < col; ++ i)
        {
            se . clear();
            for( int j = 0; j < row; ++ j)
                if( board [ j ][ i ] != '.')
                {
                    int k = board [ j ][ i ] - '0';
                    if( se . count( k))
                        return false;
                    se . insert( k);
                }
        }
        //*****
        for( int i = 0; i < row - 2; i += 3)
        {
            for( int j = 0; j < col - 2; j += 3)
                if( ! checkBoard( board , i , j))
                    return false;
        }
        return true;
    }

    bool checkBoard( vector < vector < char >>& board , int bi , int bj)
    {
        set < int > se;
        for( int i = bi; i < bi + 3; ++ i)
        {
            for( int j = bj; j < bj + 3; ++ j)
            {
                if( board [ i ][ j ] != '.')
                {
                    int k = board [ i ][ j ] - '0';
                    if( se . count( k))
                        return false;
                    se . insert( k);
                }
            }
        }
        return true;
    }
};

int main()
{
    freopen( "H: \\ Code_Fantasy \\ in.txt" , "r" , stdin);
    vector < vector < char >> ve;
    string s;
    while( cin >>s)
    {
        vector < char > tempVe;
        for( int i = 0;s [ i ]; ++ i)
        {
            tempVe . push_back(s [ i ]);
        }
        ve . push_back( tempVe);
    }
    Solution solution;
    bool ans = solution . isValidSudoku( ve);
    puts( ans ? "true" : "false");
    return 0;
}
/*

*/
目录
相关文章
|
8月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode 367. Valid Perfect Square
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
109 0
LeetCode 367. Valid Perfect Square
LeetCode 242. Valid Anagram
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
100 0
LeetCode 242. Valid Anagram
|
canal
LeetCode 125. Valid Palindrome
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
101 0
LeetCode 125. Valid Palindrome
|
算法
LeetCode 65. Valid Number
验证给定字符串是否可以解释为十进制数。
104 0
LeetCode 65. Valid Number
Leetcode-Easy 20. Valid Parentheses
Leetcode-Easy 20. Valid Parentheses
115 0
Leetcode-Easy 20. Valid Parentheses
LeetCode 20:有效的括号 Valid Parentheses
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 有效字符串需满足: 左括号必须用相同类型的右括号闭合。
770 0
|
Java
[LeetCode] Valid Parentheses 验证括号是否有效闭合
链接:https://leetcode.com/problems/valid-parentheses/#/description难度:Easy题目:20.
1020 0
|
人工智能 Java
LeetCode 36 Valid Sudoku(有效数独)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50118647 翻译 数独板被部分填充,空格部分用'.'来填充。
956 0