自己解法
这个题，思路就是遍历一遍，分别判断每行，每列每个小九宫格是否包含重复数据，因为是逐行遍历，遍历行重建行的存储，列和子九宫格用map保存了对应的数据，每次取出对应的数据来比较。子九宫格判断当前元素是第几个子九宫格，用index = (m / 3) * 3 + n / 3即可，最近看二维数组相关的题，基本都会用到行或列的除法，算当前元素在几行几列，这也算是这类问题的小技巧吧。
class Solution {
public boolean isValidSudoku(char[][] board) {
Map<Integer, List<Character>> colMap = new HashMap<>(16);
// 子九宫格map
Map<Integer, List<Character>> subMap = new HashMap<>(16);
int i = board.length;
int j = board[0].length;
for (int m = 0; m < i; m++) {
List<Character> rowList = new ArrayList<>(16);
for (int n = 0; n < j; n++) {
char current = board[m][n];
if (current == '.') {
continue;
}
// 判断行是否有重复
if (rowList.contains(current)) {
return false;
}
// 判断列是否有重复
List<Character> colList = new ArrayList<>(16);
if (null != colMap.get(n)) {
colList = colMap.get(n);
}
if (colList.contains(current)) {
return false;
}
// 判断子九宫格是否有重复
int index = (m / 3) * 3 + n / 3;
List<Character> subList = new ArrayList<>(16);
if (null != subMap.get(index)) {
subList = subMap.get(index);
}
if (subList.contains(current)) {
return false;
}
rowList.add(current);
colList.add(current);
colMap.put(n, colList);
subList.add(current);
subMap.put(index, subList);
}
}
return true;
}
}
官方解法
官方解法和自己解法思路相同，只是直接用数组分别维护了9个hashMap去保存行、列、子九宫格的信息，然后采用的value-> count的hashMap去记录元素出现的次数，在只有9个元素的情况下，速度比list.contains这种遍历查找没快太多，量大的话应该会更快。
class Solution {
public boolean isValidSudoku(char[][] board) {
// init data
HashMap<Integer, Integer> [] rows = new HashMap[9];
HashMap<Integer, Integer> [] columns = new HashMap[9];
HashMap<Integer, Integer> [] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<Integer, Integer>();
columns[i] = new HashMap<Integer, Integer>();
boxes[i] = new HashMap<Integer, Integer>();
}
// validate a board
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num != '.') {
int n = (int)num;
int box_index = (i / 3 ) * 3 + j / 3;
// keep the current cell value
rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);
// check if this value has been already seen before
if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
return false;
}
}
}
return true;
}
}
网友评论