Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Valid Sudoku

Leetcode algorithms 第 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.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

解答

检验一个数独是否合法。直接检查每一行、每一列、每个九宫格上的数字是否有重复即可。第i行的元素为a[i][*],第i列的元素为a[*][i],第i个九宫格的元素为a[i/3*3+*][i%3*3+*],具体见代码如下:

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        for (int i = 0; i < 9; i++)
        {
            set<char> s; //检查每列
            for (int j = 0; j < 9; j++)
                if(board[i][j] == '.')
                    continue;
                else if(s.find(board[i][j]) != s.end())
                    return false;
                else 
                    s.insert(board[i][j]);
            
            s.clear(); //检查每行
            for (int j = 0; j < 9; j++)
                if(board[j][i] == '.')
                    continue;
                else if(s.find(board[j][i]) != s.end())
                    return false;
                else 
                    s.insert(board[j][i]);
            
            s.clear(); //检查每个小九宫格
            int x = i/3*3, y = i%3*3;
            for (int j = x; j < x+3; j++)
                for (int k = y; k < y+3; k++)
                    if(board[j][k] == '.')
                        continue;   
                    else if(s.find(board[j][k]) != s.end())
                        return false;
                    else 
                        s.insert(board[j][k]);
        }
        return true;
    }
};

另外,以上代码写得较为繁琐,以下为简化版本,具体思路一样,只是用数组来存储每行、每列、每个九宫格的状态。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        bool row[10][10]={0}, col[10][10]={0}, mid[10][10]={0}; //行、列、九宫格
        for (int i = 0; i < 9; i++) //遍历每个元素,看其所属的行、列、九宫格是否合法
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.') continue;
                int x = board[i][j] - '1';
                if (row[i][x] || col[j][x] || mid[i/3*3+j/3][x]) return false;
                row[i][x] = col[j][x] = mid[i/3*3+j/3][x] = true;
            }
            return true;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论