问题描述:
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.
原问题链接:https://leetcode.com/problems/valid-sudoku/
问题分析
对于数独问题来说,我们首先要熟悉它本身的规则。它是一个9 x 9的矩阵。作为一个合法的数独表示,它要求里面每一行,每一列都取值自1到9,但是这些数字只能出现1次,而且不能有重复。同时,如果将这个矩阵9等分的话,则有9个3 x 3的小矩阵。对于这些小的矩阵来说,它们里面的每个数字也只能出现一次不能重复。
所以要解决这个问题一个最直观的办法就是判断它的每一行,每一列以及每个小矩阵是否都符合要求。按照这个思路,我们每次判断每一行是否合法的时候,只需要用一个set,将碰到的元素和set进行对比。如果该元素非法,则返回false。如果该元素是'.',不用继续比较,继续下一步,如果集合里有这个元素,那么说明该矩阵非法,返回false。
这里稍微困难一点的地方就是怎么来判断里面的9个小矩阵呢?假设从最左上角的那个矩阵开始,也就是这个时候最起始点的索引位置是i = 0, j = 0。按照我们每一行一行从上到下遍历的顺序,它的访问方式如下图:
这里每一条横线可以表示i的值。按照这个顺序,它们的索引位置变化按照如下的顺序(0, 0) -> (0, 1) -> (0, 2) -> (1, 0) -> (1, 1) -> (1, 2)。对于这个矩阵来说,它总共有9个元素。如果我们换一种方式来考虑。假设给定了初始的点i, j,不用i, j构成的双重循环,有没有别的办法来遍历整个矩阵呢?针对这种情况,我们可以用一个变量k来循环。从0到9。对于里面对应的每个位置的关系可以定义如下: i = i + k / 3; j = j + k % 3;
所以在给定初始i, j的情况下会有这么一个表达方式:
for(int k = 0; k < 9; k++) board[i + k / 3][j + k % 3] = xxx;
它和我们使用如下的方式来遍历是等价的:
for(int l = i; l < i + 3; l++) { for(int r = j; r < j + 3; r++) board[l][r] = xxx; }
上述的表达式能够简化部分代码。剩下的部分就是该怎么把这个部分和所有i, j的位置给串起来。对于里面的9个小矩阵,我们现在只需要找到它们每个矩阵最开始的位置。很直观,它们的位置如下:(0, 0) (0, 3), (0, 6) (3, 0), (3, 3) (3, 6) (6, 0), (6, 3) (6, 6)。我们可以很直接的用两个循环就解决了:
for(int i = 0; i < 9; i += 3) { for(int j = 0; j < 9; j += 3) { // xxxx } }
最终可以得到如下的代码:
public class Solution { public boolean isValidSudoku(char[][] board) { if(board == null || board.length != 9 || board[0].length != 9) return false; int n = board.length; for(int i = 0; i < n; i++) { Set<Character> set = new HashSet<>(); for(int j = 0; j < n; j++) { if(!isValid(set, board, i, j)) return false; } } for(int j = 0; j < n; j++) { Set<Character> set = new HashSet<>(); for(int i = 0; i < n; i++) { if(!isValid(set, board, i, j)) return false; } } for(int i = 0; i < n; i += 3) { for(int j = 0; j < n; j += 3) { Set<Character> set = new HashSet<>(); for(int k = 0; k < n; k++) if(!isValid(set, board, i + k / 3, j + k % 3)) return false; } } return true; } private boolean isValid(Set<Character> set, char[][] board, int i, int j) { if(board[i][j] == '.') return true; if(board[i][j] < '1' || board[i][j] > '9') return false; if(set.contains(board[i][j])) return false; set.add(board[i][j]); return true; } }
上述代码的时间复杂度为O(N ^ 2)。
总结
这个问题的思路并不复杂,重要的是要能找到一个对问题解决方法的一个简洁的表达方式。
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
java lru leetcode :ice_cream: LeetCode ...Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode 持续刷leetcode中... 欢迎大家交流,也欢迎star. 关于leetcode网站上的题目解法,语言选择的Java。后续会进行题目翻译和解法分析。 题目分析: Easy Leetcode 760 : Find Anagram ...Leetcode 794: Valid
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...