算法leetcode|36. 有效的数独rust重拳出击
36. 有效的数独:
请你判断一个 9 x 9
的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9
在每一行只能出现一次。
数字 1-9
在每一列只能出现一次。
数字 1-9
在每一个以粗实线分隔的 3x3
宫内只能出现一次。(请参考示例图)
注意:
- 一个有效的数独(部分已被填充)不一定是可解的。
- 只需要根据以上规则,验证已经填入的数字是否有效即可。
- 空白格用
'.'
表示。
样例 1:
输入:
board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出:
true
样例 2:
输入:
board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出:
false
解释:
除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示:
- board.length == 9
- board[i].length == 9
- board[i][j] 是一位数字(1-9)或者 ‘.’
分析:
- 面对这道算法题目,二当家的陷入了沉思。
- 主要是如何存储行,列,以及 3*3 宫内出现过的值。
- 方法很多,集合,整形数组,布尔数组都可以,只有1-9,一共9个数,最优化的空间方式应该是仅仅用一个整形,然后用位运算,这样做空间占用是很少的,但是存储和读取都需要运算,速度略有损失。
- 接下来只需要逐行,逐列遍历,一边判断行,列,和 3 * 3 宫出现过的值,如果出现重复值就是无效的。
题解:
rust
impl Solution {
pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
let mut rows = vec![vec![false; 9]; 9];
let mut columns = vec![vec![false; 9]; 9];
let mut sub_boxes = vec![vec![vec![false; 9]; 3]; 3];
for i in 0..9 {
for j in 0..9 {
let c = board[i][j];
if c != '.' {
let index = (c as u8 - b'1') as usize;
if rows[i][index] || columns[j][index] || sub_boxes[i / 3][j / 3][index] {
return false;
}
rows[i][index] = true;
columns[j][index] = true;
sub_boxes[i / 3][j / 3][index] = true;
}
}
}
return true;
}
}
go
func isValidSudoku(board [][]byte) bool {
var rows, columns [9][9]bool
var subBoxes [3][3][9]bool
for i, row := range board {
for j, c := range row {
if c != '.' {
index := c - '1'
if rows[i][index] || columns[j][index] || subBoxes[i/3][j/3][index] {
return false
}
rows[i][index] = true
columns[j][index] = true
subBoxes[i/3][j/3][index] = true
}
}
}
return true
}
c
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool rows[9][9];
bool columns[9][9];
bool subBoxes[3][3][9];
memset(rows, 0, sizeof(rows));
memset(columns, 0, sizeof(columns));
memset(subBoxes, 0, sizeof(subBoxes));
for (int i = 0; i < 9; i ) {
for (int j = 0; j < 9; j ) {
char c = board[i][j];
if (c != '.') {
int index = c - '1';
if (rows[i][index] || columns[j][index] || subBoxes[i / 3][j / 3][index]) {
return false;
}
rows[i][index] = true;
columns[j][index] = true;
subBoxes[i / 3][j / 3][index] = true;
}
}
}
return true;
}
};
c
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
bool rows[9][9];
bool columns[9][9];
bool subBoxes[3][3][9];
memset(rows, 0, sizeof(rows));
memset(columns, 0, sizeof(columns));
memset(subBoxes, 0, sizeof(subBoxes));
for (int i = 0; i < 9; i ) {
for (int j = 0; j < 9; j ) {
char c = board[i][j];
if (c != '.') {
int index = c - '1';
if (rows[i][index] || columns[j][index] || subBoxes[i / 3][j / 3][index]) {
return false;
}
rows[i][index] = true;
columns[j][index] = true;
subBoxes[i / 3][j / 3][index] = true;
}
}
}
return true;
}
python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows, columns, sub_boxes = [[False] * 9 for _ in range(9)], [[False] * 9 for _ in range(9)], [
[[False] * 9 for _ in range(3)] for _ in range(3)]
for i in range(9):
for j in range(9):
c = board[i][j]
if c != '.':
index = ord(c) - ord('1')
if rows[i][index] or columns[j][index] or sub_boxes[i // 3][j // 3][index]:
return False
rows[i][index] = True
columns[j][index] = True
sub_boxes[i // 3][j // 3][index] = True
return True
java
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9];
boolean[][] columns = new boolean[9][9];
boolean[][][] subBoxes = new boolean[3][3][9];
for (int i = 0; i < 9; i ) {
for (int j = 0; j < 9; j ) {
char c = board[i][j];
if (c != '.') {
int index = c - '1';
if (rows[i][index] || columns[j][index] || subBoxes[i / 3][j / 3][index]) {
return false;
}
rows[i][index] = true;
columns[j][index] = true;
subBoxes[i / 3][j / 3][index] = true;
}
}
}
return true;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgcicha
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01