Loading... > 今天在 LeetCode 做到一道题：[有效的数独][1]，难度是中等。 ### 题目 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 1. 数字 1-9 在每一行只能出现一次。 2. 数字 1-9 在每一列只能出现一次。 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 ![数独题目][2] 上图是一个部分填充的有效的数独。 数独部分空格内已填入了数字，空白格用 '.' 表示。 ### 代码 如果你只想通过程序，直接复制就行了(｡•ˇ‸ˇ•｡) ```cpp // 个人代码先贴上。做法不一定好，但能通过！ class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int bnl = 0; // 当前块位置（默认从0开始） for(int i = 0; i < 9; i++){ map<char,int> sta_h; map<char,int> sta_l; map<char,int> sta_b; // 检查行 for(int j = 0; j < 9; j++){ if(board[i][j] != '.'){ if(sta_h[board[i][j]] == 0){ sta_h[board[i][j]] = 1; }else{ return false; } } } // 检查列 for(int j = 0; j < 9; j++){ if(board[j][i] != '.'){ if(sta_l[board[j][i]] == 0){ sta_l[board[j][i]] = 1; }else{ return false; } } } // 检查块 int now_h,now_l; // 取得当前 3X3 的初始行列 if((bnl / 3) < 1){ now_h = 0; now_l = (bnl * 3); }else if((bnl / 3) >= 1 && (bnl / 3) < 2){ now_h = 3; now_l = ((bnl - 3) * 3); }else{ now_h = 6; now_l = ((bnl - 6) * 3); } if(now_l == -1){ now_l = 0; } for(int j = now_l; j < now_l + 3; j++){ // 开始时的列 for(int k = now_h; k < now_h + 3; k++){ // 开始时的行 if(board[k][j] != '.'){ if(sta_b[board[k][j]] == 0){ sta_b[board[k][j]] = 1; }else{ return false; } } } } bnl ++; } return true; } }; ``` ### 解题思路 这道题的难点主要在: “数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。” 横竖不能重复是非常简单的，只需要进行遍历并记录每个出现过的信息即可。 在个人代码中创建了三个Map用于储存已被使用过的数据: * sta_h: 储存行检测中出现过的值 * sta_l: 储存列检测中出现过的值 * sta_b: 储存块检测中出现过的值 每一次扫到非“.”的值时就检测是否存在，存在则直接 return false; 不存在则将map状态转为已存在。 在做这道题时很快就完成了横竖的检测。但 3 X 3 时却卡了很久（当时还以为这题贼简单） #### 3 X 3 宫内检测 首先我的思路是：在这个 9 X 9 的数独中正好有 9 个 3 X 3 的宫。可以使用一个变量来储存当前遍历到的宫是哪一个，然后可以通过简单的计算算出下一个需要检测的宫的开始位置。 由于需要检测的宫正好也有 9 个，所以可以直接把这个检测程序也放到横竖检查的遍历中。 ```cpp // 取得当前 3X3 的初始行列 if((bnl / 3) < 1){ now_h = 0; now_l = (bnl * 3); }else if((bnl / 3) >= 1 && (bnl / 3) < 2){ now_h = 3; now_l = ((bnl - 3) * 3); }else{ now_h = 6; now_l = ((bnl - 6) * 3); } if(now_l == -1){ now_l = 0; } ``` 上面的代码可以取得对应宫的初始行和列（这段代码很水，我都不知道自己是怎么搞出来的） 遍历时便可根据取得的初始行列进行检查。中间检查是否存在的程序和横竖的检测是一样的。 ```cpp for(int j = now_l; j < now_l + 3; j++){ // 开始时的列 for(int k = now_h; k < now_h + 3; k++){ // 开始时的行 if(board[k][j] != '.'){ if(sta_b[board[k][j]] == 0){ sta_b[board[k][j]] = 1; }else{ return false; // 如果中途发现重复数据，直接返回 false } } } } bnl ++; // bnl 记录了当前所在的块（当一个块检测完毕，就进入下一个检测） ``` 这道题写的很水，如果有大佬有改进意见请评论给我！万分感激！！ [1]: https://leetcode-cn.com/problems/valid-sudoku/ [2]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png Last modification：May 10th, 2020 at 09:44 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
