I'd like to continue the series of "Software Engineer Interview Questions or Tips" where I'd share you with some coding questions/tips from time to time. To share is the process of re-learning.
- Google Interview Question – Print Message
- Software Engineer Interview Tips - Using Hashtable to Reduce Runtime Complexity
Determine if a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
A valid Sudoku contains three conditions: (1) all rows should contain exactly 1 to 9. (2) all columns should contain exactly 1 to 9. (3) all sub grids (9 of them) should contain exactly 1 to 9.
The best data structure we can use is the STL:set, we need to clean the set before next validation (row, column or grid).
前不久写的这个 软件工程师面试技巧 的系列，朋友很喜欢，所以我打算把我毕生所学（哈哈）整理整理分享于大家，望喜欢。另：我觉得：分享就是一种再学习的过程。
给定一个数独，我们要检查是否有效。一个有效的数独横的竖的都只出现1-9的数字各一次，并且9个小宫格里的数字也只出现1-9各一次。
你能快速的告诉我以下是否是个有效的数独么？
我们只需要检查给定的数独中已经填好的数字。最好的方法就是通过 C++中 STL 的 unordered_set (未排序的集合) 来保存已经出的数字。记得检查下一个9宫格或者行或列的时候清空集合便可。
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_set<int> has;
for (int i = 0; i < 9; i ++) {
has.clear();
// rows = 行
for (int j = 0; j < 9; j ++) {
if (board[i][j] != '.') {
if (has.count(board[i][j])) {
return false;
}
has.insert(board[i][j]);
}
}
has.clear();
// columns = 列
for (int j = 0; j < 9; j ++) {
if (board[j][i] != '.') {
if (has.count(board[j][i])) {
return false;
}
has.insert(board[j][i]);
}
}
}
for (int i = 0; i < 3; i ++) {
for (int j = 0; j < 3; j ++) {
// 9 sub grids - 每一个9宫格也要检查
has.clear();
for (int x = i * 3; x < i * 3 + 3; x ++) {
for (int y = j * 3; y < j * 3 + 3; y ++) {
if (board[x][y] != '.') {
if (has.count(board[x][y])) {
return false;
}
has.insert(board[x][y]);
}
}
}
}
}
return true;
}
};
这题并不难，意在考灵活使用数据类型（集合），面试的时候第一个需要思考的就是：这题是否可以用穷举（暴力）来解答？即使你的暴力不太现实（需要计算力太久，像比特币挖矿一样），但是对于考官来说，这也是解决方法的第一步，之后才会考虑是否可以有其它高效的方法来提速。
Originally Published in Steemit. Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.
原创首发 SteemIt, 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.
广告一下微信群用于讨论各类编程技术：只要您对技术感兴趣都可以加群哈。
