前不久写的这个 软件工程师面试技巧 的系列, 朋友很喜欢, 所以我打算把我毕生所学(哈哈)整理整理分享于大家,望喜欢.另:我觉得:分享就是一种再学习的过程.
给定一个数独,我们要检查是否有效.一个有效的数独横的竖的都只出现1-9的数字各一次,并且9个小宫格里的数字也只出现1-9各一次.
你能快速的告诉我以下是否是个有效的数独么?
我们只需要检查给定的数独中已经填好的数字.最好的方法就是通过 C++中 STL 的 unordered_set (未排序的集合) 来保存已经出的数字.记得检查下一个9宫格或者行或列的时候清空集合便可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | // https://justyy.com/archive/4998 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; } }; |
// https://justyy.com/archive/4998 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; } };
这题并不难,意在考灵活使用数据类型(集合),面试的时候第一个需要思考的就是:这题是否可以用穷举(暴力)来解答? 即使你的暴力不太现实(需要计算力太久,像比特币挖矿一样),但是对于考官来说,这也是解决方法的第一步,之后才会考虑是否可以有其它高效的方法来提速.
英文: How to Check Valid Sudoku in C/C++?
GD Star Rating
loading...
本文一共 365 个汉字, 你数一下对不对.loading...
上一篇: 小白教程: 怎么领取 BCC (Bitcoin Cash) ?
下一篇: 软件工程师面试技巧之 动态规化 - 整数拆分
扫描二维码,分享本文到微信朋友圈
手机数独我玩过,代码的字母我认识.
其实我主要为了沙发的,哈哈!
多谢 沙发一定留给你