【leetcode】36. Valid Sudoku
程序员文章站
2022-07-15 12:31:57
...
题目:
思路:
用map<int, vector>(其实用vector也行),将所有“1”出现的位置及其块号都保存起来;将所有“2”出现的位置及其块号都保存起来;将所有“3”出现的位置及其块号都保存起来······每添加一个新的数字时,都看看与已保存的其他等值数字的位置是否冲突。
代码实现:
class Solution {
public:
struct Point{
int r;
int c;
int block;
};
int getBlockIndex(int r, int c){
// todo
return r/3 * 3 + c/3;
}
bool isInt(char c){
return c >= '0' && c <= '9';
}
int char2Int(char c){
return c - '0';
}
bool isValidSudoku(vector<vector<char>>& board) {
map<int, vector<Point>> hash;
for (int i = 1; i <= 9; ++i){
vector<Point> t;
hash[i] = t;
}
for (int i = 0; i < board.size(); ++i){
for (int j = 0; j < board[i].size(); ++j){
if (isInt(board[i][j]) == true){
vector<Point> &t = hash[char2Int(board[i][j])];
int blockIndex = getBlockIndex(i,j);
for (int k = 0; k < t.size(); ++k){
if (t[k].r == i || t[k].c == j || t[k].block == blockIndex){
return false;
}
}
t.push_back({i,j,blockIndex});
}
}
}
return true;
}
};
思路2:
- 一行一行地检查
- 一列一列地检查
- 一块一块地检查
这三部分代码可以写在一起,参考https://www.cnblogs.com/ganganloveu/p/4170632.html。
上一篇: 使用CoreData的轻量级自动数据迁移
下一篇: 创业 - 在路上
推荐阅读
-
LeetCode - 20. Valid Parentheses(0ms)
-
LeetCode-32.Longest Valid Parentheses最长有效括号子串
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划
-
36. Valid Sudoku
-
【leetcode】36. Valid Sudoku
-
LeetCode - 36. Valid Sudoku
-
LEETCODE 36. Valid Sudoku
-
[LeetCode]36. Valid Sudoku
-
leetcode题集: 36. Valid Sudoku
-
36. Valid Sudoku