【LeetCode】36. Valid Sudoku

2019-11-06 08:10:43

字体：大中小

来源：转载

供稿：网友

题目描述

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

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

解题思路

暴力判断行，列，小块是否符合要求即可。

AC代码

class Solution {public: bool isValidBucket(int* bucket) { for (int i = 0; i < 9; ++i) if (bucket[i] > 1) return false; return true; } bool isValidSudoku(vector<vector<char>>& board) { int bucket[9]; //test row for (int i = 0; i < 9; ++i) { fill_n(bucket, 9, 0); for (int j = 0; j < 9; ++j) { if (board[i][j] - '0' > 0 && board[i][j] - '0' <= 9) bucket[board[i][j] - '0' - 1]++; } if (!isValidBucket(bucket)) return false; } // test column for (int j = 0; j < 9; ++j) { fill_n(bucket, 9, 0); for (int i = 0; i < 9; ++i) { if (board[i][j] - '0' > 0 && board[i][j] - '0' <= 9) bucket[board[i][j] - '0' - 1]++; } if (!isValidBucket(bucket)) return false; } // test board for (int row = 0; row < 9; row += 3) { for (int col = 0; col < 9; col += 3) { fill_n(bucket, 9, 0); for (int i = row; i < row + 3; ++i) { for (int j = col; j < col + 3; ++j) { if (board[i][j] - '0' > 0 && board[i][j] - '0' <= 9) bucket[board[i][j] - '0' - 1]++; } } if (!isValidBucket(bucket)) return false; } } return true; }};

上一篇：[Codeforces710D]Two Arithmetic Progressions（扩展中国剩余定理）

下一篇：01背包练习